The New Sudoku Players' Forum

[dobrichev]

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?

[Mathimagics]

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?

[dobrichev]

I have never used clang.
Surely with some acrobatics the code can be made fast on any modern compiler.
I trust Tom's benchmarks.

[tdillon]

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.

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]

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:

[tdillon]

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):



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



Cheers!