## Stuck on this one

Post the puzzle or solving technique that's causing you trouble and someone will help

### Stuck on this one

I got bit by the sudoku bug about 2 weeks ago and one of the first things I did
was to write a simple program to solve them using the same logic as I would
when solving (i.e. no brute force searching). The 3rd example I picked to test
my program completely stumped it.

I've been trying to solve it myself for the last 2 weeks and I've progressed
this far:

Code: Select all
` *-----------*  |..1|9.7|..8|  |6..|185|73.|  |..7|46.|1..|  |---+---+---|  |.34|.9.|...|  |...|5.4|...|  |...|.1.|42.|  |---+---+---|  |..5|.71|9..|  |.1.|84.|..7|  |7..|.59|2..|  *-----------* `

Code: Select all
` {345}   {245}   {1}     {9}     {23}    {7}     {56}    {456}   {8}  {6}     {249}   {29}    {1}     {8}     {5}     {7}     {3}     {249}  {23589} {2589}  {7}     {4}     {6}     {23}    {1}     {59}    {259}  {1258}  {3}     {4}     {267}   {9}     {268}   {568}   {1567}  {156}  {1289}  {26789} {2689}  {5}     {23}    {4}     {368}   {1679}  {1369}  {589}   {56789} {689}   {367}   {1}     {368}   {4}     {2}     {3569}  {248}   {2468}  {5}     {236}   {7}     {1}     {9}     {48}    {36}  {29}    {1}     {2369}  {8}     {4}     {236}   {356}   {56}    {7}  {7}     {468}   {368}   {36}    {5}     {9}     {2}     {148}   {14}   `

but cannot see any way forward from here. I already have the solution for the
complete grid but I would really like to know if it is posible to solve by logic
alone or whether it is a badly formed puzzle that requires some guesswork in
order to be solved.

Can anybody see something glaringly obvious that I am just not seeing ?

--
Glenn
Glenn

Posts: 4
Joined: 03 September 2005

### Re: Stuck on this one

Glenn wrote:Can anybody see something glaringly obvious that I am just not seeing ?

No.
angusj

Posts: 306
Joined: 12 June 2005

Glenn,

This scarcely counts as glaringly obvious, but the chain-searching routine on my solver comes back with:

1. Consider the chains (4,4)-2-(7,4)-3-(7,9)~3~(5,9) and (4,4)~2~(5,5)~3~(5,9).
When the cell (5,9) contains the value 3, one chain states that the cell (4,4) contains the value 2 while the other says it doesn't - a situation that is clearly illegal.
Therefore, the cell (5,9) cannot contain the value 3.
- The move (5,9):=3 has been eliminated.
Consider the chains (3,1)~9~(3,8)~5~(8,8)~6~(8,6), (3,1)~9~(8,1)~2~(8,6) and (3,1)-3-(3,6)~3~(8,6).
Whichever of the 3 candidate values fills the cell (8,6), the cell (3,1) does not contain the value 9.
- The move (3,1):=9 has been eliminated.
Consider the chains (1,1)~4~(1,8)-4-(2,9)-2-(3,9)~2~(3,6), (1,1)-3-(1,5)-2-(3,6)~2~(3,1), (1,1)-3-(1,5)-2-(3,6)~2~(3,2) and (1,1)-3-(1,5)-2-(3,6)~2~(3,9).
Whichever of the 4 candidates in Row 3 contains the value 2, the cell (1,1) does not contain the value 4.
- The move (1,1):=4 has been eliminated.
The cell (7,1) is the only candidate for the value 4 in Column 1.
2. The value 8 is the only candidate for the cell (7,8).
3. Consider the chains (5,2)~2~(7,2)~6~(7,9)-3-(6,9) and (5,2)~2~(5,5)-3-(5,7)-3-(6,9).
When the cell (5,2) contains the value 2, one chain states that the cell (6,9) contains the value 3 while the other says it doesn't - a situation that is clearly illegal.
Therefore, the cell (5,2) cannot contain the value 2.
- The move (5,2):=2 has been eliminated.
Consider the chains (5,3)~2~(2,3)~9~(8,3), (4,1)~2~(8,1)-9-(8,3) and (5,1)~2~(8,1)-9-(8,3).
Whichever of the 3 candidates in Box [2,1] contains the value 2, the cell (8,3) does not contain the value 9.
- The move (8,3):=9 has been eliminated.
The cell (8,1) is the only candidate for the value 9 in Row 8.
4. Consider the chains (6,4)~3~(9,4)-3-(9,3)-3-(8,3), (6,6)~3~(3,6)~2~(8,6)-2-(8,3) and (6,9)-3-(5,7)-3-(8,7)~3~(8,3).
Whichever of the 3 candidates in Row 6 contains the value 3, the cell (8,3) does not contain the value 3.
- The move (8,3):=3 has been eliminated.
The cell (9,3) is the only candidate for the value 3 in Column 3.

Easy from here.

Where did you find the puzzle?
Sue De Coq

Posts: 93
Joined: 01 April 2005

Sue De Coq wrote:Glenn,
This scarcely counts as glaringly obvious, but the chain-searching routine on my solver comes back with:

Your algorithm is effective, Sue! Very impressive!

I believed I found the solution using a different method, but it turned out the argument was not valid.... (stuff deleted)
Last edited by Ocean on Sat Sep 03, 2005 2:38 pm, edited 1 time in total.
Ocean

Posts: 442
Joined: 29 August 2005

Im very new to both sudoku and forums so please bear with me.
Looking at your problem and knowing nothing about codes etc should there not be a 2 in the top left hand square making 2345.Also square middle right hand side 1678, the one above 15678 bottom right square to middle 468 top right 346 bottom middle 1468 and bottom right 1346. all differ with your code.If you are running some type of computer programme to try and solve it I wondered if the missing numbers could be part of it.

The fitter
thefitter

Posts: 2
Joined: 03 September 2005

Sue De Coq wrote:
This scarcely counts as glaringly obvious, but the chain-searching routine on my solver comes back with:

Congratulations, that is some solver you have there. It proves that it definitely can be solved without needing to guess.

Not taking anything away from your solution, but I was hoping for a pointer to some pattern or rule that I could use on future puzzles. I'm not sure that the deductions your solver has found help on that front. I know I wouldn't have been able to spot the chains myself.

Where did you find the puzzle?

I'm not 100% sure where I found it. I think it was from one of the daily newpapers left in the canteen at work but I could be wrong about that. I seem to recall there were 3 puzzles on the same page, labelled easy, tough and diabolical, if that helps to narrow it down. That was the tough one - I haven't dared look too closely at the diabolical one yet

P.S. I'm curious. What language is your solver written in ?

--
Glenn
Glenn

Posts: 4
Joined: 03 September 2005

thefitter wrote:Im very new to both sudoku and forums so please bear with me.
Looking at your problem and knowing nothing about codes etc should there not be a 2 in the top left hand square making 2345.

I eliminated the 2 in r1c1 by looking at the only 2 places that could be a 2 in column 5:

if r1c5==2 then r1c1<>2
if r5c5==2 then r4c1==2 and r1c1<>2

Also square middle right hand side 1678, the one above 15678 bottom right square to middle 468 top right 346 bottom middle 1468 and bottom right 1346. all differ with your code.

I don't quite follow which squares you're talking about there but I don't think I've eliminated any candidates incorrectly.

If you are running some type of computer programme to try and solve it I wondered if the missing numbers could be part of it.

No, my program wasn't up to the task so I was trying to solve it myself to see if there were some rules I use that I hadn't included in my program.

--
Glenn
Glenn

Posts: 4
Joined: 03 September 2005

The Fitter,

Glenn made some basic deductions on the initial puzzle before he wrote out the list of candidates for each cell in the grid. From the initial position, my solver suggests:

The value 3 in Box [3,1] must lie in Column 3.
- The moves (7,1):=3 and (8,1):=3 have been eliminated.
The value 8 in Box [2,3] must lie in Column 7.
- The moves (4,8):=8 and (5,8):=8 have been eliminated.
Consider the chains (1,8)~4~(1,1)-4-(7,1)~4~(7,9) and (1,8)-4-(2,9)~4~(7,9).
When the cell (7,9) contains the value 4, one chain states that the cell (1,8) contains the value 4 while the other says it doesn't - a situation that is clearly illegal.
Therefore, the cell (7,9) cannot contain the value 4.
- The move (7,9):=4 has been eliminated.
The values 1, 4 and 8 occupy the cells (7,8), (9,8) and (9,9) in some order.
- The moves (7,8):=6, (9,8):=6, (9,9):=3 and (9,9):=6 have been eliminated.

Since none of the moves listed as eliminated by the solver appears in the grid written out by Glenn, it's almost certain he made the same deductions himself.

Glenn,

The software is written in Java. Source is available at http://sf.net/projects/sudoku (GPL) and an applet is hosted at http://act365.com/sudoku. I took the log from a beta version of the next release - the current release won't do such a good job. Solve time is about 0.5s.

The Daily Telegraph used the term 'Diabolical' to describe puzzles that (in the opinion of the author) could only be solved through trial-and-error. With this in mind, I reran my solver with the chain-searching routines disabled. After 0.03s (i.e. much faster than before - chain-analysis is very slow), it came back with:

The value 3 in Box [3,1] must lie in Column 3.
- The moves (7,1):=3 and (8,1):=3 have been eliminated.
The value 8 in Box [2,3] must lie in Column 7.
- The moves (4,8):=8 and (5,8):=8 have been eliminated.
The cell (5,5) is one of 2 candidates for the value 2 in Column 5.
The value 3 is the only candidate for the cell (5,5).

The rest of the puzzle follows easily from here. The question is - how long would it have taken you to discover that the move (5,5):=2 leads to contradiction? The answer is 9 moves - quite a few if you only have the newspaper, a pencil and an eraser.

1. The value 3 is the only candidate for the cell (1,5).
2. The value 2 is the only candidate for the cell (3,6).
3. The cell (4,1) is the only candidate for the value 2 in Row 4.
4. The cell (1,2) is the only candidate for the value 2 in Row 1.
5. The value 9 is the only candidate for the cell (2,3).
6. The value 4 is the only candidate for the cell (2,2).
7. The value 5 is the only candidate for the cell (1,1).
8. The value 8 is the only candidate for the cell (3,2).
9. The value 6 is the only candidate for the cell (7,2).

It's hard to escape the conclusion that this puzzle is too difficult for a newspaper.
Sue De Coq

Posts: 93
Joined: 01 April 2005

ummm shouldnt the top left box have a 2 in it for the candidate list??? or am i missing something?

bodkinz
bodkinz

Posts: 2
Joined: 02 September 2005

sorry for a second post.. also bottom right cell.. top middle is missing a 6, top left is missing a 4, bottom middle is missing a 6 and bottom right is missing a 3 and 6 from the candidate list..

bodkinz
bodkinz

Posts: 2
Joined: 02 September 2005

### Re: Stuck on this one

Glenn wrote:but cannot see any way forward from here. I already have the solution for the
complete grid but I would really like to know if it is posible to solve by logic
alone or whether it is a badly formed puzzle that requires some guesswork in
order to be solved.

It's a well-formed puzzle with a unique solution.
Ultracolouring solves it logically.

{1,1}=4 excludes {1,1}=3 in {1,1}
{1,5}=3 excludes {1,5}=2 in {1,5}
{3,6}=2 excludes {3,9}=2 in row 3
{2,9}=2 excludes {2,9}=4 in {2,9}
{1,8}=4 excludes {1,1}=4 in row 1
{2,9}=2 excludes {2,9}=4 conjugates {1,8}=4 excludes {1,1}=4 so {2,9}=2 excludes {1,1}=4
{3,6}=2 excludes {3,9}=2 conjugates {2,9}=2 excludes {1,1}=4 so {3,6}=2 excludes {1,1}=4
{1,5}=3 excludes {1,5}=2 conjugates {3,6}=2 excludes {1,1}=4 so {1,5}=3 excludes {1,1}=4
{1,1}=4 excludes {1,1}=3 conjugates {1,5}=3 excludes {1,1}=4 so {1,1}=4 excludes {1,1}=4
{1,1}<>4 implies {7,1}=4
{7,1}=4 implies {9,2}<>4
Reduction: in {9,2} before=468 after=68

Verity: {7,2}=2, {7,2}=4, {7,2}=6, {7,2}=8 all imply {9,2}<>6
Reduction: {9,2}<>6 before=68 after=8

Simple
Regards
Andrew
Last edited by AMcK on Sun Sep 04, 2005 4:36 am, edited 1 time in total.
AMcK

Posts: 7
Joined: 30 June 2005

### Re: Stuck on this one

AMcK wrote:Simple

Not!
angusj

Posts: 306
Joined: 12 June 2005

Message cancelled.
Last edited by Jeff on Sun Sep 04, 2005 8:56 am, edited 1 time in total.
Jeff

Posts: 708
Joined: 01 August 2005

Jeff wrote:Using general forcing chain notation:
r7c8=8 => r9c9=4
r7c8=4 => r7c1<>4 => r1c1=4 => r1c5=3 => r3c6=2 => r3c9<>2 => r2c9=2 => =>r9c9=4
Therefore r9c9=4.

I don't follow your logic. As far as I can see r7c8=8 still leaves r9c9=[14]. And I believe that the solution actually has r9c8=4 rather than r9c9.

Interestingly, if you set r9c8=4 that does provide enough information to solve the puzzle using conventional techniques. Did you mean to prove r9c8=4 instead of r9c9=4 ?
Glenn

Posts: 4
Joined: 03 September 2005

Thanks Glenn

I guess it's wrong then. Back to the drawing board.
Jeff

Posts: 708
Joined: 01 August 2005

Next