
View previous topic :: View next topic 
Author 
Message 
 dagojr
 Joined: 26 Jan 2007  Posts: 1  :   Items 

Posted: Fri Jan 26, 2007 5:56 pm Post subject: Logical solution to #27 


I was looking at "illogical" puzzle #27 on Sudoku Solver's website. These are sudoku that the online solver cannot solve with its current code without guessing. However, I think I've found a simple and logical way to finish this one.
Here is the original puzzle:
Code: 
4 5   2 9
 2 
2 1   7 3
7  1 9  5
3   1
4  5 2  3
7 8   6 5
 7 
9 1   7 4

The program can solve this puzzle up to here:
Code: 
4 5   2 9
 2 
2 1   7 3
2 7  1 3 9  5 4
3 5   2 1
1 4  5 2  3 7
7 8 2   6 5
5 4  7  2
9 1  2  7 4

I do not know the name of this technique, or if there even is a name for it, but it's pretty easy to understand. The key squares are D1, D9, F2, and F8.
Looking at the solution grid, we see that 68 is possible in both D1 and D9. 69 is possible in F2, and 89 is possible in F8.
It is impossible for D1 to be 6 and for D9 to be 8, because this would force two 9s from F2 and F8, which share the same row. Therefore, we know that D1 must be 8 and D9 must be 6. The solver has no problem completing the rest of the puzzle from here.
This is a very specific instance, and I don't know how to generalize it. :/ 

Back to top 


 coloin
 Joined: 05 May 2005  Posts: 97  :   Items 

Posted: Sun Jan 28, 2007 12:09 am Post subject: 


Well I dont go in for solving but with the help of sudoku explainer 1.2 this is what it said !
The notation is the opoosite to yours !
Code:  XYWing
The three cells B6, A4 and H6 form an XYWing pattern on the value 8. Regardless of the correct value of the cell B6 (6 or 9), one of the two cells A4 or H6 will have the value 8 as its only remaining possible value. It follows that either the cell A4 or the cell H6 must contain the value 8.
Other occurances of the value 8 can therefore be removed from any cells sharing a row, column or block with both A4 and H6.
XYWing
The three cells H6, I4 and B6 form an XYWing pattern on the value 6. Regardless of the correct value of the cell H6 (8 or 9), one of the two cells I4 or B6 will have the value 6 as its only remaining possible value. It follows that either the cell I4 or the cell B6 must contain the value 6.
Other occurances of the value 6 can therefore be removed from any cells sharing a row, column or block with both I4 and B6. 
There you go  I didnt even know what an XY wing was ...until now !
On the other hand it could be this
Code:  Forcing Chain
If we assume that I4 does not contain the value 6, it follows, through a Forcing Chain, that I4 must contain the value 6. Therefore we can conclude that I4 contains the value 6.
The Forcing Chain consists of a chain of implications based on simple rules. The details of the Forcing Chain are given below.
Details of the Forcing Chain: (1) If I4 does not contain the value 6, then I4 must contain the value 8 (only remaining possible value in the cell) (2) If I4 contains the value 8, then H6 cannot contain the value 8 (the value can occur only once in the block) (3) If H6 does not contain the value 8, then H6 must contain the value 9 (only remaining possible value in the cell) (4) If H6 contains the value 9, then B6 cannot contain the value 9 (the value can occur only once in the row) (5) If B6 does not contain the value 9, then B6 must contain the value 6 (only remaining possible value in the cell) (6) If B6 contains the value 6, then A4 cannot contain the value 6 (the value can occur only once in the block) (7) If A4 does not contain the value 6, then I4 must contain the value 6 (only remaining possible position in the row) 
Take your pick  there is more than one way of solving these hard puzzles
Try sudoku explainer  it shows all the above very clearly
C 

Back to top 


 Phoxtrot
 Joined: 11 Jul 2007  Posts: 2  :   Items 

Posted: Wed Jul 11, 2007 11:32 am Post subject: Illogical #13 


Hello,
I have had about the same idea as you and made a logical sudoku solver too
I checked my program against the 18 first illogical sudokus you posted.
I deactivated my postulate and my guess algorithms for that purpose.
(I make a distinction between the 2: In postulate, i try a value in a square but the only situation where I consider I have learned something is if it leads me to an invalid grid. In guess algorithm, I do kind of a depth first search, trying values along the way until I get a solution.)
From the 18 first sudokus, I was only able to solve the 13th under those conditions. Only 2 non trivial algorithms were used:
TupleGreed5:
Screenshot of the grid at before algo is used:
(Not allowed to post links, so skipping around the limitation:the screenshot is on imageshack, tag sudoku)
DEBUG  (su1.algorithm.TupleGreed) Tuple(5): [1,8][1,7][1,6][1,4][1,1] union:2 5 6 8 9
In the 5 squares noted above ([row,column], top left is [0,0]), only the values 25689 are allowed; since the are 5 such squares in that line, the other squares in that line cannot have any of those values.
Note: there is a dual algorithm: You could also say that value 347 are only allowed to 3 squares on that lines. Which implies that those 3 squares must have one of these values. I didn't program that algorithm since it will solve the same situations as its dual... (with a different number of involved squares)
BlockToCol:
You probably already have that algorithm so I won't go to the trouble of making a screenshot unless necessary.
DEBUG  (su1.algorithm.BlockToRowCol) BlockToCol around [1,1] for value:5
Meaning that for the block around position [1,1] (that is the upper left block of 9 squares), the value 5 can only be found in column 1 (again counting from 0). Therefore, value 5 is forbidden to the squares in that column that do not belong to the upper left block.
If you have any question, feel free to ask
I have a few tough algorithms in my program. (Though i programmed those some time ago and i might have trouble remembering exactly whta they did...) 

Back to top 


 Phoxtrot
 Joined: 11 Jul 2007  Posts: 2  :   Items 

Posted: Wed Jul 11, 2007 2:53 pm Post subject: 


Ohoh, I have added the XY wing algorithm explained above and now i can solve the illogical #16 too.
The only 2 difficult algorithms it used are the XYwing alogrithm (which i renamed crossSection3_0, go figure why...)
DEBUG  (su1.algorithm.CrossSection3_0) CrossSection3 (row) info on square [8,6] for value:3 by crossSecting (size2) 3 squares: [6,1];[8,2]&[6,6]
And a BlockToCol algorithm (as in my previous post but for a column instead of a row) 

Back to top 


 sardonic
 Joined: 30 Aug 2007  Posts: 1  :   Items 

Posted: Thu Aug 30, 2007 1:21 pm Post subject: 


I dont know bout you guys, but I dont solve sudoku's by first entering all numbers in all open squares and then remove the numbers allready taken. It would take ages this way and I'm pretty sure, you only use this method once you get stuck using the 'normal' method, like most of us do.
So I think most of us solve them the exact opposite way:
64__139__+1___264__+_29_457__+__2___83_+86__37_19+7__2_9___+__13__69_+9364_8_2_+__5______
First of all, I've given each big square (of 9 smaller squares) a number from 1 to 9, counting from left to right, top to bottom:
S1 S2 S3
S4 S5 S6
S7 S8 S9
Ok, lets start solving:
 S1 has a 1 at row B, S2 has a 1 at row A, so S3 should have a 1 in row C
 C7 is already taken and row 8 already has a 1, so C9 is the missing 1
 S1 has a 6 at row A, S2 has a 6 at row B, so S3 should have a 6 in row C
 only 1 spot left, so C8 is a 6
 S1 has a 2 at row C, S2 has a 2 at row B, so S3 should have a 2 in row A
 A7 is already taken and row 8 already has a 2, so A9 is a 2
 S1 has a 9 at row C, S3 has a 9 at row A, so S2 should have a 9 in row B
 only 1 spot left, so B4 is a 9
I call this method "comparing squares". The next method is "completing squares":
 S2 still needs a 7 and 8
 row C already has a 7, so C4 is an 8 and thus A4 is a 7
Which leads us to the next method "completing rows":
 row C still needs a 3, only 1 spot left, C1 is a 3
If you can solve the sudoku using only these 3 methods, then I categorize this as Easy.
I would really like to see you program a sudoku solver that uses this method, as its more realistic. Who on earth solves sudoku's by first filling all the blank spots with numbers 1 to 9
I know this is kinda like starting all over, so maybe program a second sudoku solver, using 'human' logic only 

Back to top 


 Pat
 Joined: 06 Sep 2006  Posts: 128  :   Items 

Posted: Tue Sep 04, 2007 12:35 pm Post subject: 


sardonic wrote: 
I dont know bout you guys, but I dont solve sudoku's by first entering all numbers in all open squares and then remove the numbers allready taken. It would take ages this way and I'm pretty sure, you only use this method once you get stuck using the 'normal' method, like most of us do.
So I think most of us solve them the exact opposite way:
Code: 
6 4 .  . 1 3  9 . .
1 . .  . 2 6  4 . .
. 2 9  . 4 5  7 . .
++
. . 2  . . .  8 3 .
8 6 .  . 3 7  . 1 9
7 . .  2 . 9  . . .
++
. . 1  3 . .  6 9 .
9 3 6  4 . 8  . 2 .
. . 5  . . .  . . .


hi sardonic,
i enjoy solving the puzzle on paper,
without writing the list of possiblities in each cell.it is a matter of personal preference 
some people have become accustomed to using software
which automatically handles those lists!
the example you gave is indeed easy,
it only needs "hidden singles"
sardonic wrote: 
First of all, I've given each big square (of 9 smaller squares) a number from 1 to 9, counting from left to right, top to bottom:
S1 S2 S3
S4 S5 S6
S7 S8 S9

we do indeed customarily number the boxes b1...b9  in the same order you used. 

Back to top 


 Miroslav Kuzela
 Joined: 12 Nov 2007  Posts: 1  :   Items 

Posted: Mon Nov 12, 2007 8:04 pm Post subject: Solve Method 


My question:
What are differences between the solve method C (difficulty score=16) and the solve method D (difficulty score=32) for value N=2 ??? 

Back to top 


 rajkumar_innani
 Joined: 21 Mar 2009  Posts: 1  :  Location: INDIA  Items 

Posted: Fri Jun 05, 2009 5:28 am Post subject: SUDOKU SOFTWARE 


I've developed tow softwares  one can solve the given puzzle and the other can generate millions and millions of new puzzles with their solutions. For further information contact direct No. +91 9448588369 

Back to top 


 hendrik
 Joined: 16 Apr 2010  Posts: 3  :   Items 

Posted: Fri Apr 16, 2010 8:52 am Post subject: Cannot understand solve method B or found bug 


Hello Developers,
i hacked a little sudoku solver by myself for fun and now found your sudoku solver.
Your code solves the following sudoku that my app cannot solve:
000000018700040000000000030420000700000001000000300000500070200601800000040000000
I checked your solve log and in found the place where the magic or the
bug happened (see below). Can you explain what happened there? I came
to the same upper block and can not see how to go further with solving.
Thank you and greetings
Hendrik
Code: 
==============================
Starting Solve Method B
 1 2 3 4 5 6 7 8 9
+
A  239 3569 2456 7 2569 2569 4569 1 8
B  7 1 8 2569 4 3 569 2569 2569
C  29 569 2456 2569 1 8 4569 3 7
D  4 2 3 569 5689 569 7 5689 1
E  89 56789 567 4 25689 1 35689 25689 23569
F  1 5689 56 3 25689 7 45689 245689 24569
G  5 38 9 1 7 46 2 468 346
H  6 37 1 8 2359 2459 3459 4579 3459
I  238 4 27 2569 23569 2569 1 56789 3569
The value 8 in block at [D7] must lie in column 7..
The value 2 in block at [G4] must lie in row H..
The value 2 in column 5 must lie in block at [D4]..
The value 2 in row B must lie in block at [A7]..
The value 4 in column 7 must lie in block at [A7]..
Ending Solve Method B
==============================
==============================
Starting Solve Method A
 1 2 3 4 5 6 7 8 9
+
A  239 3569 2456 7 569 2569 4569 1 8
B  7 1 8 569 4 3 569 2569 2569
C  29 569 2456 2569 1 8 4569 3 7
D  4 2 3 569 5689 569 7 569 1
E  89 56789 567 4 25689 1 35689 2569 23569
F  1 5689 56 3 25689 7 5689 24569 24569
G  5 38 9 1 7 46 2 468 346
H  6 37 1 8 359 2459 359 4579 3459
I  238 4 27 569 3569 569 1 56789 3569 


Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

Posted: Fri Apr 16, 2010 12:19 pm Post subject: 


Quote:  Code: 
H  6 37 1 8 359 2459 359 4579 3459 

Where, in this row, can you place the value 2?
Regards,
Mike Metcalf 

Back to top 


 hendrik
 Joined: 16 Apr 2010  Posts: 3  :   Items 

Posted: Fri Apr 16, 2010 1:28 pm Post subject: 


Hello Mike,
I understand how to go on with the second table. But i did not see how it is possible to come from the first table to the second table. I think there is maybe a bug in the solving code.
Greets,
Hendrik 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

Posted: Fri Apr 16, 2010 1:43 pm Post subject: 


I think not. For instance:
Quote:  The value 8 in block at [D7] must lie in column 7..

means that the other values 8 in that box can be eliminated. This is called 'pointing'. And so on.
HTH
Mike Metcalf 

Back to top 


 hendrik
 Joined: 16 Apr 2010  Posts: 3  :   Items 

Posted: Fri Apr 16, 2010 1:53 pm Post subject: 


Sure, you are right! Now i understand this. thank you!
Greets,
Hendrik 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
