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   

Interesting Puzzle in the 6/12 Sunday Express

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

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Sun Jun 12, 2005 6:05 pm    Post subject: Interesting Puzzle in the 6/12 Sunday Express Reply with quote

The 6/12 Sunday Express puzzle is interesting because it isn't solvable by logic (by my app, or the sudokusolver.co.uk solver). Even Simple Forcing Chains, Nishio and Fishy Cycles come up empty (though the last simplification is a Fishy Cycle).

I post it because examining this puzzle may bring to light new logic techniques that we haven't recognized yet (or, for example, show that limited implication is needed). Or it may just be that the Telegraph puzzle setter screwed up and made it a pure guessing problem!

Here is the initial state of the puzzle:

Code:
+-------+-------+-------+
| . . . | . 1 . | . . . |
| 7 . . | . . . | 8 . . |
| . . 3 | . 6 . | 4 . . |
+-------+-------+-------+
| 3 1 . | . 4 9 | . 6 . |
| . . 8 | . 2 . | 7 . . |
| . 5 . | 7 3 . | . 1 8 |
+-------+-------+-------+
| . . 9 | . 8 . | 3 . . |
| . . 4 | . . . | . . 2 |
| . . . | . 5 . | . . . |
+-------+-------+-------+


And here is where the logic solve stalls (this $&*$ puzzle made me go and add feature that let me drag text versions of puzzles out of my app with the constraints displayed, just for you guys!)

Code:
+-----------------------+-----------------------+-----------------------+
|       .       .       |       .       .       |       .       .       |
| 2 8 9 . 2 4 8 . 5 6   | 2 3 4 .   #   . 7 8   | 5 6   . 2 3 7 . 3 7 9 |
|       . 9     .       |       .   #   .       |       . 9     .       |
|       .       .       |       .   #   .       |       .       .       |
|       .       .       |       .   #   .       |       .       .       |
|       .       .       |       .   #   .       |       .       .       |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| ##### . 2 4 6 . 1 5   | 2 3 4 . ##### . 2 3 4 | ##### . 2 3 5 . 1 3 6 |
|     # .       .       | 5     . #   # . 5     | #   # .       .       |
|     # .       .       |       . ##### .       | ##### .       .       |
|     # .       .       |       .     # .       | #   # .       .       |
|     # .       .       |       .     # .       | ##### .       .       |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| 1 2 8 . 2 8 9 . ##### | 2 5   . ##### . 7 8   | # #   . 2 5 7 . 1 7 9 |
| 9     .       .     # |       . #     .       | # #   . 9     .       |
|       .       .  #### |       . ##### .       | ##### .       .       |
|       .       .     # |       . #   # .       |   #   .       .       |
|       .       . ##### |       . ##### .       |   #   .       .       |
+-----------------------+-----------------------+-----------------------+
|       .       .       |       .       .       |       .       .       |
| ##### .   #   . ##### | ##### . # #   . ##### | ##### . ##### . ##### |
|     # .   #   .     # | #   # . # #   . #   # |     # . #     . #     |
|  #### .   #   .     # | ##### . ##### . ##### | ##### . ##### . ##### |
|     # .   #   .     # | #   # .   #   .     # | #     . #   # .     # |
| ##### .   #   .     # | ##### .   #   .     # | ##### . ##### . ##### |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| 6 9   . 6 9   . ##### | 1 5   . ##### . 1 5   | ##### . 3 4   . 3 4   |
|       .       . #   # |       .     # .       |     # .       .       |
|       .       . ##### |       . ##### .       |     # .       .       |
|       .       . #   # |       . #     .       |     # .       .       |
|       .       . ##### |       . ##### .       |     # .       .       |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| # #   . ##### . ##### | ##### . ##### . ##### | ##### .   #   . ##### |
| # #   . #     .     # |     # .     # . #     | #   # .   #   . #   # |
| ##### . ##### . ##### |     # .  #### . ##### | ##### .   #   . ##### |
|   #   .     # . #     |     # .     # . #   # |     # .   #   . #   # |
|   #   . ##### . ##### |     # . ##### . ##### |     # .   #   . ##### |
+-----------------------+-----------------------+-----------------------+
|       .       .       |       .       .       |       .       .       |
| 1 2 5 . 2 6 7 . ##### | 1 2 4 . ##### . 1 2 4 | ##### . 4 5 7 . 4 6 7 |
| 6     .       . #   # | 6     . #   # .       |     # .       .       |
|       .       . ##### |       . ##### .       |  #### .       .       |
|       .       .     # |       . #   # .       |     # .       .       |
|       .       .     # |       . ##### .       | ##### .       .       |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| 1 5 6 . 3 6 8 . # #   | 1 3 6 . ##### . 1 3   | 1 5   . 5 8 9 . ##### |
| 8     .       . # #   | 9     .     # .       |       .       .     # |
|       .       . ##### |       .     # .       |       .       . ##### |
|       .       .   #   |       .     # .       |       .       . #     |
|       .       .   #   |       .     # .       |       .       . ##### |
|.......................................................................|
|       .       .       |       .       .       |       .       .       |
| 2 8   . 2 3 7 . 1 6   | 2 3 4 . ##### . 2 3 4 | 1 6   . 4 7 8 . 4 7 9 |
|       . 8     .       | 9     . #     .       |       . 9     .       |
|       .       .       |       . ##### .       |       .       .       |
|       .       .       |       .     # .       |       .       .       |
|       .       .       |       . ##### .       |       .       .       |
+-----------------------+-----------------------+-----------------------+


I have a hunch the key, if there is one, is in the locked pairs in R5 somehow telling us something about the blocks above and below them.
Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Tue Jun 14, 2005 2:22 am    Post subject: Reply with quote

Very nice problem there. Good one for searching for new algorithms!
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Tue Jun 14, 2005 3:13 am    Post subject: Reply with quote

I see how to reason this one out. I'll try to construct an algorithm from my solution. Smile BTW I think I can extend the coloring algorithm to get it. Not positive yet, though.

Edit: Nope, not the coloring algorithm. More like the Simple Forcing Chains.

Here is the solution:

R2C3=5 -> R2C9=1 -> R2C2=6.
But also.
R2C3=5 -> R1C3=6.

Contradiction, two 6's in block 1. So R2C3 = 1. Rest of puzzle follows from standard techniques.

You need to allow Simple Forcing Chains to follow all implications from conjugate pairs (houses with only two possible cells for a number) as well as pairs (cells with only two possibilities, which you have currently enabled, I believe.)

This is a great case for loosening up Simple Forcing Chains a bit! I did this one in my head!

Edit: Ahh, maybe what you need is to allow for two or more chains to extend off a single start value and compare implications! I think that may be what is missing.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Wed Jun 15, 2005 3:06 am    Post subject: Reply with quote

I've found a way that human beings can do a semi-recursive elimination technique that is a superset of Simple Forcing Chains and Nishio. It cracks the puzzle. Because it uses Bingo chips and was inspired in part by Doug's coloring algorithm, I've dubbed it Bowman Bingo.

In order to do Bowman Bingo by hand, you will need a supply of translucent chips, such as the ones used by Bingo players (hence the name). Mark them with the numbers 1-9 so you have at least 9 of each number.

Pick a square that you wish to test, and pick a possible number for that square. Take a chip of that number and put it on the square upside-down. Now repeat the following loop:

1) Find an upside-down chip and turn it rightside-up. This is the current chip.

2) Find squares in the same row, column and block as the current chip that are forced to a single value (after eliminating the values used by rightside-up chips), and place an upside-down chip with that value written on it on the new square.

Example: you just flipped a <1> chip on R1C1. R3C3 (in the same block) has possible values <123>, and there’s a previously-flipped chip on R3C8 that has value <3>. So R3C3 is forced to <2>, and you put an upside-down <2> on it.

3) If any row, column or block now has 2 chips with the same number (either rightside-up or upside-down), then you’ve got a contradiction, and your original choice can be eliminated. Bingo, you’re a winner.

4) If you have any unflipped chips, go to step 1.

If you end up with all your chips flipped, then you’re not a winner (unless, of course, you’ve got chips on all the unsolved squares, in which case, you’ve lucked into the solution of the puzzle!). Pick another square or number, and try again.

It is entirely unclear at this point whether there are ways of picking squares to test that increase your chances of a Bingo. My guess would be, pick squares whose solution will tell you a lot about the rest of the puzzle. It will also be interesting to see if there are more complicated patterns than the “2 chips in a group with the same number” that indicate a contradiction.

Here's the trace of it cracking the Sudoku from the above stopping point:

Code:
Deduction pass 1; 35 squares solved; 46 remaining.

* Found a contradiction by Bowman Bingo.  After 7
  cycles, it became clear that R2C6 could not be a
  <3>, because this would force both R2C9 and
  R2C3 to be <1>.

  As they are in the same row, this is not possible.

   R2C6 - removing <3> from <2345> leaving <245>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 X 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 . . . 2
   . . . . 5 . . . .

  Flipped chip at R2C6 setting its value to <3>.

   Placed a <1> chip on R8C6.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 3 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 X . . 2
   . . . . 5 . . . .

  Flipped chip at R8C6 setting its value to <1>.

   Placed a <5> chip on R8C7.
   Placed a <5> chip on R5C6.

  Bowman cycle 3:

   . . . . 1 . . . .
   7 . . . 9 3 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 C 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 X . 2
   . . . . 5 . . . .

  Flipped chip at R8C7 setting its value to <5>.

   Placed a <6> chip on R1C7.

  Bowman cycle 4:

   . . . . 1 . C . .
   7 . . . 9 3 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 X 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 5 . 2
   . . . . 5 . . . .

  Flipped chip at R5C6 setting its value to <5>.

   Placed a <1> chip on R5C4.

  Bowman cycle 5:

   . . . . 1 . X . .
   7 . . . 9 3 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 C 2 5 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 5 . 2
   . . . . 5 . . . .

  Flipped chip at R1C7 setting its value to <6>.

   Placed a <5> chip on R1C3.
   Placed a <1> chip on R9C7.
   Placed a <1> chip on R2C9.

  Bowman cycle 6:

   . . C . 1 . 6 . .
   7 . . . 9 3 8 . C
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 X 2 5 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 5 . 2
   . . . . 5 . C . .

  Flipped chip at R5C4 setting its value to <1>.

  Bowman cycle 7:

   . . X . 1 . 6 . .
   7 . . . 9 3 8 . C
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 1 2 5 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 5 . 2
   . . . . 5 . C . .

  Flipped chip at R1C3 setting its value to <5>.

   Placed a <1> chip on R2C3.

  Final state:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 3 8 . 1
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 1 2 5 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 . 7 1 5 . 2
   . . . . 5 . 1 . .

  Both R2C9 and R2C3 are <1>.

Deduction pass 2; 35 squares solved; 46 remaining.

* Intersection of column 6 with block 8.
  The non-intersecting squares of the block
  cannot contain the values <3>.

   R8C4 - removing <3> from <1369> leaving <169>.
   R9C4 - removing <3> from <2349> leaving <249>.

Deduction pass 3; 35 squares solved; 46 remaining.

* Found a contradiction by Bowman Bingo.  After 11
  cycles, it became clear that R8C4 could not be a
  <1>, because this would force both R8C1 and
  R8C2 to be <8>.

  As they are in the same row, this is not possible.

   R8C4 - removing <1> from <169> leaving <69>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 X 7 . . . 2
   . . . . 5 . . . .

  Flipped chip at R8C4 setting its value to <1>.

   Placed a <3> chip on R8C6.
   Placed a <5> chip on R8C7.
   Placed a <5> chip on R5C4.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 C 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 X C . 2
   . . . . 5 . . . .

  Flipped chip at R8C6 setting its value to <3>.

  Bowman cycle 3:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 C 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 X . 2
   . . . . 5 . . . .

  Flipped chip at R8C7 setting its value to <5>.

   Placed a <6> chip on R1C7.

  Bowman cycle 4:

   . . . . 1 . C . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 X 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . . . .

  Flipped chip at R5C4 setting its value to <5>.

   Placed a <1> chip on R5C6.
   Placed a <2> chip on R3C4.

  Bowman cycle 5:

   . . . . 1 . X . .
   7 . . . 9 . 8 . .
   . . 3 C 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 C 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . . . .

  Flipped chip at R1C7 setting its value to <6>.

   Placed a <5> chip on R1C3.
   Placed a <1> chip on R9C7.

  Bowman cycle 6:

   . . C . 1 . 6 . .
   7 . . . 9 . 8 . .
   . . 3 C 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 X 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . C . .

  Flipped chip at R5C6 setting its value to <1>.

  Bowman cycle 7:

   . . C . 1 . 6 . .
   7 . . . 9 . 8 . .
   . . 3 X 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . C . .

  Flipped chip at R3C4 setting its value to <2>.

  Bowman cycle 8:

   . . X . 1 . 6 . .
   7 . . . 9 . 8 . .
   . . 3 2 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . C . .

  Flipped chip at R1C3 setting its value to <5>.

   Placed a <1> chip on R2C3.

  Bowman cycle 9:

   . . 5 . 1 . 6 . .
   7 . C . 9 . 8 . .
   . . 3 2 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . . . 5 . X . .

  Flipped chip at R9C7 setting its value to <1>.

   Placed a <6> chip on R9C3.

  Bowman cycle 10:

   . . 5 . 1 . 6 . .
   7 . X . 9 . 8 . .
   . . 3 2 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . C . 5 . 1 . .

  Flipped chip at R2C3 setting its value to <1>.

   Placed a <3> chip on R2C9.

  Bowman cycle 11:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . C
   . . 3 2 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   . . 4 1 7 3 5 . 2
   . . X . 5 . 1 . .

  Flipped chip at R9C3 setting its value to <6>.

   Placed a <8> chip on R8C1.
   Placed a <8> chip on R8C2.

  Final state:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . 3
   . . 3 2 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 5 2 1 7 . .
   4 5 2 7 3 6 9 1 8
   . . 9 . 8 . 3 . .
   8 8 4 1 7 3 5 . 2
   . . 6 . 5 . 1 . .

  Both R8C1 and R8C2 are <8>.

Deduction pass 4; 35 squares solved; 46 remaining.

* Found a contradiction by Bowman Bingo.  After 12
  cycles, it became clear that R7C1 could not be a
  <1>, because this would force both R9C2 and
  R7C2 to be <7>.

  As they are in the same column, this is not possible.

   R7C1 - removing <1> from <1256> leaving <256>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   X . 9 . 8 . 3 . .
   . . 4 . 7 . . . 2
   . . . . 5 . . . .

  Flipped chip at R7C1 setting its value to <1>.

   Placed a <6> chip on R9C3.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   . . 4 . 7 . . . 2
   . . X . 5 . . . .

  Flipped chip at R9C3 setting its value to <6>.

   Placed a <1> chip on R9C7.
   Placed a <5> chip on R1C3.

  Bowman cycle 3:

   . . C . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   . . 4 . 7 . . . 2
   . . 6 . 5 . X . .

  Flipped chip at R9C7 setting its value to <1>.

   Placed a <5> chip on R8C7.

  Bowman cycle 4:

   . . X . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   . . 4 . 7 . C . 2
   . . 6 . 5 . 1 . .

  Flipped chip at R1C3 setting its value to <5>.

   Placed a <6> chip on R1C7.
   Placed a <1> chip on R2C3.

  Bowman cycle 5:

   . . 5 . 1 . C . .
   7 . C . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   . . 4 . 7 . X . 2
   . . 6 . 5 . 1 . .

  Flipped chip at R8C7 setting its value to <5>.

   Placed a <8> chip on R8C1.

  Bowman cycle 6:

   . . 5 . 1 . X . .
   7 . C . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   C . 4 . 7 . 5 . 2
   . . 6 . 5 . 1 . .

  Flipped chip at R1C7 setting its value to <6>.

  Bowman cycle 7:

   . . 5 . 1 . 6 . .
   7 . X . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   C . 4 . 7 . 5 . 2
   . . 6 . 5 . 1 . .

  Flipped chip at R2C3 setting its value to <1>.

   Placed a <3> chip on R2C9.

  Bowman cycle 8:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . C
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   X . 4 . 7 . 5 . 2
   . . 6 . 5 . 1 . .

  Flipped chip at R8C1 setting its value to <8>.

   Placed a <3> chip on R8C2.
   Placed a <9> chip on R8C8.
   Placed a <2> chip on R9C1.

  Bowman cycle 9:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . X
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   8 C 4 . 7 . 5 C 2
   C . 6 . 5 . 1 . .

  Flipped chip at R2C9 setting its value to <3>.

   Placed a <4> chip on R5C9.

  Bowman cycle 10:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . 3
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . C
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   8 X 4 . 7 . 5 C 2
   C . 6 . 5 . 1 . .

  Flipped chip at R8C2 setting its value to <3>.

   Placed a <1> chip on R8C6.

  Bowman cycle 11:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . 3
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . C
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   8 3 4 . 7 C 5 X 2
   C . 6 . 5 . 1 . .

  Flipped chip at R8C8 setting its value to <9>.

   Placed a <6> chip on R8C4.

  Bowman cycle 12:

   . . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . 3
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . C
   4 5 2 7 3 6 9 1 8
   1 . 9 . 8 . 3 . .
   8 3 4 C 7 C 5 9 2
   X . 6 . 5 . 1 . .

  Flipped chip at R9C1 setting its value to <2>.

   Placed a <7> chip on R9C2.
   Placed a <9> chip on R1C1.
   Placed a <9> chip on R3C1.
   Placed a <7> chip on R7C2.

  Final state:

   9 . 5 . 1 . 6 . .
   7 . 1 . 9 . 8 . 3
   9 . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . 4
   4 5 2 7 3 6 9 1 8
   1 7 9 . 8 . 3 . .
   8 3 4 6 7 1 5 9 2
   2 7 6 . 5 . 1 . .

  Both R9C2 and R7C2 are <7>.

Deduction pass 5; 35 squares solved; 46 remaining.

* Intersection of row 7 with block 8.
  The non-intersecting squares of the block
  cannot contain the values <1>.

   R8C6 - removing <1> from <13> leaving <3>.

Deduction pass 6; 36 squares solved; 45 remaining.

* R9C2 is the only square in row 9 that can be
  a <3>.  It is thus pinned to that value.

Deduction pass 7; 37 squares solved; 44 remaining.

* R7C2 is the only square in column 2 that can be
  a <7>.  It is thus pinned to that value.

Deduction pass 8; 38 squares solved; 43 remaining.

* Intersection of column 2 with block 1.
  The non-intersecting squares of the block
  cannot contain the values <24>.

   R1C1 - removing <2> from <289> leaving <89>.
   R3C1 - removing <2> from <1289> leaving <189>.

Deduction pass 9; 38 squares solved; 43 remaining.

* Found a contradiction by Bowman Bingo.  After 3
  cycles, it became clear that R7C4 could not be a
  <4>, because this would force both R8C7 and
  R9C7 to be <1>.

  As they are in the same column, this is not possible.

   R7C4 - removing <4> from <1246> leaving <126>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 X 8 . 3 . .
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R7C4 setting its value to <4>.

   Placed a <5> chip on R7C8.
   Placed a <6> chip on R7C9.
   Placed a <2> chip on R9C6.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 4 8 . 3 X C
   . . 4 . 7 3 . . 2
   . 3 . . 5 C . . .

  Flipped chip at R7C8 setting its value to <5>.

   Placed a <1> chip on R8C7.

  Bowman cycle 3:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 4 8 . 3 5 X
   . . 4 . 7 3 C . 2
   . 3 . . 5 C . . .

  Flipped chip at R7C9 setting its value to <6>.

   Placed a <2> chip on R7C1.
   Placed a <1> chip on R9C7.

  Final state:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   2 7 9 4 8 . 3 5 6
   . . 4 . 7 3 1 . 2
   . 3 . . 5 2 1 . .

  Both R8C7 and R9C7 are <1>.

Deduction pass 10; 38 squares solved; 43 remaining.

* Found a contradiction by Bowman Bingo.  After 3
  cycles, it became clear that R7C6 could not be a
  <4>, because this would force both R8C7 and
  R9C7 to be <1>.

  As they are in the same column, this is not possible.

   R7C6 - removing <4> from <124> leaving <12>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 X 3 . .
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R7C6 setting its value to <4>.

   Placed a <5> chip on R7C8.
   Placed a <6> chip on R7C9.
   Placed a <2> chip on R9C6.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 4 3 X C
   . . 4 . 7 3 . . 2
   . 3 . . 5 C . . .

  Flipped chip at R7C8 setting its value to <5>.

   Placed a <1> chip on R8C7.

  Bowman cycle 3:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 4 3 5 X
   . . 4 . 7 3 C . 2
   . 3 . . 5 C . . .

  Flipped chip at R7C9 setting its value to <6>.

   Placed a <2> chip on R7C1.
   Placed a <1> chip on R9C7.

  Final state:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   2 7 9 . 8 4 3 5 6
   . . 4 . 7 3 1 . 2
   . 3 . . 5 2 1 . .

  Both R8C7 and R9C7 are <1>.

Deduction pass 11; 38 squares solved; 43 remaining.

* Intersection of row 7 with block 9.
  The non-intersecting squares of the block
  cannot contain the values <4>.

   R9C8 - removing <4> from <4789> leaving <789>.
   R9C9 - removing <4> from <479> leaving <79>.

Deduction pass 12; 38 squares solved; 43 remaining.

* Found a contradiction by Bowman Bingo.  After 3
  cycles, it became clear that R8C8 could not be a
  <5>, because this would force both R9C7 and
  R7C9 to be <6>.

  As they are in the same block, this is not possible.

   R8C8 - removing <5> from <589> leaving <89>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . .
   . . 4 . 7 3 . X 2
   . 3 . . 5 . . . .

  Flipped chip at R8C8 setting its value to <5>.

   Placed a <1> chip on R8C7.
   Placed a <4> chip on R7C8.

  Bowman cycle 2:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 C .
   . . 4 . 7 3 X 5 2
   . 3 . . 5 . . . .

  Flipped chip at R8C7 setting its value to <1>.

   Placed a <6> chip on R9C7.

  Bowman cycle 3:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 X .
   . . 4 . 7 3 1 5 2
   . 3 . . 5 . C . .

  Flipped chip at R7C8 setting its value to <4>.

   Placed a <6> chip on R7C9.
   Placed a <3> chip on R5C8.

  Final state:

   . . . . 1 . . . .
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 4 6
   . . 4 . 7 3 1 5 2
   . 3 . . 5 . 6 . .

  Both R9C7 and R7C9 are <6>.

Deduction pass 13; 38 squares solved; 43 remaining.

* A set of 2 squares can be constrained.
  The following squares share possibilities <15>:

   R8C1
   R8C7

  No other squares in row 8 have those
  possibilities.  Thus, any additional possibilties
  they have can be eliminated.

   R8C1 - removing <68> from <1568> leaving <15>.
   R8C7 - removing <> from <15> leaving <15>.

Deduction pass 14; 38 squares solved; 43 remaining.

* Found a contradiction by Bowman Bingo.  After 7
  cycles, it became clear that R1C9 could not be a
  <3>, because this would force both R9C3 and
  R1C3 to be <6>.

  As they are in the same column, this is not possible.

   R1C9 - removing <3> from <379> leaving <79>.

  Here is a trace of the Bowman matrix as it developed.

   X = the current square (also an "C").
   C = squares with chips on them.
   . = squares that can still have more than one value.

  Bowman cycle 1:

   . . . . 1 . . . X
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . .
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . .
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R1C9 setting its value to <3>.

   Placed a <4> chip on R5C9.

  Bowman cycle 2:

   . . . . 1 . . . 3
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 . X
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . .
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R5C9 setting its value to <4>.

   Placed a <3> chip on R5C8.
   Placed a <6> chip on R7C9.

  Bowman cycle 3:

   . . . . 1 . . . 3
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 X 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . C
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R5C8 setting its value to <3>.

  Bowman cycle 4:

   . . . . 1 . . . 3
   7 . . . 9 . 8 . .
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . X
   . . 4 . 7 3 . . 2
   . 3 . . 5 . . . .

  Flipped chip at R7C9 setting its value to <6>.

   Placed a <1> chip on R2C9.
   Placed a <1> chip on R9C7.

  Bowman cycle 5:

   . . . . 1 . . . 3
   7 . . . 9 . 8 . X
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . 6
   . . 4 . 7 3 . . 2
   . 3 . . 5 . C . .

  Flipped chip at R2C9 setting its value to <1>.

   Placed a <5> chip on R2C3.

  Bowman cycle 6:

   . . . . 1 . . . 3
   7 . C . 9 . 8 . 1
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . 6
   . . 4 . 7 3 . . 2
   . 3 . . 5 . X . .

  Flipped chip at R9C7 setting its value to <1>.

   Placed a <6> chip on R9C3.
   Placed a <5> chip on R8C7.

  Bowman cycle 7:

   . . . . 1 . . . 3
   7 . X . 9 . 8 . 1
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . 6
   . . 4 . 7 3 C . 2
   . 3 C . 5 . 1 . .

  Flipped chip at R2C3 setting its value to <5>.

   Placed a <2> chip on R2C8.
   Placed a <6> chip on R1C3.

  Final state:

   . . 6 . 1 . . . 3
   7 . 5 . 9 . 8 2 1
   . . 3 . 6 . 4 . .
   3 1 7 8 4 9 2 6 5
   . . 8 . 2 . 7 3 4
   4 5 2 7 3 6 9 1 8
   . 7 9 . 8 . 3 . 6
   . . 4 . 7 3 5 . 2
   . 3 6 . 5 . 1 . .

  Both R9C3 and R1C3 are <6>.

Deduction pass 15; 38 squares solved; 43 remaining.

* 2 squares in column 9 form a simple locked pair.
  The following squares share possibilities <79>:

   R1C9
   R9C9

  Thus, possibilities <79> can be removed from
  the rest of the column.

   R3C9 - removing <79> from <179> leaving <1>.

Deduction pass 16; 39 squares solved; 42 remaining.

* R2C3 is the only square in row 2 that can be
  a <1>.  It is thus pinned to that value.

* Reconstraining R9C3 fixes its value at <6>.
* Reconstraining R1C3 fixes its value at <5>.
* Reconstraining R8C2 fixes its value at <8>.
* Reconstraining R9C7 fixes its value at <1>.
* Reconstraining R8C7 fixes its value at <5>.

* Reconstraining R1C7 fixes its value at <6>.
* Reconstraining R2C9 fixes its value at <3>.
* Reconstraining R5C9 fixes its value at <4>.
* Reconstraining R5C8 fixes its value at <3>.
* Reconstraining R7C9 fixes its value at <6>.
* Reconstraining R9C1 fixes its value at <2>.
* Reconstraining R8C8 fixes its value at <9>.
* Reconstraining R8C1 fixes its value at <1>.
* Reconstraining R7C8 fixes its value at <4>.
* Reconstraining R8C4 fixes its value at <6>.
* Reconstraining R9C9 fixes its value at <7>.
* Reconstraining R7C1 fixes its value at <5>.
* Reconstraining R9C6 fixes its value at <4>.
* Reconstraining R9C4 fixes its value at <9>.
* Reconstraining R1C9 fixes its value at <9>.
* Reconstraining R9C8 fixes its value at <8>.

* Reconstraining R1C1 fixes its value at <8>.

* Reconstraining R3C1 fixes its value at <9>.
* Reconstraining R1C6 fixes its value at <7>.
* Reconstraining R3C6 fixes its value at <8>.
* Reconstraining R1C8 fixes its value at <2>.
* Reconstraining R2C8 fixes its value at <5>.
* Reconstraining R1C2 fixes its value at <4>.
* Reconstraining R3C8 fixes its value at <7>.
* Reconstraining R2C6 fixes its value at <2>.
* Reconstraining R3C2 fixes its value at <2>.
* Reconstraining R5C1 fixes its value at <6>.
* Reconstraining R3C4 fixes its value at <5>.
* Reconstraining R5C4 fixes its value at <1>.
* Reconstraining R5C2 fixes its value at <9>.
* Reconstraining R5C6 fixes its value at <5>.
* Reconstraining R7C4 fixes its value at <2>.
* Reconstraining R2C4 fixes its value at <4>.
* Reconstraining R7C6 fixes its value at <1>.

* Reconstraining R2C2 fixes its value at <6>.
* Reconstraining R1C4 fixes its value at <3>.

Deduction pass 17; 81 squares solved; 0 remaining.

Solution found!
Deduction completed...

Back to top
View user's profile Send private message Visit poster's website AIM Address
Doug

Joined: 28 May 2005
Posts: 42
:

Items
PostPosted: Wed Jun 15, 2005 4:31 am    Post subject: Reply with quote

Actually, this implements exactly what I was suggesting in the reply before yours!

I would be remiss were I not to point out that the coloring algorithm is due to AMcK. I mearely described it after deducing the algorithm from the output of his code on this forum. (It is equivalent to the Fishy Cycles algorithm that I did do independantly, though.)

Anyway, I tried it out and I think that its more in line with SFC than with AMcK's coloring algorithm. His algorithm proceeds in a very deterministic way and considers only one value at a time. SFC considers many forced values. Same, of course, with this one.

A way that I think the algorithm can be made more "intelligent" is in the choices of which chips to flip while doing step 1. My thought is this: select a chip to flip whose row, column, and block intersect houses with the most chips, where the intersections themselves have the most unknown cells and cells without chips. This should maximizes the chance for finding a contradiction sooner.
_________________
Doug Bowman
www.flickr.com/photos/bistrosavage
Back to top
View user's profile Send private message Send e-mail
MadOverlord

Joined: 01 Jun 2005
Posts: 80
:
Location: Wilmington, NC, USA

Items
PostPosted: Wed Jun 15, 2005 4:48 am    Post subject: Reply with quote

A small optimization; you can place chips on squares that are pinned to single values (because no other square in the group can have that value). It turns out that Bowman Bingo generates as many pins as direct forces, and this makes it easier to find contradictions faster.

My program isn't being particularly smart. It just tries all the 2-possibility cells, then the 3's, and so on, going from TR to BL in the grid -- not looking at the context. It almost always finds a Bingo in the first couple of tries, though that nasty second challenge problem requires 10 tries before it finds a bingo.

A heuristic for deciding what squares to test first would be useful.

The chip-flip selection optimization sounds about like what I was going to try, and I'll code it tomorrow.
Back to top
View user's profile Send private message Visit poster's website AIM Address
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Sun Jun 19, 2005 7:08 am    Post subject: Reply with quote

My first order created logic algorithm solves this problem. Yet to workout how it solves it though.
Back to top
View user's profile Send private message
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