Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

User-friendly internet only solver at sudokusolver.co.uk
Goto page Previous  1, 2, 3
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software
View previous topic :: View next topic  
Author Message
dagojr

Joined: 26 Jan 2007
Posts: 1
:

Items
PostPosted: Fri Jan 26, 2007 5:56 pm    Post subject: Logical solution to #27 Reply with quote

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
View user's profile Send private message
coloin

Joined: 05 May 2005
Posts: 97
:

Items
PostPosted: Sun Jan 28, 2007 12:09 am    Post subject: Reply with quote

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:
XY-Wing
The three cells B6, A4 and H6 form an XY-Wing 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.

XY-Wing
The three cells H6, I4 and B6 form an XY-Wing 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
View user's profile Send private message
Phoxtrot

Joined: 11 Jul 2007
Posts: 2
:

Items
PostPosted: Wed Jul 11, 2007 11:32 am    Post subject: Illogical #13 Reply with quote

Hello,
I have had about the same idea as you and made a logical sudoku solver too Smile
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 Smile

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
View user's profile Send private message
Phoxtrot

Joined: 11 Jul 2007
Posts: 2
:

Items
PostPosted: Wed Jul 11, 2007 2:53 pm    Post subject: Reply with quote

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 XY-wing 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
View user's profile Send private message
sardonic

Joined: 30 Aug 2007
Posts: 1
:

Items
PostPosted: Thu Aug 30, 2007 1:21 pm    Post subject: Reply with quote

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 Confused

I know this is kinda like starting all over, so maybe program a second sudoku solver, using 'human' logic only Wink
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Tue Sep 04, 2007 12:35 pm    Post subject: Reply with quote

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
View user's profile Send private message Visit poster's website
Miroslav Kuzela

Joined: 12 Nov 2007
Posts: 1
:

Items
PostPosted: Mon Nov 12, 2007 8:04 pm    Post subject: Solve Method Reply with quote

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
View user's profile Send private message
rajkumar_innani

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

Items
PostPosted: Fri Jun 05, 2009 5:28 am    Post subject: SUDOKU SOFTWARE Reply with quote

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
View user's profile Send private message Send e-mail
hendrik

Joined: 16 Apr 2010
Posts: 3
:

Items
PostPosted: Fri Apr 16, 2010 8:52 am    Post subject: Cannot understand solve method B or found bug Reply with quote

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
View user's profile Send private message
m_b_metcalf

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

Items
PostPosted: Fri Apr 16, 2010 12:19 pm    Post subject: Reply with quote

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
View user's profile Send private message
hendrik

Joined: 16 Apr 2010
Posts: 3
:

Items
PostPosted: Fri Apr 16, 2010 1:28 pm    Post subject: Reply with quote

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
View user's profile Send private message
m_b_metcalf

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

Items
PostPosted: Fri Apr 16, 2010 1:43 pm    Post subject: Reply with quote

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
View user's profile Send private message
hendrik

Joined: 16 Apr 2010
Posts: 3
:

Items
PostPosted: Fri Apr 16, 2010 1:53 pm    Post subject: Reply with quote

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

Greets,
Hendrik
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Software All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron