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   

Puzzle from question on Pappocom's forum

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku
View previous topic :: View next topic  
Author Message
nj3h

Joined: 29 Jul 2005
Posts: 9
:
Location: Virginia - USA

Items
PostPosted: Fri Jul 29, 2005 5:43 pm    Post subject: Puzzle from question on Pappocom's forum Reply with quote

Angus, I d/l your program to give it a try. It looks like a great program in that is does the candidate determinations for you. Anyway, I do have the following situation described below I would like your comments on if you can spare a few minutes.

I copied the progress that someone else had made into your program. After about 5 clicks or so on solve next step, the program stopped providing any more answers. The matrix is as follows:

xx8 463 759
xx7 825 x16
x65 179 8x2

851 6x2 x7x
x32 xx7 x68
67x xx8 52x

xxx xx6 28x
x8x xx1 6x5
5x6 x84 x97

By the way, the question is in the Non-Pappocom directory. The message is titled "Stuck - What else" or something like that.

In the other forum scrose talks about using foced chains to solve. Am I using your program incorrectly in that I don't get any further in getting to a solution using the F11 key?

One other question, is there a button or option to solve the entire puzzle with one command?

Thanks,
nj3h (George)
Back to top
View user's profile Send private message
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sat Jul 30, 2005 4:06 am    Post subject: Re: Puzzle from question on Pappocom's forum Reply with quote

nj3h wrote:
I copied the progress that someone else had made into your program. After about 5 clicks or so on solve next step, the program stopped providing any more answers.

Hi George. There will alway be puzzles where it'll be impossible, or too complicated, to explain to mere mortals the logic behind a step - and at that point Simple Sudoku will simple say 'No Hint available'. (Note: that's not to say the boundaries of what's solvable and explainable wont change over time.)

nj3h wrote:
In the other forum scrose talks about using foced chains to solve. Am I using your program incorrectly in that I don't get any further in getting to a solution using the F11 key?

No, you've just hit the current limit of Simple Sudoku's solving matrix.

nj3h wrote:
One other question, is there a button or option to solve the entire puzzle with one command?

No, you can only get SS to solve one step at a time.
Back to top
View user's profile Send private message Visit poster's website
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Sat Jul 30, 2005 8:29 am    Post subject: Supercolouring solution Reply with quote

Here's the supercolouring solution to the puzzle.
[New] I've now added backtrace analysis of the reasoning leading to each move.
Here's the starting point
Code:

12   12   8    4    6    3    7    5    9   
349  49   7    8    2    5    34   1    6   
34   6    5    1    7    9    8    34   2   
8    5    1    6    349  2    349  7    34   
49   3    2    59   1459 7    149  6    8   
6    7    49   39   1349 8    5    2    134 
17   49   349  3579 359  6    2    8    134 
27   8    349  27   39   1    6    34   5   
5    12   6    23   8    4    13   9    7   

The supercolour map is
Code:

1a2a     1b2b     *        *        *        *        *        *        *       
3a9a     4b9b     *        *        *        *        3b4c     *        *       
3b4c     *        *        *        *        *        *        3a4b     *       
*        *        *        *        3e4f     *        9d       *        3g4h     
4b9b     *        *        5a       1b4j5b   *        1a       *        *       
*        *        4c9a     3h9j     1a3i4m9k *        *        *        1b3j     
1b7a     4c9a     3k9m     3l5b7b9n 3m5a9o   *        *        *        1a3n4b   
2b7b     *        3o4b9p   2a7a     3p9q     *        *        3b4c     *       
*        1a2a     *        2b3r     *        *        1b3s     *        *       

Here is all the logic leading to contradictions that enable reductions. It's still a bit flaky so apologies for any errors.
Code:

Constraint in col 7 3b excludes 3f
Conjugate in row 2 3a conjugates 3b
3f excludes 3b and 3b conjugates 3a so 3f implies 3a
Exclusion in {4,7} 3f excludes 9d
Conjugate in row 4 9c conjugates 9d
3f excludes 9d and 9d conjugates 9c so 3f implies 9c
Constraint in row 5 9b excludes 9c
Conjugate in row 2 9a conjugates 9b
9c excludes 9b and 9b conjugates 9a so 9c implies 9a
3f implies 9c and 9c implies 9a so 3f implies 9a
Exclusion in {2,1} 3a excludes 9a
Conjugate in row 2 3a conjugates 3b
9a excludes 3a and 3a conjugates 3b so 9a implies 3b
3f implies 9a and 9a implies 3b so 3f implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 3f implies 3a and 3f implies 3b but 3a excludes 3b
Reduction: 3f=false in {4,7} before=349 after=49

Constraint in col 1 4a excludes 4i
Conjugate in box 4 4i conjugates 4l
4a excludes 4i and 4i conjugates 4l so 4a implies 4l
Constraint in col 3 4l excludes 4e
Conjugate in row 3 4c conjugates 4e
4l excludes 4e and 4e conjugates 4c so 4l implies 4c
4a implies 4l and 4l implies 4c so 4a implies 4c
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 2 3a conjugates 3b
4c excludes 3b and 3b conjugates 3a so 4c implies 3a
4a implies 4c and 4c implies 3a so 4a implies 3a
Exclusion in {2,1} 3a excludes 4a
Conjugate in row 2 3a conjugates 3b
4a excludes 3a and 3a conjugates 3b so 4a implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 4a implies 3a and 4a implies 3b but 3a excludes 3b
Reduction: 4a=false in {2,1} before=349 after=39

Exclusion in {4,7} 4g excludes 9d
Conjugate in row 4 9c conjugates 9d
4g excludes 9d and 9d conjugates 9c so 4g implies 9c
Constraint in col 5 9c excludes 9q
Conjugate in row 8 9p conjugates 9q
9c excludes 9q and 9q conjugates 9p so 9c implies 9p
4g implies 9c and 9c implies 9p so 4g implies 9p
Exclusion in {8,3} 4e excludes 9p
Conjugate in row 3 4c conjugates 4e
9p excludes 4e and 4e conjugates 4c so 9p implies 4c
4g implies 9p and 9p implies 4c so 4g implies 4c
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 2 3a conjugates 3b
4c excludes 3b and 3b conjugates 3a so 4c implies 3a
4g implies 4c and 4c implies 3a so 4g implies 3a
Constraint in col 7 4c excludes 4g
Conjugate in row 3 4c conjugates 4e
4g excludes 4c and 4c conjugates 4e so 4g implies 4e
Exclusion in {3,8} 3a excludes 4e
Conjugate in row 2 3a conjugates 3b
4e excludes 3a and 3a conjugates 3b so 4e implies 3b
4g implies 4e and 4e implies 3b so 4g implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 4g implies 3a and 4g implies 3b but 3a excludes 3b
Reduction: 4g=false in {4,7} before=49 after=9

Constraint in row 5 4i excludes 4k
Conjugate in box 4 4i conjugates 4l
4k excludes 4i and 4i conjugates 4l so 4k implies 4l
Constraint in col 3 4l excludes 4e
Conjugate in row 3 4c conjugates 4e
4l excludes 4e and 4e conjugates 4c so 4l implies 4c
4k implies 4l and 4l implies 4c so 4k implies 4c
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 2 3a conjugates 3b
4c excludes 3b and 3b conjugates 3a so 4c implies 3a
4k implies 4c and 4c implies 3a so 4k implies 3a
Constraint in col 7 4c excludes 4k
Conjugate in row 3 4c conjugates 4e
4k excludes 4c and 4c conjugates 4e so 4k implies 4e
Exclusion in {3,8} 3a excludes 4e
Conjugate in row 2 3a conjugates 3b
4e excludes 3a and 3a conjugates 3b so 4e implies 3b
4k implies 4e and 4e implies 3b so 4k implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 4k implies 3a and 4k implies 3b but 3a excludes 3b
Reduction: 4k=false in {5,7} before=149 after=19

Exclusion in {6,9} 1c excludes 4n
Conjugate in col 9 1c conjugates 1a
4n excludes 1c and 1c conjugates 1a so 4n implies 1a
Constraint in row 6 4l excludes 4n
Conjugate in box 4 4i conjugates 4l
4n excludes 4l and 4l conjugates 4i so 4n implies 4i
Constraint in col 1 4c excludes 4i
Conjugate in row 3 4c conjugates 4e
4i excludes 4c and 4c conjugates 4e so 4i implies 4e
Exclusion in {7,9} 1a excludes 4e
Conjugate in row 1 1a conjugates 1b
4e excludes 1a and 1a conjugates 1b so 4e implies 1b
4i implies 4e and 4e implies 1b so 4i implies 1b
4n implies 4i and 4i implies 1b so 4n implies 1b
Constraint in row 1 1a excludes 1b
Conflict: 4n implies 1a and 4n implies 1b but 1a excludes 1b
Reduction: 4n=false in {6,9} before=134 after=13

Exclusion in {7,3} 3k excludes 4p
Conjugate in col 3 3k conjugates 3o
4p excludes 3k and 3k conjugates 3o so 4p implies 3o
Constraint in row 8 3o excludes 3b
Conjugate in row 2 3a conjugates 3b
3o excludes 3b and 3b conjugates 3a so 3o implies 3a
4p implies 3o and 3o implies 3a so 4p implies 3a
Constraint in row 7 4o excludes 4p
Conjugate in col 2 4b conjugates 4o
4p excludes 4o and 4o conjugates 4b so 4p implies 4b
Constraint in row 2 4b excludes 4c
Conjugate in row 3 4c conjugates 4e
4b excludes 4c and 4c conjugates 4e so 4b implies 4e
Exclusion in {3,8} 3a excludes 4e
Conjugate in row 2 3a conjugates 3b
4e excludes 3a and 3a conjugates 3b so 4e implies 3b
4b implies 4e and 4e implies 3b so 4b implies 3b
4p implies 4b and 4b implies 3b so 4p implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 4p implies 3a and 4p implies 3b but 3a excludes 3b
Reduction: 4p=false in {7,3} before=349 after=39

Constraint in col 5 9c excludes 9q
Conjugate in row 8 9p conjugates 9q
9c excludes 9q and 9q conjugates 9p so 9c implies 9p
Exclusion in {8,3} 4e excludes 9p
Conjugate in row 3 4c conjugates 4e
9p excludes 4e and 4e conjugates 4c so 9p implies 4c
9c implies 9p and 9p implies 4c so 9c implies 4c
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 2 3a conjugates 3b
4c excludes 3b and 3b conjugates 3a so 4c implies 3a
9c implies 4c and 4c implies 3a so 9c implies 3a
Constraint in row 5 9b excludes 9c
Conjugate in row 2 9a conjugates 9b
9c excludes 9b and 9b conjugates 9a so 9c implies 9a
Exclusion in {2,1} 3a excludes 9a
Conjugate in row 2 3a conjugates 3b
9a excludes 3a and 3a conjugates 3b so 9a implies 3b
9c implies 9a and 9a implies 3b so 9c implies 3b
Constraint in row 2 3a excludes 3b
Conflict: 9c implies 3a and 9c implies 3b but 3a excludes 3b
Reduction: 9c=false in {4,5} before=349 after=34
Reduction: 9c=false in {5,7} before=19 after=1

Exclusion in {5,4} 5a excludes 9f
Conjugate in row 5 5a conjugates 5b
9f excludes 5a and 5a conjugates 5b so 9f implies 5b
Exclusion in {5,5} 1c excludes 5b
Conjugate in col 9 1c conjugates 1a
5b excludes 1c and 1c conjugates 1a so 5b implies 1a
9f implies 5b and 5b implies 1a so 9f implies 1a
Constraint in row 5 9b excludes 9f
Conjugate in row 2 9a conjugates 9b
9f excludes 9b and 9b conjugates 9a so 9f implies 9a
Exclusion in {2,1} 3a excludes 9a
Conjugate in row 2 3a conjugates 3b
9a excludes 3a and 3a conjugates 3b so 9a implies 3b
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 3 4c conjugates 4e
3b excludes 4c and 4c conjugates 4e so 3b implies 4e
Exclusion in {7,9} 1a excludes 4e
Conjugate in row 1 1a conjugates 1b
4e excludes 1a and 1a conjugates 1b so 4e implies 1b
3b implies 4e and 4e implies 1b so 3b implies 1b
9a implies 3b and 3b implies 1b so 9a implies 1b
9f implies 9a and 9a implies 1b so 9f implies 1b
Constraint in row 1 1a excludes 1b
Conflict: 9f implies 1a and 9f implies 1b but 1a excludes 1b
Reduction: 9f=false in {5,4} before=59 after=5

Exclusion in {5,5} 1c excludes 9g
Conjugate in col 9 1c conjugates 1a
9g excludes 1c and 1c conjugates 1a so 9g implies 1a
Constraint in row 5 9b excludes 9g
Conjugate in row 2 9a conjugates 9b
9g excludes 9b and 9b conjugates 9a so 9g implies 9a
Exclusion in {2,1} 3a excludes 9a
Conjugate in row 2 3a conjugates 3b
9a excludes 3a and 3a conjugates 3b so 9a implies 3b
Exclusion in {2,7} 3b excludes 4c
Conjugate in row 3 4c conjugates 4e
3b excludes 4c and 4c conjugates 4e so 3b implies 4e
Exclusion in {7,9} 1a excludes 4e
Conjugate in row 1 1a conjugates 1b
4e excludes 1a and 1a conjugates 1b so 4e implies 1b
3b implies 4e and 4e implies 1b so 3b implies 1b
9a implies 3b and 3b implies 1b so 9a implies 1b
9g implies 9a and 9a implies 1b so 9g implies 1b
Constraint in row 1 1a excludes 1b
Conflict: 9g implies 1a and 9g implies 1b but 1a excludes 1b
Reduction: 9g=false in {5,5} before=1459 after=145

I've omitted the trace of the multi-recolouring step later which sometimes helps the final reductions.
Regards
Andrew


Last edited by AMcK on Sun Jul 31, 2005 1:16 pm; edited 3 times in total
Back to top
View user's profile Send private message Send e-mail
angusj
Site Admin
Joined: 18 Jun 2005
Posts: 406
:

Items
PostPosted: Sat Jul 30, 2005 9:49 am    Post subject: Reply with quote

AMcK wrote:
Conflict: 3f -> 1b x 3b

Is there some way to 'see' this by looking at the completed colour map?
Back to top
View user's profile Send private message Visit poster's website
AMcK

Joined: 07 Apr 2005
Posts: 89
:
Location: Cambridge

Items
PostPosted: Sun Jul 31, 2005 1:19 pm    Post subject: Reply with quote

Angus
FYI I've updated my original supercolouring post with the full logical backtrace (for contraductions) as you suggest.
Regards
Andrew
Back to top
View user's profile Send private message Send e-mail
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Solving sudoku All times are GMT
Page 1 of 1

 
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