The New Sudoku Players' Forum

[sdk_fan]

What are your exact criteria for preferring one approach over another?

Very simple: avoiding assigning a candidate in a box and see how it goes; and using the result to decide if such assignment can be a part of the solution.

When we talk there are always assumption.

I assume a reasonable CPU time is background requirement, which you don't. You assumed a known set of solution grids are already available, which I don't.

[JasonLion]

Then consider multi-digit templates (a POM variation). All possible single digit templates are matched against the grid and the sets of single digit compatible templates are then matched for compatibility with sets of templates for another digits, building up sets of per-digit mutually compatible templates. When you complete the process of merging in all 9 digits you are left with the set of all possible solutions.

This approach does not guess, does not backtrack, is not trial and error, does not assign candidates to boxes without facts to prove that assignment is correct, and it runs in plausible CPU time (typically seconds to hours, depending on the puzzle) on readily available machines.

---

I certainly do not assume that the set of all possible solution grids is already available. It can be created on demand extremely easily, for example by using techniques based on the approach that was used to count the number of such grids that exist. The matching of a clue set against the set of all possible solutions is an important design pattern to understand because, in a deep sense, all solvers work this way. All solvers are doing some kind of search through the space of all possible solution grids (or larger spaces that contain that one as a subset). Looking at things from this point of view, the differences between solvers are in how they divide up that space into smaller chunks and in what order they tackle these smaller chunks. That means that two of the most interesting questions you can ask about a solver, if not the most interesting, is how it divides up the solution space and how efficiently that division allows it to prune the search tree.

Most of the common brute force solvers actually work by enumerating/searching a much larger space, the set of all possible placements of digits into the grid (without being limited by the Sudoku one rule). They then prune off huge portions of the enumeration using Sudoku knowledge derived from the already solved cells. The enumeration is typically done using recursion with aggressive pruning, and typically involves what most people call backtracking. But at a conceptual level neither recursion or backtracking is required. Conceptually they are simply selecting the valid solutions out of the space they are enumerating/searching.

[sdk_fan]

No comment on POM, since I do not understand it.

Here I attached a message I sent to Andrew Stuart:

First of all I want to explain my view of brute-forcing: It means "exhaustive trial" to me. But my algorithm only implements "exhaustive consideration" of n (n<=27) constraints currently processed.
no trial is ever attempted.

A distinction is that when you "try" a candidate, you are NOT using the Sudoku specific methodology but a universal methodology.
But every elimination in my algorithm relies only on Sudoku specific knowledge., and I have to perform "exhaustive consideration" of available constraints because I want to exhaustively apply these understood knowledge on the remaining Sudoku specific knowledge that are not yet considered. But when all such Sudoku-specific knowledge are considered, we are done, guaranteed, and no universal methodology is used.

In short, the exhaustive consideration of processed constraints is necessary, since I have to consider 27 constraints one at a time.

[eleven]

Ah ok, you are really doing this "no guessing/no contradiction eliminations" thing (in the true spirit of Myth Jellies). Excuse me, i have banned that out of my mind before years because of its ineffectiveness. But it was always clear, that it is possible, simply because any contradiction elimination of the form "try a candidate and prove a contradiction" can be reformulated as a "pure" deduction/implication to a form: "All possible assignments in the affected cells/regions dont allow this candidate". The bad thing of the "good" elimination is, that it is a lot more complicated in almost all cases with a certain amount of complexity.

With this in mind, i think, that your computation times are very good (if its minutes for the hardest, though the program is not speed optimized) and can compare well to the 9 digit POM method described by Jason.

[eleven]

sdk_fan,

one more thought.

Take this algorithm, similar to yours, but much simpler:

Code: Select all

0. Define an order of units (regions), e.g.
   b1,r1,c1,r2,c2,b2,r3,b3,b4,c3,b7,r4,c4,b5,r5,r6,b6,c5,c6,b8,r7,c7,r8,c8,r9,c9,b9
1. Take the first one and list all possible subset solutions
2. For all other units
   Fix the common part (cells) of each solution and add all possible solutions including this unit.
   If there are more than 2, make a copy for each.
   If there is none, delete it.


This also should leave you with all puzzle solutions.

Do you think, it would be slower or need more memory than yours ?

[sdk_fan]

sdk_fan,

one more thought.

Take this algorithm, similar to yours, but much simpler:

Code: Select all

0. Define an order of units (regions), e.g.
   b1,r1,c1,r2,c2,b2,r3,b3,b4,c3,b7,r4,c4,b5,r5,r6,b6,c5,c6,b8,r7,c7,r8,c8,r9,c9,b9
1. Take the first one and list all possible subset solutions
2. For all other units
   Fix the common part (cells) of each solution and add all possible solutions including this unit.
   If there are more than 2, make a copy for each.
   If there is none, delete it.


This also should leave you with all puzzle solutions.

Do you think, it would be slower or need more memory than yours ?

Hi, eleven, I have to say that your algorithm is so concise that I do not precisely know the procedure. Do you just come up with it?
But I am sure that you understand the nature of my approach, and if you say yours is similar (which I can tell) then I assume it will work as well.

I am not particularly worried about the memory explosion problem, because it is a good sign that we are treating a problem symbolically rather than by exhaustive trials. (I admit that the symbolic feature of my tree structure is not as obvious as a BDD is.) For example, BDD based symbolic model checker and BDD based SAT solver also has memory explosion issue. But what we can do is to minimise the growth of the size of transient space. Therefore, why specifically

Code: Select all

b1,r1,c1,r2,c2,b2,r3,b3,b4,c3,b7,r4,c4,b5,r5,r6,b6,c5,c6,b8,r7,c7,r8,c8,r9,c9,b9

?
Instead, I think b1,r1,r2,b2,... immediately form a circle of cogwheels, and you probably can prune the your space earlier. Your intervening c1 and c2 dramatically increase your transient space and do you no good both in memory and thus in CPU time alike.
Also we can probably find a better cogwheels circle to start with. Therefore the sequence is not fixed. (And you really do not know the key redundancy can be detected from which circle, and from which history of circle formation.)
My intuition tells me the decision tree I described is intuitive enough and intuition is a good thing, so I wonder what will be the data structure you are going to use.

EDIT: In short:1. the CPU/Memory usage is very much depending on the order of units; The true optimal order is not easily known. 2. choose the most appropriate data structure.

[eleven]

Do you just come up with it?

Yes, it is just an idea i had, when i tried to understand your method. Since i worked with subset puzzles built of units (regions) before, it was a short way there.

I am not particularly worried about the memory explosion problem

I am neither, as long as there is enough space on the hard disc. The memory really needed in RAM is minimal, the rest could be done in files as well, but of course slower.

Instead, I think b1,r1,r2,b2,... immediately form a circle of cogwheels, and you probably can prune the your space earlier.

You are probably right, i did not think much about that. If doing it this way, i would simply start with the band with the least candidates.
[Edit:] No, i would do it this way: Start with the unit with the least candidates. Then out of those, which have the minimum number of "new" unsolved cells (from the last step), again take the one with the least candidates.

... so I wonder what will be the data structure you are going to use.

Just a list of sudokus, with one more unit solved in each step.

[sdk_fan]

No, i would do it this way: Start with the unit with the least candidates. Then out of those, which have the minimum number of "new" unsolved cells (from the last step), again take the one with the least candidates.

I really think this is the only indeterministic part of the algorithm, and any reasonable order is good as long as the space explosion problem can be checked. My experience is that circle-finding, which come with an overhead, is good for very hard puzzle, but it won't be worthwhile for a puzzle with average difficulties. So your heuristics cannot be wrong when you can justify it. The true optimal order won't be easy to know, but perhaps also not worthwhile to know.

Just a list of sudokus, with one more unit solved in each step.

Way to go! Follow your intuition is always good.
My feeling is that when you have branched two subtrees t1 and t2 from a node n, it can be interpreted as n is SHARED by two partial assignments, therefore one node is saved.
But this is implementation detail. As long as you are aware of the memory issue, you won't be off.

[eleven]

Hm, what could be shared ?
All, what could solve n units is possible. And all what cannot solve n+1 units is eliminated in the next step.

[sdk_fan]

Hm, what could be shared ?

Eleven, I am not very clear what data structure you are going to use. So I can only explain to you in my terminology. Sorry.
Think about a multiple N solution sudoku has been solved by algorithm 1, I claim that tree c is the set of solutions.
suppose N = #solutions = # leaves = #paths.

But I only have 1 root, from which all N solutions are branched. Then I can probably say some non-leaf nodes are shared by these paths (which are solutions). So you do not need to save NL pieces of information (L is the # of levels), but only those nodes in tree c.

Likewise, in the middle of computation, I think a tree structure is appropriate.

[eleven]

There are some things i want to say and clarify, but i have no time at all now. Hopefully next weekend...

[sdk_fan]

Anybody understands the procedure and know about BDD will agree my algorithm is not brute-force enumeration at all, but the very opposite: symbolic operation, which means operation working on sets. You achieve that not for a name, but for the real benefit: efficiency. You always get something back when you pay the price for memory.

[JasonLion]

Right now the most efficient known approach, by a significant margin, is standard brute force with limited Sudoku knowledge, guessing, and backtracking. There is some indication/question that SAT might be better, but there aren't any solid timing comparisons and no optimized implementation. My guess is that SAT will win out for larger board sizes but can't match brute force for standard Sudoku.

[sdk_fan]

Right now the most efficient known approach, by a significant margin, is standard brute force with limited Sudoku knowledge, guessing, and backtracking. There is some indication/question that SAT might be better, but there aren't any solid timing comparisons and no optimized implementation. My guess is that SAT will win out for larger board sizes but can't match brute force for standard Sudoku.

This I agree. In the long run, logic method and search should always be combined together.

I have a little concern about the very much talked about DLX- based Sudoku approach. I suppose the algorithm itself is great and general. (I do not understand its detail). I think it is correct, but may not be perfectly appropriate to model Sudoku to an exact cover problem. in other word, Sudoku board may not be 100% optimal to be "upgraded" to a exact cover. Here is my thought:
Algorithm X is supposed to choose the set of rows that exactly cover the set of cols. A 'perfect' exact cover problem, I think, is that, you do not have any information about the constraints among the rows beforehand -- their constraints are supposed be revealed by algorithm X. So any subsets of rows could be considered by a innocent person as potential solutions, before the matrix is passed to the alogirthm X. That would be a perfect problem to be handled by Algorithm X. But in Sudoko, this is not true, we partially know the constraints among 729 rows -- that is some rows (presenting a common cell) cannot be the part of the solution together, and there will be exactly 81 rows to be selected. That means, Algorithm X, or DLX, will be handling some redundancy it should not handle, which means, when handling larger size Sudoku, the efficiency will not be high.
EDIT, I may be very wrong since I do not know too much about the algorithm

[eleven]

Hi sdk_fan,

though its really strange to write a program, which tries to solve a sudoku using a way, which is more complicated and a lot slower than public ones, without delivering an output, which can manually be followed, and though i am very short of time, ... i could not resist to make a try to mimic your program in the way i scetched above.
In the time i had, i did not manage to fix all the bugs. When i ran it against the first 200 in champagne's list today, it failed for one puzzle with 0 solutions, while the other ones were correct. So i guess its just a minor bug concerning a special property of this puzzle. Maybe i'll fix that, but probably not. I think the questions i had, are answered sufficiently.

Btw you inspired me to another favorite method to solve hardest puzzles on paper without any computer help Instead of guessing a number, making a copy and trying to show a solution/contradiction, until all copies are resolved, i now would select a unit and gusss a full assignment. This would give me say 30 copies (i noticed that there are between 20 and 1000 possible assignments for the 27 units in the puzzles i looked at) of the puzzle with this unit resolved. They would have about newspaper puzzles difficulty, most singles puzzles and a few harder ones. But for 29 of them i would not have to find a solution, but a contradiction. This could be done in a day or two and i am sure its more interesting than to mimic Brian's method on paper. However when i changed the bb_solver to do that, it was 60 to 120% slower, when i selected the smallest and an average size assignment set fo start with.

Now the questions i was interested in were mainly, how big the set of possible solutions per level would become and how strong it is influenced by the selected order of units to add (in your case groups, but for the hardest each group contains of all unsolved cells of a unit).
I dont know an upper limit, because on my 1 GB RAM notebook i had to stop with 4,5 mio solutions. But to find a good order is very important. Since i guess, that orders other than making alternatively a full band and stack until all are resolved, only can be worse, i tried all 36 ways of band/stack combinations (with a fixed order of units within the band/stack). Though all these 199 puzzles could be solved with this 4.5 mio limit, there were big differences in the maximum size, e.g. i saw about 250000 as the minimum and some other orders, which could not make it within the limit.
The bad thing is, that i dont have an idea how to find a good order. Allways to take the band/stack with the least possible assignments in the units is often a bad strategy. I have the suspicion, that no better heuristics can be found, which dont take long to evaluate. So to define the order is a kind of guessing.
My only alternative to avoid heavy memory problems (at least on the notebook) was to use a backtracking method. Try the first order, if it exceeds the 4,5 mio, try the next. (Of course here i can stop, when i am through with all units. All solutions are known then - at least when the bug is fixed). This took about 40 minutes for the 200 puzzles @2,67Gh.

You asked for the data structures:
The solutions are stored in a STL list. When i add a unit, i first make a list of all possible assignments and from that an array of vectors, which contain the possible assignments for a specific pattern of the intersecting (engaging) cells.

Of course you cou avoid any memory problems by doing this depth first. Take the first assignment for the first unit, then the first of the combination with the next assignment, etc, until you have nothing or a solution. And then ... backtrack. All you would need in memory is, to save how to get to the next solution per level. This can be easily done, when all these vector arrays are kept in memory for all levels (units to combine) - you can calculate them, as soon you have defined the unit order. Then you just need a pointer to where you are.
Then i cant see any performance advantage for the breath first method.