The New Sudoku Players' Forum

[simes]

There must be a third algrothim. Any ideas?

This is where it gets complicated, and where my own program (also in Delphi) starts "guessing". You have to look for what other information you can glean about number placement - somtimes you can determine which row or column a number must be in without being able to identify the exact cell. This in turn can eliminate cells in other blocks leaving only a single possibility. For an example see the thread http://forum.enjoysudoku.com/viewtopic.php?t=36 and see how the position of the 5 in block 1 is determined.

[Guest]

Yes, there is a 'third' heuristic but it doesn't help much with the really difficult puzzles. It's the 'identical pairs' test. If you have exactly two cells in a row, colum or box with the same pair of values xy then either one must be x and the other y. You don't yet know which is which but you do know that no other cell in the row/column/box can contain either x or y, which can therefore be eliminated. This often release another iteration of the eliminate and/or unique value heuristics.

The catch-all algorithm you're looking for is the 'brute force' search of the pruned search tree which simply searches all feasible configurations of the grid until it finds a correct solution.

You can see this in action in my application at www.mckernan.it/downloads/solver.zip
First click the 'solve' button to run the three heuristics. If you don't have a solution then click the [alphabeta] button and the brute force algorithm will find the solution. The next version will integrate the two algorithms.

Try Times 83, which is quite hard

8 7 9
2 7 4
7 1 5
3
7 2 1 6 4
6
8 4 3
9 8 2
4 5 7

AMcK

[simes]

Hey! where'd the original question go?

[Pappocom]

My apologies to all readers of this thread, and to howshaw himself. After moving the original question into this thread, I accidentally deleted it. I have emailed howshaw to explain and apologize.

- Wayne

[howshaw]

My program now applies the following algrothim...
1) Look at each cell in the gird and if any are empty then abort the solution.
2) Scan each cell in the gird in order and if a cell contains a single digit then cross that digit out of all the other cells in its row, column and box. Repeat steps 1&2 until the entire grid is scanned without the grid changing. This follows the basic rule of the game.
3) Scan each row and look for a cell that contains a digit that is unique in the row. For example, in a row with three unknown cells, with [1,9], [2,9] and [1,2,6] in them, the 6 is unique. Set the cell to the unique digit (in this case the cell with [1,2,6] in it is set to contain only 6, and then jump back to step 1.
4) Do the step 3 scan again, but this time by columns.
5) Do the step 3 scan again, but this time by boxes.
6) Scan each row and if two cells, each with the same two digits in them are found, then remove those two digits from all the other cells in the row. For example in a row with [1,4], [1,4,5], [1,7,8], [1,4], [4,9] and [2,9] the pair of [1,4] would be detected and the row would be changed to [1,4], [5], [7,8], [1,4], [9] and [2,9]. If any changes are made to the grid in doing this then jump back to step 1.
7) Do the step 6 scan again, but this time by columns.
8) Do the step 6 scan again, but this time by boxes.
9) Finally guess. It is not totally random about its guessing. It tries to find a cell with the fewest number of possible digits in it, in a row, column and box that is the most complete. It sets this cell to the smallest of the allowed digits and recurses back to step 1 (it does not allow nested recursion). If the guess results in a grid with an empty cell then the grid is restored to its state before the guess and the program moves on.

Guessing can be turned off, and without it this method does not lead to a solution for the Times 1st March or 4th March. In fact only one cell is found in the 1st March puzzle. The program produces a log what what it tried and how the cells changed, its too much to post, but I can email it if someone wants to send me a message.

It would be possible to perform the step 6 scan but looking for three occurences of the same triple, four occurences of the same quad. etc, but I have tried it on the 1st March puzzle and it does not seem to help.
The big question is... How did anybody solve the Times 1st March puzzle? What I need is the exact list of steps, whether by hand or software. If there really is a purely logical solution (and I STILL have no evidence that there is) then what is the big secret.

[simes]

Is March 1st number 80? If yes, is that the one you really meant? (It seems a mite simple)

OK, here's a list of steps - coords in (x,y)
(3, 8) = 4
(3, 9) = 3
(4, 8) = 7
(8, 1) = 2
(2, 9) = 6
(3, 1) = 5
(3, 2) = 1
(3, 5) = 2
(4, 2) = 3
(5, 1) = 9
(5, 2) = 8
(5, 8) = 6
(6, 2) = 4
(6, 8) = 8
(7, 1) = 4
(7, 2) = 6
(7, 8) = 2
(7, 9) = 5
(8, 9) = 7
(9, 3) = 7
(9, 7) = 6
(1, 3) = 6
(1, 7) = 7
(2, 1) = 3
(2, 5) = 5
(5, 9) = 1
(7, 5) = 3
(9, 5) = 4
(9, 6) = 5
(1, 5) = 1
(2, 4) = 8
(2, 6) = 9
(4, 6) = 1
(5, 3) = 5
(5, 5) = 7
(5, 7) = 3
(6, 3) = 1
(6, 6) = 3
(6, 7) = 5
(8, 5) = 6
(8, 6) = 8
(9, 4) = 2
(1, 4) = 3
(1, 6) = 4
(4, 3) = 2
(4, 4) = 5
(4, 7) = 9
(6, 4) = 6
(8, 4) = 1

In each case, the value is the only possible value for the cell.

[malcolmr]

There is definitely a logical solution to all puzzles published in the Times so far. My current software does not yet implement all agorithms for solution but the next release (currently under test) will. There is a fourth way of looking at the values which is a where a value for a box must be in a particular unique row or column. The difficulty comes in how to handle this situation when found. I think I have got it right but will carry on testing until the end of this weekend before releasing software including it. So far I have not found an 'insoluble by logic' puzzle, even though I thought they existed at first. 'Insoluble by software' depends on the software. My software allows guesses but will NEVER use them for auto solving. It would be possible to use a pure quesswork solver to come up with a valid solution. This is not a good idea. One of these days it will have to work through every possible combination to solve the puzzle and this could take a very long time ( I understand possible combinations are 81 x 80 x 79 x ......3 x 2 x 1, work it out for yourself).

[Guest]

I started solving Sudoku puzzles manually, then wrote a program that emulated my manual technique. In no case did I ever consider a guessing method, I always solved by logic - whether manually or by software.
I now have a program which solves every puzzle published to date.
Incidentally, I have never found a duplicate solution using logic.

My algorithm uses an initial Sudoku 9x9 array, and a "Poss" 9x9 array initially containing 123456789 in each cell. The objective is to reduce the possible solutions in each Poss cell to one digit instead of all 9.

Step 1
Using the Sudoku array as source I remove each element from Poss that matches by row, column and block. I leave single elements in the Poss array, however. I refresh the Sudoku array with any single element in the Poss array.

In simple terms, I look at the first Sudoku cell. If empty, I ask which digits can possibly occupy it once the entries in the same row, column, and block are taken into account? I repeat for all cells. Any cell that now has only one digit in it can be written onto the Sudoku sheet immediately.

Step 2
Now I process the Poss array, looking for a unique element (1-9) in each row, and set that cell to just that element. I repeat for each column and 3x3 block. I update the Sudoku array with any single element in the Poss array.

In simple terms, if I look across a row containing my possible entries, and I find a digit that occurs only once, then that digit can be placed into the corresponding Sudoku cell immediately. The Poss cell can be set to just that digit, too.

I reiterate steps 1 and 2 until the Poss array and the Sudoku array contain 9x9 single elements.

Now I need a REALLY tough one to test the program, since it has not failed yet.

[simes]

Thumbs, I don't think your two steps are enough. Consider yesterdays puzzle (No 94)

Code: Select all

8..7.....
.....4.2.
...2..17.
..6.2..9.
1..4.5..6
.2..9.3..
.31..2...
.4.3.....
.....8..3


I think repeating the two steps leaves it looking like:

Code: Select all

8.27...3.
.....4.2.
...2..17.
.8612..9.
1..4.5286
.2.8963.1
.31..2...
.483....2
2....8..3


but what's the next move?

I'd go for a 7 in the centre cell, but I don't think your logic would find it. (Or have I missed something obvious?)

[Guest]

Hi. I've written a program too (a macro in Excel of all things!) which seems to solve all but one puzzle I've thrown at it (A "Diabolical" from the Torygraph. I believe this one requires T&E). I've implemented one test that no one else has mentioned and can think of one other, which I've never needed so haven't coded...

Firstly the "2 occurences of a double possibility" test mentioned above (e.g. Two cells in a row can contain only 2 & 3, but you don't know which is which) can be extrapolated to "N occurences of an N-ple possibility". In other words if 3 cells could be 2, 3 & 4, but you don't know which is which, no other cells in that row/col/box can be 2, 3 or 4. This got me out of a fix with a Telegraph puzzle once. Obviously the higher N gets, the less use this becomes.

The test I haven't implemented is an extrapolation of "if X is only possible in one square, then that square must be X". This can be expanded to "if two digits only appear in two cells, both cells can only be one of those two digits", and so on for N digits. e.g. If the possibilities for two cells in a row are 1279 and 2347, and 2 and 7 occur no where else on the row, then both cells can only be 2 or 7. This may help by eliminating 1, 9, 3 & 4 from the relevent cells. Again, this was handy once when doing a puzzle, but I can't quite face coding it! I have a nagging feeling that the other algorithms people have mentioned will always eliminate this posibility - but I have no way to prove or disprove this.

BTW Simes - thanks for your wise words on that other topic. I thought of responding again, but decided that your post was a nice way to leave it. :o)

[simes]

But I take it you still disagree?

For some reason, Wayne has locked that thread ... but we could always continue in a new one ;-)

[Guest]

Well yes, Obviously I disagree, but my head was starting to bleed, and it wasn't doing the wall any good either. You can lead a horse to water, but it'll still gather moss.

[simes]

Okley dokley.

Well, when you find a puzzle that is solvable logically, and has an alternative solution too, we can discuss it again.

[Guest]

OK, I'll do that.

In the mean time, and back on topic, my program has let me down! It won't solve today's puzzle (No 95). I couldn't do it manually either, but that's another issue - has any one tried it with their program?

[simes]

Mine will solve it... but only by T&E. It has the simpler logic built into it, but not the complex interactions.. I'm still waiting to find out how these work myself!