The New Sudoku Players' Forum

[Forerunner]

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?

[Animator]

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  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


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

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


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.)

[Carcul]

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

[Crazy Girl]

Post Deleted, irrelevent post

[Forerunner]

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.

[QBasicMac]

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

[tso]

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 pair

Therefore,
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.

[tarek]

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)


[Edit: oops, the step above had already been concluded]

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 Candidates
r9c2=3: r9c2=3 => r1c2=7
r9c2=5: r9c2=5 => r9c5=3 => r5c5=5 => r5c3=3 => r8c3=7 => r2c3=5 => r2c1=9 => r3c1=3 => r1c2=7
Threfore r1c2=7


& singles from there,

Tarek

[vidarino]

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

[Camchase]

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

Camchase

[Forerunner]

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.

[NeilB]

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