Re: Solving puzzles mechanically

Programs which generate, solve, and analyze Sudoku puzzles

Postby Guest » Thu Mar 24, 2005 9:12 am

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
 

Postby milobird » Thu Mar 24, 2005 10:30 am

Yes... What a team!
milobird
 
Posts: 21
Joined: 20 March 2005

Postby Guest » Thu Mar 24, 2005 1:16 pm

anybody fancy starting a puzzle creation group on Yahoo?

http://groups.yahoo.com/search?query=sudoku
Guest
 
Posts: 312
Joined: 25 November 2005

Postby milobird » Fri Mar 25, 2005 5:47 pm

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

Postby Guest » Sat Mar 26, 2005 4:01 am

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
 

Postby Guest » Sat Mar 26, 2005 10:50 am

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
 

Postby Guest » Sat Mar 26, 2005 3:27 pm

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
 

Postby Guest » Sat Mar 26, 2005 10:59 pm

(Guest: What is your name?)

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

Postby Thumbs » Sat Mar 26, 2005 11:42 pm

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:

Postby Thumbs » Sun Mar 27, 2005 12:00 am

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 65
6    5 7
 59 67 3
138  6  7
594781326
726   81
    1 69
 6 8    3
9  6 4 8
     POSSIBLE ENTRIES:
234      47       237      1        2349     8        249      6        5
6        148      123      2349     2349     5        249      7        2489
248      5        9        24       6        7        124      3        1248
1        3        8        249      249      6        459      45       7
5        9        4        7        8        1        3        2        6
7        2        6        3459     3459     39       8        1        49
2348     478      2357     235      1        23       6        9        24
24       6        1257     8        2579     29       12457    45       3
9        17       12357    6        2357     4        1257     8        12


Also, this one:
Code: Select all
     SUDOKU contains:
46 1 8 2
   4761
  19 24
8  5 4  1
    17  4
614893752
  67495
 4 3852
 3   1 4
     POSSIBLE ENTRIES:
4        6        3579     1        35       8        39       2        3579
2359     2589     23589    4        7        6        1        389      3589
357      578      1        9        35       2        4        3678     35678
8        279      2379     5        26       4        369      369      1
2359     259      2359     26       1        7        3689     3689     4
6        1        4        8        9        3        7        5        2
12       28       6        7        4        9        5        138      38
179      4        79       3        8        5        2        1679     679
579      3        5789     26       26       1        89       4        789
Thumbs
 
Posts: 6
Joined: 17 March 2005

Postby Guest » Sun Mar 27, 2005 12:35 am

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
 

Postby Guest » Sun Mar 27, 2005 9:53 am

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
 

Postby Pappocom » Sun Mar 27, 2005 12:53 pm

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

Postby Guest » Sun Mar 27, 2005 4:30 pm

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
 

Postby milobird » Mon Mar 28, 2005 12:44 am

Consider where the number three in column six can be placed.
milobird
 
Posts: 21
Joined: 20 March 2005

PreviousNext

Return to Software

cron