## I'm stumped

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

### I'm stumped

HI, I am making a sudoku solving program just for fun, but I've come across a bump in the road with a certain puzzle.

My program implements the basic stuff, as well as naked pairs, hidden pairs, and intersection removal (terms I got from this site: http://www.scanraid.com/sudoku.htm).

The sudoku that I've found to stump my program is this: http://www.sudoku.org.uk/DailySudoku.asp?day=15/01/2006

When I run my program, it can only get to the following point:

What solving tricks (without random guessing!) are out there that I could incorporate into my program? And what in this puzzle could I do to get any further?
Forerunner

Posts: 3
Joined: 18 January 2006

First: a text version of the grid: (Benefits of a text version: loads faster, easier to modify (read: ccopy and paste), will exists as long as the thread exist (for example: if you remove your image then this thread is useless.)

Code: Select all
`2   37   8   | 9   6   5  | 4  37  159  6    57  | 4   1   3  | 2  79  839  1    4   | 8   2   7  | 5  39  6-------------+------------+----------35  2    1   | 35  4   9  | 8  6   77   8    35  | 2   35  6  | 9  1   4 6   4    9   | 1   7   8  | 3  5   2-------------+------------+----------4   9    6   | 35  8   1  | 7  2   358   357  37  | 6   9   2  | 1  4   351   35   2   | 7   35  4  | 6  8   9`

A technique you can use to get a next move: simple colouring.

Code: Select all
`2   37   8   | 9   6   5  | 4  37  159  6    57  | 4   1   3  | 2  79  839  1    4   | 8   2   7  | 5  39  6-------------+------------+----------35  2    1   | 35  4   9  | 8  6   77   8    35+ | 2   35- 6  | 9  1   4 6   4    9   | 1   7   8  | 3  5   2-------------+------------+----------4   9    6   | 35  8   1  | 7  2   358   357  37- | 6   9   2  | 1  4   351   35   2   | 7   35+ 4  | 6  8   9`

Colouring the 3s:

r5c5 is the opposite of r5c3.
r8c3 is the opposite of r5c3
r9c5 is the opposite of r5c5. (in other words: r9c5 is the same as r5c3).

r9c2 sees both a + (row 9) and a - (box 7) and therefore it cannot have the number 3.

In case you don't see the logic:

Or: r5c5 = 3 ==> r9c5 = 3 ==> r9c2 <> 3.
Or: r5c5 <>3 ==> r8c3 = 3 ==> r9c2 <> 3.

Update: fixed the explanation. Thanks Crazy Girl. (It used to say 'opposite of r5c2' instead of r5c3.)
Last edited by Animator on Wed Jan 18, 2006 8:46 pm, edited 2 times in total.
Animator

Posts: 469
Joined: 08 April 2005

A much more simpler technique that can be used is the BUG principle: in order for the puzzle have just one solution, r8c2 must be "3" and the puzzle is solved.

Carcul
Carcul

Posts: 724
Joined: 04 November 2005

Post Deleted, irrelevent post
Crazy Girl

Posts: 189
Joined: 08 November 2005

Thanks for all the help guys.

However, is coloring the only good way to approach this problem? It seems too wishy-washy for my tastes.
Forerunner

Posts: 3
Joined: 18 January 2006

Forerunner wrote:too wishy-washy for my tastes

Maybe this seems less "wishy-washy" (Same thing without mentioning colors)

r5c5=3 means r5c3<>3 means r8c3=3
But then there is no place for 3 on row 9
Thus r7c5<>3

Mac
QBasicMac

Posts: 441
Joined: 13 July 2005

I agree with Carcul that the best solution is BUG:

If your Sudoku has ONE cell with THREE candidates and all other undecided cells have TWO candidates -- you can immediately fill that three-candidate cell. Just check which candidate appears THREE TIMES in the row, column or box in which this three-candidate cell resides. That candidate is the one that goes in the three candidate cell.

More on BUG here.

But there are many other non-wishy-washy choices:

Code: Select all
`2   37   8   | 9   6   5  | 4  37  1 59  6    57  | 4   1   3  | 2  79  8 39  1    4   | 8   2   7  | 5  39  6 -------------+------------+---------- 35  2    1   | 35  4   9  | 8  6   7 7   8   [35] | 2  [35] 6  | 9  1   4 6   4    9   | 1   7   8  | 3  5   2 -------------+------------+---------- 4   9    6   | 35  8   1  | 7  2   35 8   357  x37 | 6   9   2  | 1  4   35 1  [35]  2   | 7  [35] 4  | 6  8   9 `

Examine the cells in brackets:

Code: Select all
`r9c2 + r9c5 form a naked pair       r9c5 + r5c5 form a naked pair              r5c5 + r5c3 form a naked pairTherefore, r9c2           +     r5c3 form a remote naked pair.`

You may exclude all 3s and 5s from any cells that can *see* both of these cells, that is, r8c3<>3.

This sequence of 5 cells can also be thought of as either bivalue loop OR a bilocation loop making the same exclusion.

Actually, once you've reduced the puzzle to this point where nearly all cells are bivalue -- nearly every where you look you'll find another solution, an xy-wing or forcing chain or loop. There are maybe a half a dozen forcing chains of various lengths that will finish off this puzzle.
tso

Posts: 798
Joined: 22 June 2005

Code: Select all
`*-----------------------------------------------*| 2    37   8   | 9    6    5   | 4    37   1   || 59   6    57  | 4    1    3   | 2    79   8   || 39   1    4   | 8    2    7   | 5    39   6   ||---------------+---------------+---------------|| 35   2    1   | 35   4    9   | 8    6    7   || 7    8    35  | 2    35   6   | 9    1    4   || 6    4    9   | 1    7    8   | 3    5    2   ||---------------+---------------+---------------|| 4    9    6   | 35   8    1   | 7    2    35  || 8    357  357 | 6    9    2   | 1    4    35  || 1    35   2   | 7    35   4   | 6    8    9   |*-----------------------------------------------*Eliminating 5 From r8c3 (Column 2 & Box 7 Box-line interaction)`

Code: Select all
`*-----------------------------------------------*| 2    37   8   | 9    6    5   | 4    37   1   || 59   6    57  | 4    1    3   | 2    79   8   || 39   1    4   | 8    2    7   | 5    39   6   ||---------------+---------------+---------------|| 35   2    1   | 35   4    9   | 8    6    7   || 7    8    35  | 2    35   6   | 9    1    4   || 6    4    9   | 1    7    8   | 3    5    2   ||---------------+---------------+---------------|| 4    9    6   | 35   8    1   | 7    2    35  || 8    357  37  | 6    9    2   | 1    4    35  || 1    35   2   | 7    35   4   | 6    8    9   |*-----------------------------------------------*Candidates in r9c2 will force r1c2 to have only 7 as valid Candidatesr9c2=3: r9c2=3 => r1c2=7r9c2=5: r9c2=5 => r9c5=3 => r5c5=5 => r5c3=3 => r8c3=7 => r2c3=5 => r2c1=9 => r3c1=3 => r1c2=7Threfore r1c2=7`

& singles from there,

Tarek
Last edited by tarek on Thu Jan 19, 2006 7:13 am, edited 1 time in total.

tarek

Posts: 2644
Joined: 05 January 2006

There is also a Turbot Fish in 3s in the latter of tarek's grids, which eliminates 3 from R8C3.

To Forerunner; I suggest you add Turbot Fish (or even better; general X-cycles) to your solver. It's a powerful tool, and the patterns (or cycles) can crack a lot of otherwise inpenetrable puzzles.

Vidar
vidarino

Posts: 295
Joined: 02 January 2006

R8,9C2 provides a locked candidate with 5's - removing the 5 from R8C3. After that the BUG will apply. Very simple.

Camchase
Camchase

Posts: 30
Joined: 03 January 2006

vidarino wrote:To Forerunner; I suggest you add Turbot Fish (or even better; general X-cycles) to your solver. It's a powerful tool, and the patterns (or cycles) can crack a lot of otherwise inpenetrable puzzles.

Thanks for the advice. I'll look into thost methods and see what I find.
Forerunner

Posts: 3
Joined: 18 January 2006

vidarino wrote:To Forerunner; I suggest you add Turbot Fish (or even better; general X-cycles) to your solver. It's a powerful tool, and the patterns (or cycles) can crack a lot of otherwise inpenetrable puzzles.
This may not be the right place to ask this question but, is there a listing somewhere of all the Sudoku solvers that have been built by members of these forums? I've seen mention of many of them and would like to follow a URL or two to check them out.

-Neil
NeilB

Posts: 8
Joined: 22 January 2006