Tdoku: a speedy Sudoku solver

Programs which generate, solve, and analyze Sudoku puzzles

Re: Tdoku: a speedy Sudoku solver

Postby dobrichev » Thu Jul 11, 2019 9:45 pm

Hi Tom,

In a short time your solver evolved from a toy "touch and go" project to a serious solving machine.
Congratulations for these striking results!

Are you planning extensions like checking for redundant clues?
dobrichev
2016 Supporter
 
Posts: 1762
Joined: 24 May 2010

Re: Tdoku: a speedy Sudoku solver

Postby Mathimagics » Fri Jul 12, 2019 1:33 am

I take it that I am the only one who can't compile it with clang … major bummer :(

@Mladen: I assume that you can compile it with clang on Win10-x64, but that you also have MSVC on your rig .. Is that right?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1396
Joined: 27 May 2015
Location: Canberra

Re: Tdoku: a speedy Sudoku solver

Postby dobrichev » Fri Jul 12, 2019 6:49 am

I have never used clang.
Surely with some acrobatics the code can be made fast on any modern compiler.
I trust Tom's benchmarks.
dobrichev
2016 Supporter
 
Posts: 1762
Joined: 24 May 2010

Re: Tdoku: a speedy Sudoku solver

Postby tdillon » Fri Jul 12, 2019 8:46 am

dobrichev wrote:In a short time your solver evolved from a toy "touch and go" project to a serious solving machine.
Congratulations for these striking results!
Are you planning extensions like checking for redundant clues?

Thanks Mladen! Other projects beckon, so I'm not planning much more work on this for now.

Mathimagics wrote:I take it that I am the only one who can't compile it with clang

I've made a few changes for windows, and now it works for me with http://releases.llvm.org/8.0.0/LLVM-8.0.0-win64.exe

Compiling the benchmark program with just Tdoku:
(add -mavx2 if appropriate)
Code: Select all
clang++.exe -o run_benchmark.exe -O3 '-msse4.1' -Xclang -flto-visibility-public-std .\src\run_benchmark.cc .\src\solver_basic.cc .\src\solver_dpll_triad_scc.cc .\src\solver_dpll_triad_simd.cc .\src\other_solvers.cc

Compiling the benchmark program with Tdoku and SK_BFORCE2:

Code: Select all
clang++.exe -o run_benchmark.exe -O3 '-msse4.1' -Xclang -flto-visibility-public-std -DSKBFORCE .\src\run_benchmark.cc .\src\solver_basic.cc .\src\solver_dpll_triad_scc.cc .\src\solver_dpll_triad_simd.cc .\src\other_solvers.cc .\other\sk_bitfields.cpp .\other\sk_t.cpp

Running:

Code: Select all
PS C:\Users\tom\tdoku> .\run_benchmark.exe -s skbforce,tdoku .\data\puzzles2_magictour_top1465

Give it another try! It also works for me under cygwin, where it's easier to use the standard BUILD.sh, but cygwin has a pretty old version of clang.
tdillon
 
Posts: 20
Joined: 14 June 2019

Re: Tdoku: a speedy Sudoku solver

Postby tdillon » Thu Jul 18, 2019 8:30 pm

In trying to tidy up this project I just revisited an optimization I'd previously considered and rejected. The idea was to merge pending eliminations to a box or a band so they can be applied at the first opportunity instead of individually depending on where in the call stack the eliminations originate from. This made things faster for easy puzzles but slower for hard puzzles, which wasn't a trade-off I liked.

But it turns out I hadn't thought this all the way through. Most of the cost of this change comes from box eliminations since we have to increase the size of the box state by a 256 bit vector. But most of the benefit comes from the band eliminations since we initialize each puzzle by queuing 6 band elimination messages, offering lots of opportunity for quick merges. By performing merges on just the band messages we get improvement on every dataset, with especially significant improvements on the easy or invalid ones:

Code: Select all
kaggle                     1.32x
gen_puzzles                1.24x   <<
17_clue                    1.09x
magictour_top1465          1.04x
seg_benchmark              1.02x
forum_hardest_1905         1.02x
forum_hardest_1905_11+     1.01x
forum_hardest_1106         1.01x

The updated benchmarks:

Image
tdillon
 
Posts: 20
Joined: 14 June 2019

Re: Tdoku: a speedy Sudoku solver

Postby tdillon » Fri Jul 26, 2019 9:08 pm

A few updates:

I've added a comparison to emerentius_ Rust sudoku solver, which proves to be for most platforms and datasets the fastest of the JCZSolve-family solvers. Thanks to emerentius_ for help in getting the Rust project set up for benchmarking!

I've made a few changes to tune Tdoku performance on the most modern hardware I can find (that being the GCE compute-optimzed VM (c2-standard-4) i.e. Cascade Lake). Tdoku sees a nice boost in relative performance on this platform, partly thanks to AVX512VL. Whenever Ice Lake CPUs arrive I hope there will be some further boost thanks to the vector popcount in AVX512BITALG.

Full benchmark results here: https://github.com/t-dillon/tdoku/tree/master/benchmarks

Here's the tested platform most favorable to Tdoku (and least favorable for rust-sudoku vs. SK_BFORCE2):

Image

Here's the tested platform most favorable to rust-sudoku (and least favorable for Tdoku):

Image

Cheers!
tdillon
 
Posts: 20
Joined: 14 June 2019

Previous

Return to Software