The New Sudoku Players' Forum

[Mathimagics]

Did you add some logical rules for 16 x 16 Sudoku solver?

Not yet.

The current solver is simply a port of the 9x9 FSSS2 solver, with 256-bit wide bitmaps instead of 128-bit ones.

But it can easily be extended, and used to demonstrate the ideas discussed above, namely that more complex rules than singles will prove their worth on a larger grid than 9x9. The humungous solution space of 16x16, dwarfs that of 9x9 (16 is a planet, while 9 is a pea). That almost guarantees that any additional methods will speed up, rather than slow down, the solver.

Cheers
MM

PS: I too am interested in whether tdillon's solver is scalable to 16x16. I suspect it might be difficult, but he will tell us shortly.

Also, I think that creint's solver definitely is scalable, and thus we might be able to do some simple experiments.

[Serg]

Hi, rjamil!
I think the difference between "backtracking" and "brute-force" Sudoku solvers is meaningful for purists only. These names for Sudoku solvers are equivalent in wide sense. But since we started discussing this topic, I should say that my unerstanding of brute-force Sudoku solving procedure differs from yours.

I think that brute-force Sudoku solving technique is selection of any combination of digits 1-9 in all empty cells, even as meaningless as ones for all empty cells. Only when all empty cells are filled (and we have some solution to check), we check if it meets the rules of sudoku. If that solution contains the same digits in some row/column/box, solution is rejected and we form another (full) solution, changing some digits in empty cells. This strategy is insanely ineffective, so noone use it in practice, but instead all use backtracking procedure.

It's a paradox, but I think all "logical" Sudoku solver (implemented in procedural programming languages) are backtracking solvers. At every step they can use maybe very sophisticated logical methods just to get another partial solution. There is no principal difference between a solver checking naked/hidden singles only and a solver checking forcing chains, exosets, etc.

Serg

[Edited] I deleted wrong statement.

[Serg]

Hi, all!
After some pondering I propose such Sudoku solvers classification.

- "Backtracking" or universal Sudoku solvers. They deal with puzzles having 0, 1 or multiple solutions. The main goal of these solvers - to find all/first/first two solutions (or count all/first 2 solutions) as fast as possible. Their implementations are based on backtracking algorithm reinforced by some logical techniques for speed. These solvers are the fastest. Examples: fsss2, JCZsolver, tdoku, etc. Some people call these solvers "brute-force".

- "Human style" solvers. They deal with puzzles having unique solution only. The goal of these solvers - to find unique solution using some combination of logical techniques. If at some step no techniques can be applied, these solvers says the puzzle has no human logic solution. Such solvers differ by their applicability (i.e. by number of puzzles they can solve in human style), elegancy of solutions, etc. Before "human style" solvers usage one must check - is given puzzle valid? (i.e. has it unique solution?) by some backtracking solver.

Serg

[Edited. I corrected a typo.]

[tdillon]

Did you checked use of other logical solving rules (beyond naked/hidden singles and locked candidates) in your "tdoku" solver?

Hi Serg,

Tdoku also has exactly-three constraints over minirows and minicols (what I was calling triads). I think these correspond to locked triples and hidden triples (when confined to a minirow or minicol)

Tom

[tdillon]

PS: I too am interested in whether tdillon's solver is scalable to 16x16. I suspect it might be difficult, but he will tell us shortly.

Hi Mathimagics,

I think it would be pretty easy to extend tdoku to the 16x16 case. In a way it's a more natural fit than 9x9 since it would fully exploit 256 bit registers. But tdoku has had a lot of micro-optimization for the 9x9 case, and it would take some effort to tune it back up again. For example, I'm not sure the special representation I have of band configurations would be worthwhile for 16x16, and it might be simpler to just represent band state with a matrix of positive triads.

Totally agree that more expensive heuristics and constraint propagation will become worthwhile for 16x16 and larger. You can also see this reflected in the relative performance gains of Minisat when compared to fsss2 and tdoku on difficult pencilmark sudoku.

Tom

[rjamil]

Hi Serg,

Hi, rjamil!
I think the difference between "backtracking" and "brute-force" Sudoku solvers is meaningful for purists only. These names for Sudoku solvers are equivalent in wide sense. But since we started discussing this topic, I should say that my unerstanding of brute-force Sudoku solving procedure differs from yours.

Serg

First of all, many thanks for your valuable response.

I think, there are two types of problems that need to be solve by two different type of Brute-Force (exhaustive) algorithms, i.e., deterministic and randomized algorithms. See here and here and here.

Based on my above mentioned assumption, your definition also seems to be right.

R. Jamil

[RSW]

FSSS is a simple backtracking solver with naked single + hidden single checking as the fundamental search-tree pruning method.

It gets its speed advantage by a highly efficient representation of the current puzzle state, using bitmaps. This is designed in such a way as to make the testing for hidden singles more efficient.

This is good to know.
When I set up my own brute force solver, I never considered doing it without some kind of singles checking. It was trivial to include naked singles, but hidden singles were more complicated due to the data structure that I chose. I'm also using bit mapping, but would need to include a second set of bit maps to handle hidden singles. In most cases, just the naked singles eliminations were sufficient for my needs. But rare puzzles would be horrendously slow to solve this way. So, I added one hidden singles scan at the beginning, and then reverted to just naked singles for the rest of the solution. This sped things up considerably, but there are still occasional puzzles where this isn't sufficient. So, I'll probably add a second set of bit patterns to handle the hidden singles at each level.

@rjamil
Great animation!

[m_b_metcalf]

@rjamil
Great animation!

Indeed, but if I stare at the cells r5c3 or r6c2 I sometimes see the value 7 flash by, but that value cannot be in the pencil marks for those cells. So why are they shown?

Thanks,

Mike

[Mathimagics]

Mike,

See here: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking

[RSW]

Mike,

See here: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking

Now I'm totally disillusioned.

[m_b_metcalf]

See here: https://en.wikipedia.org/wiki/Sudoku_solving_algorithms#Backtracking

MM, Thanks. I'll clearly have to pose my simple-minded question elsewhere!

Mike

[Mathimagics]

Mike, my apologies, I did fail to answer your question.

There are no pencilmarks in this simplified solver. It is a backtracking solver reduced to its purest/simplest form.

For each unsolved cell (left to right) the solver the tests all possible candidates 1 to 9. The current cell's candidate value is shown in blue. If this value contradicts the Sudoku rules, the cell is cleared and the solver returns (backtracks), and moves on to the next value.

So, for example, you will occasionally see a red 7 appear in box 4, but since this always results in a contradiction (since box 4 already has a 7), it immediately disappears as the search procedure backtracks.

Cheers
MM

[m_b_metcalf]

There are no pencilmarks in this simplified solver. It is a backtracking solver reduced to its purest/simplest form.

MM, Thanks. I just didn't realise that this simplest form was of any practical use. I have a number of backtracking solvers. They all involve:

1. Set up a list of pencil marks (valid candidate values).
2. Solve as far as possible for singles.
3. 'Condition' the puzzle by rearranging its row/columns/bands so as to have the highest density of givens in its top left corner and the lowest in the bottom right.

Thus, the statement "A brute force algorithm visits the empty cells in some order, filling in digits sequentially, or backtracking when the number is found to be not valid." becomes for me

"My brute force algorithm visits the empty cells in an optimized order, filling in valid candidates sequentially, or backtracking when the number is found to be not valid."

Regards,

Mike

[Mathimagics]

The method of visiting (unsolved) cells in an optimal order is what I called the NCS (next cell selection) strategy in this old thread, the rather flippantly titled Guess Theory.

There I make a general point that a depth-first search solver will inevitably encounter some pathological cases where its NCS is sub-optimal. This is not usually an issue for 9x9 solvers, but becomes a serious issue for 16x16.

[rjamil]

Hi Mike,

1. Set up a list of pencil marks (valid candidate values).

Well, by setting up a list of valid candidate values at initial puzzle state and/or after each step, instead of all 1 to 9 values, will violate brute-force definition and should be called T&E / guessing algorithm.

R. Jamil