
View previous topic :: View next topic 
Author 
Message 
 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Mon May 25, 2009 8:29 am Post subject: 


Code: 
. 3 . . 2 5 7 . .
1 . . . 3 4 . . .
. . . . . . . 6 .
++
5 . . 8 . . . . .
6 . . . . 3 . . 7
. . 1 . . . . 2 6
++
. . 2 . . . . . 9
. 4 . 7 . . . . .
. . . 2 . . 6 8 . 
after ss steps
Almost Locked Set XZRule: A=r359c3 {3459}, B=r1258c8 {13459}, X=4, Z=3 => r8c3,r9c9<>3
1 single then
Almost Locked Set XZRule: A=r18c3 {568}, B=r1349c9 {13458}, X=8, Z=5 => r8c89,r9c2<>5
singles to the end
Code:  . . 8 3 1 . 6 . .
. . . . . 4 . . .
. . . . 9 . . . 3
++
. . . 5 . 9 . . .
8 . . 1 . . . 3 .
6 . 2 . . . 8 . 9
++
2 5 . 6 . . . . .
. . 9 . 2 . . . 7
. . . . . . 1 . . 
alot of singles then:
Skyscraper: 5 in r1c9,r2c5 (connected by r9c59) => r1c6,r2c7<>5
singles to the end.
Code:  . . . 6 7 . . . 9
1 6 . . . . . . .
. . . . . . . 5 .
++
. . . . . 8 4 . .
. . 4 . . . 8 1 .
. 7 . . . 9 . . .
++
. 3 . 9 5 . . . .
8 . . . . . . . .
4 . . . 2 . 1 7 3 
after ss
Almost Locked Set XZRule: A=r4c5 {36}, B=r146c1 {2356}, X=3, Z=6 => r4c3<>6
singles to the end.
Code:  . . . 3 . . 9 . 8
. . . . . 8 5 . .
. . . . 9 . . . 1
++
9 5 2 . . 4 6 . .
. . . . . . . . 5
8 . . . . . 4 1 .
++
. . 6 7 . 9 3 . .
. . 4 . . . . 6 .
5 . 8 . 6 . . . 9 
after ss
Empty Rectangle: 7 in b6 (r8c19) => r5c1<>7
XYZWing: 2/3/7 in r45c5,r5c7 => r5c6<>7
WWing: 7/3 in r4c5,r6c3 connected by 3 in r46c9 => r6c56<>7
Locked Candidates Type 1 (Pointing): 7 in b5 => r12c5<>7
Finned XWing: 7 r29 c28 fr2c1 => r1c2<>7
Almost Locked Set XZRule: A=r7c1 {12}, B=r13c3,r2c12,r3c1 {123457}, X=2, Z=1 => r1c1<>1
Almost Locked Set XZRule: A=r2c125 {1347}, B=r3c36 {357}, X=3, Z=7 => r3c1<>7
Almost Locked Set XZRule: A=r3c67 {257}, B=r6c2369 {23567}, X=5, Z=2 => r5c7<>2
more singles then
Naked Triple: 1,5,3 in r13c3,r2c2 => r1c2,r2c1<>1
XYZWing: 5/4/1 in r1c35,r2c5 => r1c6<>1
singles to the end.
{this was the more difficult of the 4 posted} 

Back to top 


 NewUrbanBlues
 Joined: 22 Oct 2006  Posts: 36  :   Items 

Posted: Mon May 25, 2009 4:55 pm Post subject: Solver Logic 


Hello strmckr
I agree with you. Logic should solved any boards...
Can you elaborate more about this technique ? What is its name ? Is there some Web pages explaining the logic behind ?
Thanks
Thierry 

Back to top 


 lkSudoku
 Joined: 16 May 2009  Posts: 60  :   Items 

Posted: Mon May 25, 2009 6:28 pm Post subject: 


In mathematical terms, there should exist a logic that solves all SuDoKu boards without backtracking, however this is only in theoretical term
All known logical methods that do not require backtracking are likely to cover only part of the entire logical space and thus when applying only known logical methods that are not equivalent to backtracking, it is not certain that they do solve any puzzle 

Back to top 


 strmckr
 Joined: 24 Apr 2009  Posts: 52  :   Items 

Posted: Tue May 26, 2009 2:50 am Post subject: 


http://sudokuone.com/
Set Theory:
the logic behind takes alot of understanding matrics.
and there specific arangment limits.
there isnt any simplistic way to explain how it works.
are you familar with the sk loop? (first seen to solve easter monster)
if you are it is a prime example of a cover matrics limit.
16 cells with 4 digits
each so that all digits are covered exactly 4 times thus all intersections between the 16 cells cannot contain the 4 digits.
Quote:  In mathematical terms, there should exist a logic that solves all SuDoKu boards without backtracking, however this is only in theoretical term
All known logical methods that do not require backtracking are likely to cover only part of the entire logical space and thus when applying only known logical methods that are not equivalent to backtracking, it is not certain that they do solve any puzzle 
there is an open thread on here that shows how to use dlx to find all cover sets.
http://www.setbb.com/sudoku/viewtopic.php?t=1747&mforum=sudoku
and is based on allan's coverset modles.
and has been sucessfully used to show an exact cover matrics that after application reduces a grid to all singles.
and this also works on all grids.
this method is the only appoarch that i have seen working that can solve all puzzles with none t&E logic. 

Back to top 


 lkSudoku
 Joined: 16 May 2009  Posts: 60  :   Items 

Posted: Thu May 28, 2009 7:06 pm Post subject: 


Perhaps another question should be asked:
Suppose we have any sudoku grid of size NxN where N is not a constant, can the solution be computed in time polynomial in N?
Is the NxN sudoku puzzle an NPHard problem?
Or, in simpler terms, can any NxN sudoku puzzle be solved in time that is not exponential in N?
A polynomial time algorithm rules out the set cover method, the trial and error method, and probably some other methods 

Back to top 


 gsf
 Joined: 18 Aug 2005  Posts: 408  :  Location: NJ USA  Items 

Posted: Thu May 28, 2009 8:28 pm Post subject: 


lkSudoku wrote:  Perhaps another question should be asked:
Suppose we have any sudoku grid of size NxN where N is not a constant, can the solution be computed in time polynomial in N?
Is the NxN sudoku puzzle an NPHard problem?
Or, in simpler terms, can any NxN sudoku puzzle be solved in time that is not exponential in N?
A polynomial time algorithm rules out the set cover method, the trial and error method, and probably some other methods 
NxN sudoku is NPcomplete 

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
