t-dillon / tdoku Goto Github PK

Hi Tom,

Thanks for writing this awesome sudoku generator!

I want to make a mobile app and i need some puzzles which categorized by easy/medium/hard/...

I simply try it like "build/generate -p0 -c0 -g1 -d1 -n100 -e50 -s0 -l5"
but i don't know how to use parameters to generate games with specified difficulty.

Can you help me please?

Hello Tom, thanks for this amazing project I am making a small side project a sudoku game where I was trying to generate some really difficult puzzles. can you help me with a config for that I tried one you shared in an issue earlier but it requires minisat to be enabled and when I am trying to build with minisat I am greeted with the following error?

I did install minisat using brew but still, the error comes up.

A small config for creating extremely hard puzzles would be a great help.

❯ ./BUILD.sh  -DMINISAT=on
-- The C compiler identification is AppleClang 13.0.0.13000029
-- The CXX compiler identification is AppleClang 13.0.0.13000029
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/cc - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Check for working CXX compiler: /Applications/Xcode.app/Contents/Developer/Toolchains/XcodeDefault.xctoolchain/usr/bin/c++ - skipped
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Configuring done
-- Generating done
-- Build files have been written to: /Users/ashish/tdoku/build
[  4%] Building CXX object CMakeFiles/tdoku_object.dir/src/solver_dpll_triad_simd.cc.o
[  8%] Building CXX object CMakeFiles/tdoku_object.dir/src/util.cc.o
[  8%] Built target tdoku_object
[ 12%] Linking CXX static library libtdoku_static.a
[ 12%] Built target tdoku_static
[ 16%] Linking CXX shared library libtdoku_shared.dylib
[ 16%] Built target tdoku_shared
[ 20%] Building CXX object CMakeFiles/run_benchmark.dir/src/run_benchmark.cc.o
[ 24%] Building CXX object CMakeFiles/run_benchmark.dir/src/util.cc.o
[ 28%] Building CXX object CMakeFiles/run_benchmark.dir/src/solver_dpll_triad_simd.cc.o
[ 32%] Building CXX object CMakeFiles/run_benchmark.dir/other/other_solvers.cc.o
[ 36%] Building CXX object CMakeFiles/run_benchmark.dir/other/other_minisat.cc.o
/Users/ashish/tdoku/other/other_minisat.cc:1:10: fatal error: 'minisat/core/Solver.h' file not found
#include <minisat/core/Solver.h>
         ^~~~~~~~~~~~~~~~~~~~~~~
1 error generated.
make[2]: *** [CMakeFiles/run_benchmark.dir/other/other_minisat.cc.o] Error 1
make[1]: *** [CMakeFiles/run_benchmark.dir/all] Error 2
make: *** [all] Error 2
❯ brew install minisat
Warning: minisat 2.2.1 is already installed and up-to-date.
To reinstall 2.2.1, run:
  brew reinstall minisat

I've written a few sudoku solvers, but I've avoided recursion because I wanted to make sure I didn't overflow the stack if I wanted to use it on larger boards. Reading some of the listed benchmark timings I'm wondering if there's some performance benefit to having the cpu essentially handle a stack with recursion. I've got two implementations, one I think is equivalent to the basic solver you have listed, the other uses additional bitmasks to do space based eliminations (I think the term's called cross hatching). They run about 1ms and 3ms per puzzle. If I template out specifically for the board size it seems to roughly improve performance by a factor of 10, but obviously my hardware's not the same and my code's probably not ideal.

The cross hatching approach seems to shave a significant amount of branching factor from the basic algorithm by cutting the guess work by a fourth, but it doesn't seem to pay off unless the board is complex.

I'd be curious to see what the benchmarks look like.

The link to the 17 clue Sudoku puzzles do not work.
Getting 1020 error access denied.
README

Hi Tom! Really appreciate your work on this.

Can you please add support for generating and solving sudokus other than the classic 9x9 variant? If not as command-line arguments, maybe as compile-time options.

As you must be well aware sudokus are of interest to not only the human players, but also to AI researchers. With the recent advances in Neuro-Symbolic AI, Sudoku datasets are becoming a popular testbed once again. One often requires experimenting with different variants with larger sizes and rectangular boxes (like 6x6 sudokus with 2x3 boxes) to investigate interesting questions regarding scalability and generalisation.

Your repository contains one of the most complete treatments of sudoku solvers and generators, and I'm sure it would be of great utility to extend it with this feature. Thanks.

I don't know a lot of C or C++, but I tried to analyze the code as well as I could.
In ./include/tdoku.h there is a function

static inline size_t SolveSudoku(const char *input, size_t limit, uint32_t configuration,
                                 char *solution, size_t *num_guesses) {
    return TdokuSolverDpllTriadSimd(input, limit, configuration, solution, num_guesses);
}

I am just assuming that the TdokuSolverDpllTriadSimd is "imported" from ./src/solver_dpll_triad_simd.cc.
My situation is the following:
I have a single string representing a puzzle (that has only one solution) and want to find that one solution.

Let's say that I have a variable puzzle containing a str with a length of 81 or 729.
Now, I would like to have a function get_solution that takes a puzzle and returns a tuple (solution,num_guesses) (I don't need the regular return value.)

1. Would you mind writing a small python script that exposes the function to python? If you are especially generous with your time, you could also explain your code and how to compile the files when using python.

2. Another problem is that I am running Windows and the make command in BUILD.sh isn't running, but I might just use WSL or do you maybe know a way how to compile the whole folder just with gcc?

3. Also, I haven't quite understood all the parameters in the generator. Especially not -c,-g,-r,-d,-e,-n. What is the effect on the Sudoku of those options, respectively.