The New Sudoku Players' Forum

[sdk_fan]

Solve Every Sudoku without Guessing. Your comment are welcome. I did some promotion for this forum.

www.fileupyours.com/files/314015/Sudoku_without_Guessing.pdf {PDF}

Thanks

[SudoQ]

Solve Every Sudoku without Guessing. Your comment are welcome.

Short question:
Is the application using the method you describe and you refer to available?

/SudoQ

[sdk_fan]

Is the application using the method you describe and you refer to available?
/SudoQ

The program is running on my computer. I do not plan to publish my python program, which is quite messy and not "pythonic". But I hope my algorithm description in that file is concise enough so everyone can have his/her own implementation, in their favourite languages. Hopefully, there will be major improvement to the algorithm /data structure, for example to address the memory explosion problem, and explore the parallelism

One thing I didn't have time to do but I think doable is to add an explanation feature.

[JasonLion]

Several algorithms are already known for solving any puzzle without guessing or trial and error. Consider the following: match the clues against the set of all possible solution grids. The solution grid that contains all of the clues is the solution. While highly impractical, there certainly isn't any guessing or trial and error involved. Solving methods like this one are considered brute force algorithms. Your approach also looks like a brute force approach, though I am not completely certain of that.

[sdk_fan]

Consider the following: match the clues against the set of all possible solution grids...

I do not agree this is really solving. This is checking a database. You need to have the database at the first place.

I won't say my method is a brute force, because it never need to assume any candidate. And all solutions (if there are multiple solutions) are generated simultaneously. To achieve that, you need to consider all candidates in the middle of computation, until a piece of evidence proves that they are invalid.

But I agree that there is a relationship between this algorithm and systematic search.

[sdk_fan]

Several algorithms are already known for solving any puzzle without guessing or trial and error.

That is interesting, may I know where I can find them?
Thank you,

[JasonLion]

This kind of discussion requires clearer definitions of terms. You dismiss my first proposal because it is simply a "database". Yet, your approach involves enumerations of the possible positions of cogs, which look like "databases" to me. What is the logical difference between those two things?

Some other approaches that don't involve guessing: multi-digit POM, whips, forcing nets, and tabling.

[sdk_fan]

Yet, your approach involves enumerations of the possible positions of cogs, which look like "databases" to me. What is the logical difference between those two things?

The difference is: your proposal requires pre-existing "all solution grids", while mine computes whatever "database" that is necessary on the fly. Its size grows and shrinks and eventually becomes the exact set of solutions to the board. I think there is a big difference.

For one thing, you say your proposal is highly impractical, while mine yields a workable program.

[eleven]

sdk_fan, to your information:

Brian Turner's backtracking method can be described this way:

Code: Select all

0.  Set the level to 0.
1.  Solve all singles and locked candidates
2a. If the puzzle is solved, stop
2b. If the level is 0 and the puzzle has no solution (a contradiction),
    there is no solution, stop
2c. If the puzzle is still unsolved, continue with 3.
2d. If the level is greater 0 and the puzzle has no solution,
    decrease the level and remove the candidate set in the higher level
    If this leaves a single, continue with 1.
3.  Find the first cell with the minimum number of candidates.
    Copy the grid (new "node"), increase the level,
    set the first candidate in this cell, continue with 1.

Brian made a very fast implementation in C++ in his bb_solver (bitbased, using lookup tables). It solves the 14258 extremely hard puzzles in champagne's list in 5 seconds.

[coloin]

Well...it might be all down to semantics.

"Guessing" has a logical element which you cant deny. Trivially even the simplist [single] insertion of a cell can be made assumptive. [e.g it cant be x because it has to be y] The only difference is the length of the process by which an insertion or elimination can be made.

I havnt looked at your program but i could ask how it decides where to start in the process.
If it is able to solve without an assumptive process can you ascribe a "rating" as to how quick/how tricky/length of path etc

This might be a very useful by-product of your software.

Of course it would have to be isomorph invarient.

Switching off uniqueness as a method is also aesthetically pleasing to me !!!!!

Regards

C

[JasonLion]

It is very straightforward, though slow, to enumerate all possible solution grids on the fly. I see no logical difference between doing so and what you propose. In one sense I am simply extending the cog size to include all cells on the board. Certainly there is a practical difference of several orders of magnitude in the CPU time required. I didn't notice you mentioning CPU time requirements as a criteria before now. Previously you only mentioned avoiding guessing and avoiding trial and error. That is why I said you need to be precise in listing your definition of terms. What are your exact criteria for preferring one approach over another?

[sdk_fan]

Brian made a very fast implementation in C++ in his bb_solver (bitbased, using lookup tables). It solves the 14258 extremely hard puzzles in champagne's list in 5 seconds.

Wow, that is very great speed, many orders of magnitude faster than my implementation! But the main point here is that I am not using backtracking. But I will use this information in my revision of the paper.

My solver solved about 99.5% of those puzzles (in days). At the end of my paper I discuss the shortcoming of my approach, which is memory explosion, which prevents my 32-bit machine solve the remaining 0.5%. (unfortunately, 2GB is just a little to short). But I also give out the solutions there.

Thank you very much for your effort in finding very hard puzzles!

Here is the output of the running of "discrepancy"

Code: Select all

>>> solve(tests['discrepancy'])
Attacking..
Starting with...
col:  1 2 3 4 5 6 7 8 9
-----------------------
r 1 | _ _ _ _ _ _ _ 3 9
r 2 | _ _ _ _ _ 1 _ _ 5
r 3 | _ _ 3 _ 5 _ 8 _ _
r 4 | _ _ 8 _ 9 _ _ _ 6
r 5 | _ 7 _ _ _ 2 _ _ _
r 6 | 1 _ _ 4 _ _ _ _ _
r 7 | _ _ 9 _ 8 _ _ 5 _
r 8 | _ 2 _ _ _ _ 6 _ _
r 9 | 4 _ _ 7 _ _ _ _ _

End with...
col:  1 2 3 4 5 6 7 8 9
-----------------------
r 1 | _ _ _ _ _ _ _ 3 9
r 2 | _ _ _ _ _ 1 _ _ 5
r 3 | _ _ 3 _ 5 _ 8 _ _
r 4 | _ _ 8 _ 9 _ _ _ 6
r 5 | _ 7 _ _ _ 2 _ _ _
r 6 | 1 _ _ 4 _ _ _ _ _
r 7 | _ _ 9 _ 8 _ _ 5 _
r 8 | _ 2 _ _ _ _ 6 _ _
r 9 | 4 _ _ 7 _ _ _ _ _

Not solved in the pre-processing. Now Using Cogwheel Method
col:     1       2       3       4       5       6       7       8       9
--------------------------------------------------------------------------
r 1  82567|  81456| 124567|    826|   2467|   8467|   1247| D    3| D    9|
--------------------------------------------------------------------------
r 2  89267|   8946|   2467|  89236|  23467| D    1|    247|   2467| D    5|
--------------------------------------------------------------------------
r 3   9267|   1469| D    3|    926| D    5|   9467| D    8|  12467|   1247|
--------------------------------------------------------------------------
r 4    235|    345| D    8|    135| D    9|    357| 123457|   1247| D    6|
--------------------------------------------------------------------------
r 5   9356| D    7|    456|  81356|    136| D    2|  13459|   8149|   8134|
--------------------------------------------------------------------------
r 6 D    1|   9356|    256| D    4|    367|  83567|  92357|   8927|   8237|
--------------------------------------------------------------------------
r 7    367|    136| D    9|   1236| D    8|    346|  12347| D    5|  12347|
--------------------------------------------------------------------------
r 8   8357| D    2|    157|   1359|    134|   9345| D    6|  81497|  81347|
--------------------------------------------------------------------------
r 9 D    4|  81356|    156| D    7|   1236|   9356|   1239|   8129|   8123|
--------------------------------------------------------------------------
Tree built for group [(6, 3), (4, 2), (4, 1), (5, 3), (6, 2), (5, 1)]
Tree built for group [(6, 3), (5, 3), (8, 3), (9, 3), (2, 3), (1, 3)]
0:14:23.518 spent, 20 leaves (paths), 2 groups engaged.
Tree built for group [(8, 3), (9, 3), (7, 1), (7, 2), (8, 1), (9, 2)]
0:00:00.026 spent, 108 leaves (paths), 3 groups engaged.
Tree built for group [(4, 2), (6, 2), (7, 2), (9, 2), (2, 2), (3, 2), (1, 2)]
0:00:00.040 spent, 198 leaves (paths), 4 groups engaged.
Tree built for group [(4, 1), (5, 1), (7, 1), (8, 1), (3, 1), (2, 1), (1, 1)]
0:00:00.043 spent, 382 leaves (paths), 5 groups engaged.
Tree built for group [(4, 2), (4, 1), (4, 8), (4, 6), (4, 4), (4, 7)]
0:00:00.056 spent, 886 leaves (paths), 6 groups engaged.
Tree built for group [(4, 6), (4, 4), (5, 5), (6, 5), (5, 4), (6, 6)]
0:00:00.246 spent, 3986 leaves (paths), 7 groups engaged.
Tree built for group [(5, 3), (5, 1), (5, 5), (5, 4), (5, 8), (5, 9), (5, 7)]
0:00:00.458 spent, 7770 leaves (paths), 8 groups engaged.
Tree built for group [(6, 3), (6, 2), (6, 5), (6, 6), (6, 8), (6, 9), (6, 7)]
0:00:00.797 spent, 16786 leaves (paths), 9 groups engaged.
Tree built for group [(5, 5), (6, 5), (8, 5), (1, 5), (9, 5), (2, 5)]
0:00:03.467 spent, 31696 leaves (paths), 10 groups engaged.
Tree built for group [(2, 3), (2, 2), (2, 1), (2, 5), (2, 7), (2, 4), (2, 8)]
0:00:03.266 spent, 40224 leaves (paths), 11 groups engaged.
Tree built for group [(4, 8), (5, 8), (6, 8), (2, 8), (9, 8), (3, 8), (8, 8)]
0:00:02.913 spent, 42622 leaves (paths), 12 groups engaged.
Tree built for group [(8, 3), (8, 1), (8, 5), (8, 8), (8, 6), (8, 4), (8, 9)]
0:00:03.860 spent, 36784 leaves (paths), 13 groups engaged.
Tree built for group [(4, 4), (5, 4), (2, 4), (8, 4), (3, 4), (1, 4), (7, 4)]
0:00:01.781 spent, 19900 leaves (paths), 14 groups engaged.
Tree built for group [(3, 2), (3, 1), (3, 8), (3, 4), (3, 9), (3, 6)]
0:00:02.125 spent, 14444 leaves (paths), 15 groups engaged.
Tree built for group [(1, 3), (1, 2), (1, 1), (1, 5), (1, 4), (1, 7), (1, 6)]
0:00:00.461 spent, 6376 leaves (paths), 16 groups engaged.
Tree built for group [(4, 6), (6, 6), (8, 6), (3, 6), (1, 6), (7, 6), (9, 6)]
0:00:00.345 spent, 3580 leaves (paths), 17 groups engaged.
Tree built for group [(7, 1), (7, 2), (7, 4), (7, 6), (7, 7), (7, 9)]
0:00:00.370 spent, 1007 leaves (paths), 18 groups engaged.
Tree built for group [(5, 9), (6, 9), (8, 9), (3, 9), (7, 9), (9, 9)]
0:00:00.135 spent, 161 leaves (paths), 19 groups engaged.
Tree built for group [(9, 3), (9, 2), (9, 5), (9, 8), (9, 6), (9, 9), (9, 7)]
0:00:00.078 spent, 33 leaves (paths), 20 groups engaged.
Tree built for group [(8, 5), (9, 5), (8, 6), (8, 4), (7, 4), (7, 6), (9, 6)]
0:00:00.041 spent, 1 leaves (paths), 21 groups engaged.
Tree built for group [(9, 8), (8, 8), (8, 9), (7, 7), (7, 9), (9, 9), (9, 7)]
0:00:00.137 spent, 1 leaves (paths), 22 groups engaged.
Tree built for group [(1, 5), (2, 5), (2, 4), (3, 4), (1, 4), (3, 6), (1, 6)]
0:00:00.046 spent, 1 leaves (paths), 23 groups engaged.
Tree built for group [(2, 3), (1, 3), (2, 2), (3, 2), (1, 2), (3, 1), (2, 1), (1, 1)]
0:00:00.130 spent, 1 leaves (paths), 24 groups engaged.
Tree built for group [(4, 8), (4, 7), (5, 8), (5, 9), (5, 7), (6, 8), (6, 9), (6, 7)]
0:00:00.130 spent, 1 leaves (paths), 25 groups engaged.
Tree built for group [(2, 7), (2, 8), (3, 8), (3, 9), (1, 7)]
0:00:00.020 spent, 1 leaves (paths), 26 groups engaged.
Tree built for group [(4, 7), (5, 7), (6, 7), (2, 7), (1, 7), (7, 7), (9, 7)]
0:00:00.060 spent, 1 leaves (paths), 27 groups engaged.
The puzzle has been decided. Time spent in the cogwheel method: 0:00:22.286000
There are 1 solutions.
Solution #1:
7 5 1 8 4 6 2 3 9
8 9 2 3 7 1 4 6 5
6 4 3 2 5 9 8 7 1
2 3 8 1 9 7 5 4 6
9 7 4 5 6 2 3 1 8
1 6 5 4 3 8 9 2 7
3 1 9 6 8 4 7 5 2
5 2 7 9 1 3 6 8 4
4 8 6 7 2 5 1 9 3
Garbage: 1051796

[eleven]

But the main point here is that I am not using backtracking.

If i understood right,what you are doing, the main difference to Brian's method is, that you are doing a breadth first and Brian a depth first search in your trees. This does not have any impact to questions like "is this or that one a guessing method ?" Its just a design decision, which can have impact to the peformance.

[sdk_fan]

I havnt looked at your program but i could ask how it decides where to start in the process.....

If it is able to solve without an assumptive process can you ascribe a "rating" as to how quick/how tricky/length of path etc. Of course it would have to be isomorph invarient.

Hi, Coloin, Your questions are difficult to answer but I think to the point, because I was thinking about rating!

For the first part: the process.. If you read section 3 (2 pages at most) of that paper, you can understand the process and your comment will be appreciated.

For the 2nd part.
While I can say all solutions are bound to be found, there are many ways to find them. The main problem is that the sequence to combine 27 constraints is not decided. I use a heuristic to find a sequence that encourages early formation of cause-effect-back-to-cause circles among these constraints; at this stage I cannot guarantee this heuristics will invariantly find the isomorphic sequence on isomorphic invariants. (But I also do not see why it could behave differently). Nevertheless, even if the heuristic could be proved to work invariantly, it does not guaranteed to find the true optimal sequence for a particular puzzle. So my intuition says 'rating' is rather a subjective thing so I gave up the thought.

[sdk_fan]

If i understood right,what you are doing, the main difference to Brian's method is, that you are doing a breadth first and Brian a depth first search in your trees.

Hi, eleven, I am not thinking I am searching. A candidate is removed only because an evidence says it can't be there. But before that evidence (a constraint) is considered, that candidate should remain there. Here evidence is not gained by trying the candidate out first; but by checking the current constraint under consideration.

There is a tree involved, which is never complete (for searching purpose), until the last constraint (a row, a col, or a block) is considered. But at that moment the solutions are already decided, which is the tree itself.

There is no hint of breadth first process in my program. All traversing is done in depth first manner.