|
View previous topic :: View next topic |
Author |
Message |
| nj3h
| Joined: 29 Jul 2005 | Posts: 9 | : | Location: Virginia - USA | Items |
|
Posted: Fri Jul 29, 2005 5:43 pm Post subject: Puzzle from question on Pappocom's forum |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Sat Jul 30, 2005 4:06 am Post subject: Re: Puzzle from question on Pappocom's forum |
|
|
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 |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sat Jul 30, 2005 8:29 am Post subject: Supercolouring solution |
|
|
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 |
|
|
| angusj Site Admin
| Joined: 18 Jun 2005 | Posts: 406 | : | | Items |
|
Posted: Sat Jul 30, 2005 9:49 am Post subject: |
|
|
AMcK wrote: | Conflict: 3f -> 1b x 3b |
Is there some way to 'see' this by looking at the completed colour map? |
|
Back to top |
|
|
| AMcK
| Joined: 07 Apr 2005 | Posts: 89 | : | Location: Cambridge | Items |
|
Posted: Sun Jul 31, 2005 1:19 pm Post subject: |
|
|
Angus
FYI I've updated my original supercolouring post with the full logical backtrace (for contraductions) as you suggest.
Regards
Andrew |
|
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
|