## Re: Solving puzzles mechanically

Programs which generate, solve, and analyze Sudoku puzzles
Milo, Simes (and Wayne),

I think I may have provoked this by writing a fairly detailed answer to Milo's question, which Wayne has removed. On reflection, I'm happy to concur with Wayne's point that this was a bit unreasonable. I agree with Simes though, that other people's discussions can be interesting without needing to butt in, though I can't normally help myself :o). Equally, although we are talking about using computers, this design process is also a very effective way to distill the nature of the puzzle, and I have certainly gained great insight into how to solve the puzzle by hand too. This is of course the geek in me, but I'm sure it will have helped others too.

Finally, as it got deleted, I'd like to re-iterate my return of thanks to Milo - It was a fun.
Guest

Yes... What a team!
milobird

Posts: 21
Joined: 20 March 2005

anybody fancy starting a puzzle creation group on Yahoo?

http://groups.yahoo.com/search?query=sudoku
Guest

Posts: 312
Joined: 25 November 2005

Good idea.

I have started a new Google group...

Please join this group to discuss mathematical aspects of Sudoku which are beyond the scope of these forums.

EDIT: New forum is here:
http://www.setbb.com/phpbb/?mforum=sudoku
Last edited by milobird on Thu Apr 07, 2005 7:47 am, edited 1 time in total.
milobird

Posts: 21
Joined: 20 March 2005

In the Google group (mentioned above), Thumbs stated the following solution technique:

Code: Select all
`Scan a row (or column) to discover if only 2 or 3 cells contain the same possible. If the 2 or 3 cells are within the same box, remove all possibles from the remaining 6 cells in that block. Point of clarification - if there are only 2 cells, they must both be in the same box. If there are only 3 cells they must all be within the same box.`

I am repeating it here, as it is fundamentally important.

Using this technique has enabled my Su Doku program to solve by pure logic ALL puzzles I have so far submitted to it with absolutely no trial and error.
At long last I can now solve the 'fiendish' puzzles.
Guest

Hi Anthony,

This doesn't really make any sense does it? Perhaps it's just the way it's written, but it sounds like he's talking about single digits ("3 cells contain the same possible"), but if this is the case, then by definition that digit won't be a possible in the other cells (if it's only in those three, that obviously it's not in the other six), so what is there to remove?

If that's not what he means, and is in fact talking about 2 possibles in 2 cells, 3 in 3 cells, etc., then this is covered neatly by Milo's solution, as are much more complex possibilities..

Either way, only dealing with 2, or 3 cells/possibilities may solve most puzzles, but I don't think it can't solve all if you don't go to 4. Likewise, you must test both for cells with exclusive digit-possiblities and digits with exclusive cell-possibilities. Either that, or go up to N=8 for just one of these tests.
Guest

Hi, sorry, I've re-read it and think I know what he means now, but don't forget that the reverse must also be tested - i.e. possibles in a box occuring only at the intersection of a particular row or column. It's easiest to think of (and code) Rows, Columns and Boxes as "Units", and then check for intersections, that way you will catch everything.
Guest

You say "don't forget that the reverse must also be tested".

Yes, I did remember it and it's now incorporated into my Su Doku solver program (written in PureBasic).

My program now seems to solve almost every Su Doku puzzle I throw at it. The ONLY one giving it any problem is puzzle number 4 (rated as very hard) at www.thetimes.co.uk as it needs trial and error to complete it. Has anyone solved this puzzle purely logically? If so, how?

I am on the lookout for really difficult puzzles to help me to improve my program so that I can eliminate trial and error. Has anyone got any?
Guest

### Column and box technique

IJ wrote:Hi Anthony,

This doesn't really make any sense does it? Perhaps it's just the way it's written, but it sounds like he's talking about single digits ("3 cells contain the same possible"), but if this is the case, then by definition that digit won't be a possible in the other cells (if it's only in those three, that obviously it's not in the other six), so what is there to remove?

If you pencil in to a cell all of the possible values that can go into it, then repeat for all empty cells, then you are ready to interpret the rule.

Scan a row. If the same possible appears in two cells, check if those two cells are within the same block. If so, you can eliminate that possible from the remaining 6 cells in that block.

Example, showing block 1 and column 1

12 124 567
13 234 1567
45 1568 9
678
467
9
68
78
46

Since 1 can only appear in the top two positions of column 1 we can eliminate the 1's in the remaining 6 cells in the top box.

Same applies for this case, where the 1 is still restricted to the first column of the box, but in the first and third position.

12 124 567
23 234 1567
145 1568 9
678
467
9
68
78
46

Likewise if it occurred in the first second and third positions.

I trust that clarifies it?
Thumbs

Posts: 6
Joined: 17 March 2005

### Difficult problems to test against:

Anthony Jordan wrote:I am on the lookout for really difficult puzzles to help me to improve my program so that I can eliminate trial and error. Has anyone got any?

Try this one:
Code: Select all
`     SUDOKU contains:   1 8 656    5 7 59 67 3138  6  7594781326726   81    1 69 6 8    39  6 4 8     POSSIBLE ENTRIES:234      47       237      1        2349     8        249      6        56        148      123      2349     2349     5        249      7        2489248      5        9        24       6        7        124      3        12481        3        8        249      249      6        459      45       75        9        4        7        8        1        3        2        67        2        6        3459     3459     39       8        1        492348     478      2357     235      1        23       6        9        2424       6        1257     8        2579     29       12457    45       39        17       12357    6        2357     4        1257     8        12`

Also, this one:
Code: Select all
`     SUDOKU contains:46 1 8 2   4761  19 248  5 4  1    17  4614893752  67495 4 3852 3   1 4     POSSIBLE ENTRIES:4        6        3579     1        35       8        39       2        35792359     2589     23589    4        7        6        1        389      3589357      578      1        9        35       2        4        3678     356788        279      2379     5        26       4        369      369      12359     259      2359     26       1        7        3689     3689     46        1        4        8        9        3        7        5        212       28       6        7        4        9        5        138      38179      4        79       3        8        5        2        1679     679579      3        5789     26       26       1        89       4        789`
Thumbs

Posts: 6
Joined: 17 March 2005

Thank you Thumbs for the two puzzles.

But ...

My program solved them easily, each in under one second and without using any trial and error.

Have you any more difficult?
Guest

This one is pretty nasty (Friday 18th March). It needs analysis of subsets of possibilities (as per Milo's rules 2 and 3)

http://www.timesonline.co.uk/article/0,,18209-1529640,00.html

I've also been seriously struggling with the "Very hard" one on the web site for some time now, but I doubt it needs Trial and Error - Wayne is pretty adamant that all his puzzles do not, and haas always been right so far. Perhaps if he reads this he could comment (please no more than yes it is possible, or - gasp - no it isn't, as I really want to complete it without any hints, even though it may take me weeks!
Guest

Hi IJ. Yes, just to confirm that the Very Hard puzzle (like all Pappocom puzzles) has just one solution and is solveable using logic alone.

I like your attitude. Don't let it beat you! (but take your time)

- Wayne
Pappocom

Posts: 599
Joined: 05 March 2005

My Su Doku program solved the puzzle of Friday March 18 fairly easily using pure logic.
However, it fails to solve the 'Very Hard' website puzzle without trial and error. Below shows how far my program reached using pure logic. Can anyone give me clues to help me to proceed further?

Su Doku Solution Logfile

Top-left and bottom-right cells are at (0,0) and (8,8)

Times Website Puzzle 4 [43825] Very Hard
SolvePuzzle(12)
Horizontal Bands
(0,8) = 5
Vertical Bands
(0,4) = 3
(0,5) = 4
Unique Fit
(3,8) = 8
Count Fits (columns)
(0,2) = 2
Count Fits (blocks)
(5,5) = 9
Count Fits (rows)
(3,0) = 9
Count Fits (columns)
(5,1) = 5
Count Fits (blocks)
(4,1) = 2
Horizontal Bands
(3,1) = 4
Single Row (boxes)
(6,2) from 368 to 68
Single Column (boxes)
(4,2) from 367 to 36
(4,6) from 13467 to 1346
(4,7) from 13467 to 1346
Single Box (columns)
(3,7) from 137 to 17
(4,6) from 1346 to 146
(4,7) from 1346 to 146
------
------
Unsolved

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

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

8 2 . 5 . . . . .
. . . . . . . . 5
5 3 4 8 9 . 7 1 .
Guest

Consider where the number three in column six can be placed.
milobird

Posts: 21
Joined: 20 March 2005

PreviousNext