Smallest nontrivial configuration?

Everything about Sudoku that doesn't fit in one of the other sections

Smallest nontrivial configuration?

Postby Pink Pig » Thu Mar 02, 2006 7:36 pm

Yesterday's USA Today puzzle (http://puzzles.usatoday.com/sudoku/archive/2006/03/01/) quickly leads to the following configuration:

Code: Select all
Grid:
 *-----------*
 |.6.|154|928|
 |425|968|731|
 |...|732|654|
 |---+---+---|
 |..2|641|873|
 |...|579|162|
 |176|283|495|
 |---+---+---|
 |...|316|289|
 |2..|897|546|
 |689|425|317|
 *-----------*

Candidates:
 *--------------------------------------------------*
 | 37   6    37   | 1    5    4    | 9    2    8    |
 | 4    2    5    | 9    6    8    | 7    3    1    |
 | 89   19   18   | 7    3    2    | 6    5    4    |
 |----------------+----------------+----------------|
 | 59   59   2    | 6    4    1    | 8    7    3    |
 | 38   34   348  | 5    7    9    | 1    6    2    |
 | 1    7    6    | 2    8    3    | 4    9    5    |
 |----------------+----------------+----------------|
 | 57   45   47   | 3    1    6    | 2    8    9    |
 | 2    13   13   | 8    9    7    | 5    4    6    |
 | 6    8    9    | 4    2    5    | 3    1    7    |
 *--------------------------------------------------*


and if you drop this into Simple Sudoku and ask for a hint, it will tell you "No hint available". This is the smallest configuration (15 open cells) I have yet encountered for which elementary methods (i.e. the methods known to Simple Sudoku) are of no avail.

It has some interesting properties: there is only one "abundant" digit, namely 3, and one "abundant" cell, namely r5c3. If it were possible to remove the 3 as a candidate from r5c3, then the remaining cells would either have no solution or more than one solution. The easiest way to see this is to note that if the reduced candidate matrix has a solution, then there must be a second solution created by replacing each digit selected in the open cells by its alternative. Thus, if there is a unique solution, r5c3 must be a 3, which is indeed the case.

I'm pretty sure that there are several other ways of solving this grid. Can anyone suggest one which is simpler (preferably not relying on uniqueness arguments)?
Pink Pig
 
Posts: 1
Joined: 02 March 2006

Postby ravel » Fri Mar 03, 2006 9:26 am

This is the well known BUG principle, with one glance you can say that r5c3 must be 3 (there is only 1 cell with 3 candidates and the 3 can be found 2 more times in the same row and column)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby vidarino » Fri Mar 03, 2006 9:41 am

The following Nice Loop cracks the puzzle:
R1C1=3=R1C3=7=R7C3=4=R5C3=8=R5C1=3=R1C1 -> R1C1=3

I generally think XY-Chains are easier to follow, though, despite being a tad longer:
R1C1-7-R1C3-3-R8C3-1-R8C2-3-R5C2-4-R7C2-5-R7C1-7-R1C1 -> R1C1 <> 7

(Meaning that if you stick a 7 in R1C1 you would end up with a 7 in R7C1 as well - two 7s in one column.)

Vidar
vidarino
 
Posts: 295
Joined: 02 January 2006

Re: Smallest nontrivial configuration?

Postby Smythe Dakota » Sat Mar 04, 2006 4:13 pm

Pink Pig wrote:.... If it were possible to remove the 3 as a candidate from r5c3, then the remaining cells would either have no solution or more than one solution. The easiest way to see this is to note that if the reduced candidate matrix has a solution, then there must be a second solution created by replacing each digit selected in the open cells by its alternative. Thus, if there is a unique solution, r5c3 must be a 3, which is indeed the case. ....

This is "meta-reasoning", which some would object to. A purist would insist that part of the task in solving a puzzle is to establish uniqueness.

Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Re: Smallest nontrivial configuration?

Postby tso » Sun Mar 05, 2006 3:12 am

Smythe Dakota wrote:
Pink Pig wrote:.... If it were possible to remove the 3 as a candidate from r5c3, then the remaining cells would either have no solution or more than one solution. The easiest way to see this is to note that if the reduced candidate matrix has a solution, then there must be a second solution created by replacing each digit selected in the open cells by its alternative. Thus, if there is a unique solution, r5c3 must be a 3, which is indeed the case. ....

This is "meta-reasoning", which some would object to. A purist would insist that part of the task in solving a puzzle is to establish uniqueness.

Bill Smythe


Of course, many (actually most) of us purists absolutely disagree. I've been solving Sudoku and other logic puzzles for decades -- it would never have occured to me to prove that the composer of the puzzle didn't make a blunder or typo. "If 'this' were 'that', then the puzzle is unsolvable, therefore 'this' cannot be 'that'." -type logic is a staple of solving puzzles including DOMINOS, BATTLESHIPS and many, many others.

It it's never the 'purists' who object to this type of logic -- its always the the logic-puzzle-novice, the puzzle solver who never attempted a logic puzzle until Sudoku became ubiquitious, a solver who often believes that some Sudokus simply cannot be solved without guessing or trial and error.

Us 'purists', for whom Sudoku is just one of hundreds of grid based logic puzzles laugh - ha - at the idea that one perfectly good logical tactic is set aside by some as voodoo logic. Similar arguments have been carried on in this forum about other tactics including xy-wings, coloring and forcing chains -- all of which were labled as no better than guessing or trial and error by some -- but not by 'purists'.
tso
 
Posts: 798
Joined: 22 June 2005


Return to General

cron