SAT Sudoku Solver and Generator

Programs which generate, solve, and analyze Sudoku puzzles

SAT Sudoku Solver and Generator

Postby hkociemba1 » Wed Aug 08, 2018 2:29 pm

I wrote a program to solve/generate Sudokus (not only for the usual boxsize 3x3 but for any any boxsize NxM and N, M < 16). It uses some basic "human" solving techniques but also a SAT-solver can be selected. Download, program usage and some short explanation how the SAT-part works are here:http://kociemba.org/themen/sudoku/program.html

You must have a 64-bit windows systemfor the basic functions and additionally 64-bit Java for the SAT part.

Any questions, feedbacks and criticism are welcome.
User avatar
hkociemba1
 
Posts: 29
Joined: 08 August 2018

Re: SAT Sudoku Solver and Generator

Postby hkociemba1 » Thu Aug 16, 2018 9:48 pm

Though the feedback is not overwhelming yet with 0 replies I want to announce that I now added support for SudokuP variant for any boxsize. The program also could verify the uniqueness of the recently found three 9-clue SudokuPX for boxsize 3x3 (just check both SudokuX and SudokuP).

http://kociemba.org/themen/sudoku/program.html
User avatar
hkociemba1
 
Posts: 29
Joined: 08 August 2018

Re: SAT Sudoku Solver and Generator

Postby StrmCkr » Fri Aug 17, 2018 6:58 am

http://forum.enjoysudoku.com/composing-a-solution-grid-t34745-15.html

has some feed back regarding your code and ideas.

the langue of choice is more keen to my side of the word and very few others... as i use turbo pascal {syntax} is very close to delphi
most on here use c, c# and java with a few ruby coders kicking around.

on-top of that very few share their codes :( information on how to do stuff they do share but direct code is few and far between with the loss of the programmers forum
Some do, some teach, the rest look it up.
User avatar
StrmCkr
 
Posts: 834
Joined: 05 September 2006

Re: SAT Sudoku Solver and Generator

Postby creint » Fri Aug 17, 2018 3:52 pm

It can generate large grids, that's nice, but it gets slower on lower errors, probably because of the randomness.
The reducing part for large grids is very slow 0.8 sec for each given, that can be improved to probably average 1000 givens/sec or faster when you only want known easy strategies.
Reducing givens will probably faster than generating a random grid in this way.
creint
 
Posts: 28
Joined: 20 January 2018

Re: SAT Sudoku Solver and Generator

Postby hkociemba1 » Sat Aug 18, 2018 8:58 am

creint wrote:The reducing part for large grids is very slow 0.8 sec for each given, that can be improved to probably average 1000 givens/sec or faster when you only want known easy strategies.

For fast detection of the easy strategies I use several arrays of bitvectors. The array rc_n for example returns for a given row r and a column c a bitvector rc_n[r,c] which holds the candidates for this cell. The array rn_c returns for for a given row r and a candidate n a bitvector rn_c[r,n] which holds the columns where the candidate n occurs in row r etc.
Adding a clue is easy since there is no ambiguity which candidates have to be deleted in the bitarrays. But for the reducing process you have to remove clues. If you remove a clue you cannot just reverse the process and set the corresponding bits in the arrays.
So what I do in the moment is to completely recompute the arrays after a single clue is removed (so I start with an empty grid and add again all remaining clues) which of course is very timeconsuming in the case of large grids with tens of thousends clues. Almost all of the 0.8 s goes here - I did not notice this before. Faster approaches are possible and I already have something in mind which should not be too complicated to implement. Thanks for the suggestion.
User avatar
hkociemba1
 
Posts: 29
Joined: 08 August 2018

Re: SAT Sudoku Solver and Generator

Postby hkociemba1 » Tue Aug 21, 2018 9:24 pm

I have completely rewritten the clue removal routine and the reduction is at least one magnitude faster than before for large grids. The new version 0.93 is downloadable on my homepage.
User avatar
hkociemba1
 
Posts: 29
Joined: 08 August 2018


Return to Software