Is there a fish in here?

Advanced methods and approaches for solving Sudoku puzzles

Is there a fish in here?

Postby Sudtyro » Tue Jan 16, 2007 4:46 pm

The following 6’s candidate grid came up in a recent puzzle after running through the basics. I count five strong links, but see no loops or obvious chains. Is there a fish in this bowl? Sure seems hard to spot the patterns. Other single-digit methods?

Code: Select all
. . 6 | . . . | 6 6 .
. 6 6 | . . . | . 6 6
. . . | . . . | . . .
------+-------+------
. . . | . . 6 | . 6 6
6 . 6 | . . . | . 6 .
6 . 6 | . . 6 | . . 6
------+-------+------
6 . . | . . . | 6 . .
6 6 6 | . . . | . . 6
. . . | . . . | . . .
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Postby Ruud » Tue Jan 16, 2007 11:34 pm

I did a pattern check on your grid, but there is no fish nor any other single-digit technique available.

Ruud
Ruud
 
Posts: 664
Joined: 28 October 2005

Pattern check for FISH

Postby Sudtyro » Wed Jan 17, 2007 1:39 pm

Is the "pattern check" a machine algorithm, or is it something that can be done manually?
Sudtyro
 
Posts: 68
Joined: 21 December 2006

Re: Pattern check for FISH

Postby ravel » Wed Jan 17, 2007 4:53 pm

Sudtyro wrote:Is the "pattern check" a machine algorithm, or is it something that can be done manually?
Doing it manually is cumbersome. One way is to find valid templates and "exclude" those digits, e.g. you can start following:
if one of A or B is true, there is always a valid pattern for the digits marked with +
Code: Select all
 . . 6 | . . . |+6 6 .
 .+6 6 | . . . | . 6 6
 . . . | . . . | . . .
 ------+-------+------
 . . . | . . B | . A 6
 6 . A | . . . | . B .
 6 . B | . . A | . . 6
 ------+-------+------
 6 . . | . . . | 6 . .
+6 6 6 | . . . | . .+6
 . . . | . . . | . . .
Now i write 9 for digits, that cannot be eliminated. Assume that A or B and C or D is true.
Code: Select all
 . . C | . . . | 9 D .
 . 9 D | . . . | . C 6
 . . . | . . . | . . .
 ------+-------+------
 . . . | . . A | . 9 B
+6 . 9 | . . . | . 9 .
 6 . 9 | . . B | . . A
 ------+-------+------
 6 . . | . . . |+6 . .
 9+6 6 | . . . | . . 9
 . . . | . . . | . . .
now six 6's are left to check
Code: Select all
 . .+9 | . . . | 9 9 .
 . 6 9 | . . . | . 9+6
 . . . | . . . | . . .
 ------+-------+------
 . . . | . .+9 | . 9 9
 9 . 9 | . . . | .+9 .
+6 . 9 | . . 6 | . . 9
 ------+-------+------
 6 . . | . . . |+9 . .
 9+9 6 | . . . | . . 9
 . . . | . . . | . . .
now four
Code: Select all
 . . 9 | . . . |+9 9 .
 .+6 9 | . . . | . 9 9
 . . . | . . . | . . .
 ------+-------+------
 . . . | . . 9 | .+9 9
 9 .+9 | . . . | . 9 .
 9 . 9 | . .+6 | . . 9
 ------+-------+------
+6 . . | . . . | 9 . .
 9 9 6 | . . . | . .+9
 . . . | . . . | . . .
and a last one
Code: Select all
 . . 9 | . . . | 9+9 .
 .+9 9 | . . . | . 9 9
 . . . | . . . | . . .
 ------+-------+------
 . . . | . . A | . 9 B
+9 . 9 | . . . | . 9 .
 9 . 9 | . . B | . . A
 ------+-------+------
 9 . . | . . . |+9 . .
 9 9+6 | . . . | . . 9
 . . . | . . . | . . .


Of course this is not an optimal way, better methods ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby udosuk » Thu Jan 18, 2007 8:44 am

I think a pattern check means you just trial and error each digit in the pattern and see if the placement of any digit will prevent other digits to be placed validly (each row/column/box should have exactly one of that digit placed)...

For this particular pattern, only a total of 23 digits to test, so shouldn't be too hard manually (particularly if you use a solver program such as Simple Sudoku to help)... I'd say it takes less than 0.5ms with Ruud's program...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Obi-Wahn » Thu Jan 18, 2007 9:36 am

Not exactly. A template ceck means to generate all possible complete solutions for a single digit (46656 for an empty grid). Then you combine them to find any candidate that isn't part of at least one solution.

In your case there are 12 different complete solutions for digit 6 and every candidate is part of at least one of them. So there is no exclusion possible.
User avatar
Obi-Wahn
 
Posts: 61
Joined: 05 January 2007
Location: Darmstadt, Germany


Return to Advanced solving techniques