Skip to content

Latest commit

 

History

History
94 lines (73 loc) · 5.36 KB

README.md

File metadata and controls

94 lines (73 loc) · 5.36 KB

Other Solvers

To facilitate benchmarking, several solvers of current or historical interest are included here.

So set them up for benchmarking run the following commands:

git submodule update --init --recursive
other/setup_jczsolve.sh 
other/setup_rust_sudoku.sh

  1. norvig-sudoku (P.Norvig 2007)
    A C++ port of the solver from Peter Norvig's well known article Solving Every Sudoku Puzzle.

    • Sources are included as a git submodule.
    • build with -DNORVIG=on

  2. fast_solv_9r2 (I.Zelaya 2008)
    An early exact cover/DLX-based solver originally announced here on the setbb Sudoku Programmers Forum and subsequently included in attractivechaos's benchmarks of fast solvers in 2011.

    • Patched sources from here are already included.
    • build with -DFAST_SOLV_9R2=on

  3. zerodoku (J.Schirle 2008)
    A simple and fast solver included in early benchmarks by members of the setbb Sudoku Programmers Forum, and later by attractivechaos.

    • Patched sources from here are already included.
    • build with -DZERODOKU=on

  4. bb_sudoku (B.Turner 2009)
    An influential early solver originally announced here on the setbb Sudoku Programmer's Forum. Capable of using hidden singles, locked candidates, subsets, and various fishes, but configured here for benchmarking using only hidden singles and locked candidates since this is the fastest mode.

    • Patched sources from here are already included.
    • Build with -DBB_SUDOKU=on

  5. JSolve (J.Linhart 2010)
    An early fast solver tracing its lineage to bb_sudoku with additional optimization. Originally announced here on the setbb forum and subsequently included in attractivechaos's benchmarks of fast solvers in 2011.

    • Patched sources from here are already included.
    • build with -DJSOLVE=on

  6. FSSS (M.Dobrichev 2010)
    Another fast solver from the era of JSolve and bb_sudoku.

    • Patched sources from here are already included.
    • build with -DFSSS=on

  7. kudoku (AttractiveChaos 2011)
    A solver based on exact cover (but not using dancing links). Kudoku can be seen in action here and also as a part of attractivechaos's own benchmarks of fast solvers in 2011.

    • Patched sources from here are already included.
    • build with -DKUDOKU=on

  8. FSSS2 (M.Dobrichev 2014-2015)
    A SIMD bitboard-based redesign by the author of FSSS which set a new standard of performance.

    • Sources are included as a git submodule.
    • build with -DFSSS2=on

  9. lhl_sudoku (Lee Hsien Loong, <2015)
    A casual but well-known solver with the distinction of being the only one on this list written by a head-of-state.

    • Sources are included as a git submodule.
    • build with -DLHL=on

  10. JCZSolve (Zhouyundong et al. 2012-2016)
    A fast and influential solver incorporating an innovative representation by Zhouyundong and resulting from the collaborative effort of several members of the New Sudoku Players Forum.

    • Copyright unspecified and sources not directly incliuded.
    • The setup_jczsolve.sh script will fetch and patch sources from JCZSolve10.zip attached to this post.
    • build with -DJCZSOLVE=on

  11. SK_BFORCE2 (GPenet 2018)
    A solver derived from JCZSolve and including further optimizations.

    • Sources are included as a git submodule.
    • build with -DSK_BFORCE2=on

  12. rust_sudoku (Emerentius 2017-2019)
    The rust Sudoku library. A port of JCZSolve to rust and including further optimizations.

    • Sources are included as a git submodule, but require a separate build step.
    • Install rustup
    • Run other/setup_rust_sudoku.sh, which will build rust_sudoku shared libraries using clang 9,10,11
    • Build with -DRUST_SUDOKU=on

  13. gss (Bart 2019)
    A solver aimed at using as many inference techniques as possible to reduce the need for backtracking (see here).

    • Sources are included as a git submodule.
    • build with -DGSS=on

For additional comparisons, the project also includes Sudoku solvers based on a few genera purpose SAT solvers and optimizers:

  1. Minisat

    • $ sudo apt install minisat libz-dev
    • Build with -DMINISAT=on

  2. Gurobi

    • Install Gurobi
    • Build with -DGUROBI=on -DGUROBI_DIR=${GUROBI_LOCATION}/gurobi900/linux64

  3. Z3

    • $ sudo apt install libz3-dev
    • Build with -DZ3=on