|
View previous topic :: View next topic |
Author |
Message |
| tilps
| Joined: 19 Jun 2005 | Posts: 44 | : | | Items |
|
Posted: Wed Jul 20, 2005 2:45 pm Post subject: Another case of avoiding trial/error |
|
|
While researching improving the performance of my sudoku generator i came upon the following position. (and lots more like it)
Code: | .......1.
....5.2..
.783..6..
8.3......
..21863..
......4.6
..1..879.
..4.2....
.3....... |
row 6 column 4 cannot be a 7 (just down left from the centre 8), but my program cannot generate logic to prove this fact. Is this situation an example where elimination of a possibility Requires trial/error or is the constructive logic required just so hiddeously complex that my program doesnt go near it? |
|
Back to top |
|
|
| Nick70
| Joined: 08 Jun 2005 | Posts: 160 | : | | Items |
|
Posted: Wed Jul 20, 2005 2:54 pm Post subject: |
|
|
First of all, the problem you posted doesn't have a unique solution.
Having said that, you can actually prove that (6,4)<>7.
You need a triple forcing chain, however.
Code: | 234569 2459 569 | 246789 4679 2479 | 589 1 345789
13469 149 69 | 46789 5 1479 | 2 347 34789
12459 7 8 | 3 149 1249 | 6 45 459
-------------------------+--------------------------+-------------------------
8 6 3 | 4579 479 4579 | 159 257 12579
4579 459 2 | 1 8 6 | 3 57 579
1579 159 579 | 2579 379 23579 | 4 8 6
-------------------------+--------------------------+-------------------------
256 25 1 | 456 346 8 | 7 9 2345
5679 8 4 | 5679 2 13579 | 15 356 135
25679 3 5679 | 45679 14679 14579 | 158 2456 12458
Found a forcing chain:
(8,1)=7 => (9,3)<>7 => (6,3)=7 => (6,4)<>7
(8,4)=7 => (6,4)<>7
(8,6)=7 => (8,6)<>3 => (6,6)=3 => (6,6)<>2 => (6,4)=2 => (6,4)<>7
- Remove 7 from (6,4)
|
|
|
Back to top |
|
|
| tilps
| Joined: 19 Jun 2005 | Posts: 44 | : | | Items |
|
Posted: Wed Jul 20, 2005 10:55 pm Post subject: |
|
|
Should have mentioned that I know it doesnt have a unique solution. Its from the middle of the generation phase. I was trying to generate puzzles iteratively, by only placing numbers onto places which are still possible after the previous phase. However, I was producing problems which were unsolvable, much to my distaste.
hrmm, the removal of the 7 must not result in progress, or I would have found this myself during my followup testing.
Looks like I should seperate n-tupple checking (where n>2) from increased lookahead. |
|
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
|