Could someone tell me ...

Advanced methods and approaches for solving Sudoku puzzles

Could someone tell me ...

Postby kernparker » Sun Sep 18, 2005 1:57 pm

... why this won't work all the time? (It works most of the time, but Wayne Gould has confirmed that it won't work all of the time)

It is my conjecture that this straightforward, brute force approach should work:

Pencilmark every unpopulated small square with every digit that could occur there, all digits except those that occur in the small square's row, column, or 3x3 square. (This is admittedly a tedious process, subject to error, but if you're careful you can do it accurately.)

I submit that, because the puzzle has a unique solution, there now MUST EXIST a row, a column, or a 3x3 square in which some pencilmarked digit occurs only once. That digit must populate that small square. So you put the digit in the small square and then, importantly, remove any pencilmarked versions of that digit from the small square's row, column, and 3x3 square.

On you go, continuing to find unique pencilmarked occurrences within a row, column, or 3x3 square, until the puzzle is solved. It's brute force, but it seems like that it must work.

And it has worked, every time I've tried it until last night.

But now, I've got a puzzle that I think disproves my conjecture. I have filled lots of empty cells, and am now facing a situation in which I do not have a row, a column, or a 3x3 square in which there is a unique pencilmarked occurrence. I can make one guess and solve the puzzle easily using the above method, but you should never have to guess. I have triple-checked everything, and I don't think I've made any pencilmark mistakes.

I'd appreciate any insights from the Sudoku community ...

Kern Parker
Asheville, NC
kernparker
 
Posts: 1
Joined: 18 September 2005

Postby Nick67 » Sun Sep 18, 2005 3:03 pm

Hi Kern,

It is my conjecture that this straightforward, brute force approach should work:


I'm afraid that your conjecture ... is false. But I hope to convince you that this is a good thing!

But now, I've got a puzzle that I think disproves my conjecture.


Here is another example puzzle that also disproves it:

Code: Select all
 *-----------*
 |..9|2.8|.4.|
 |8..|..9|7..|
 |..1|...|...|
 |---+---+---|
 |...|.37|..1|
 |24.|...|.58|
 |1..|84.|...|
 |---+---+---|
 |...|...|8..|
 |..3|6..|..4|
 |.7.|9.3|6..|
 *-----------*


 ... with these values or candidates in each cell:

{3567}  {56}    {9}     {2}     {567}   {8}     {1}     {4}     {356}   
{8}     {256}   {246}   {34}    {1}     {9}     {7}     {36}    {2356} 
{34567} {256}   {1}     {347}   {567}   {45}    {25}    {8}     {9}     
{69}    {689}   {68}    {5}     {3}     {7}     {4}     {2}     {1}     
{2}     {4}     {7}     {1}     {9}     {6}     {3}     {5}     {8}     
{1}     {3}     {5}     {8}     {4}     {2}     {9}     {67}    {67}   
{4569}  {12569} {246}   {47}    {257}   {145}   {8}     {379}   {2357} 
{59}    {12589} {3}     {6}     {2578}  {15}    {25}    {79}    {4}     
{45}    {7}     {248}   {9}     {258}   {3}     {6}     {1}     {25}   



In Sudoku jargon, the puzzle has no "naked singles" (cells with just 1 candidate) and no "hidden singles" (cells containing a candidate that appears just once in that cell's row, column, or square).

The good news is that there are other patterns to search for.

Consider r8c7 and r9c9. Both cells contain the candidates 2 5. (This pattern is called a naked pair). Since one cell must contain a 2, and the other must contain a 5, we can safely eliminate 2 and 5 as candidates from each other cell in the same 3 x 3 box. In particular, we can eliminate 2 and 5 as candidates for r7c9.

And then there are other patterns we can find in this puzzle. Each time we find a pattern, we can eliminate more candidates. Eventually, there will be a cell with a naked or hidden single. We can then safely enter that value in the cell, and as you describe, remove that value as a candidate from the cells in the same row, column, and square. This leads to more singles ... or to more other patterns.

Part of the fun in Sudoku is that there are so many different patterns to search for. You described "hidden singles", and I mentioned "naked pairs". There are many others, and an excellent description of many of them appears on this web page.

So my overall point is that, while your conjecture may not have been true ... you are on your way to having more fun with Sudoku!
Nick67
 
Posts: 113
Joined: 24 August 2007

Re: Could someone tell me ...

Postby zebedeezbd » Sun Sep 18, 2005 4:03 pm

kernparker wrote:Pencilmark every unpopulated small square with every digit that could occur there, all digits except those that occur in the small square's row, column, or 3x3 square. (This is admittedly a tedious process, subject to error, but if you're careful you can do it accurately.)

Indeed, this is precisely what most people in this forum do to solve a sudoku (except the simple ones). In fact to have any hope of solving some of the tougher ones, you have to take this approach (or something similar).
It sounds to me like you have only been tackling relatively simple sudokus so far, solvable by the 3 or 4 simple methods alone. But perhaps you are ready to move on to harder ones now that require you to hunt for "naked pairs" (as explained by Nick67) or "naked triples". There are many even more sophisticated techniques too, but they are not usually required to solve most newspaper-published puzzles.[/quote]
zebedeezbd
 
Posts: 60
Joined: 14 September 2005

Re: Could someone tell me ...

Postby zebedeezbd » Sun Sep 18, 2005 4:05 pm

zebedeezbd wrote:Indeed, this is precisely what most people in this forum do to solve a sudoku (except the simple ones).

I just thought I should clarify that ambiguous statement! I meant simple sudokus, not simple members of this forum. Although either statement may be true...[/quote]
zebedeezbd
 
Posts: 60
Joined: 14 September 2005

Re: Could someone tell me ...

Postby Doyle » Sun Sep 18, 2005 7:47 pm

kernparker wrote:
It is my conjecture that this straightforward, brute force approach should work:

Pencilmark every unpopulated small square with every digit that could occur thereand 3x3 square...


Your conjecture is actually true, with a catch. It depends on how you define "every digit that could occur there." Only one digit in each cell eventually, so your conjecture is true, eventually. But the more difficult Sudokus will have more than one candidate in some cells after the simpler elimination techniques that solvers tend to start with, and even after exhaustive brute force eliminations that rely on what I'd call "first order" rules. So your conjecture is false in that sense. Other techniques, still logical but more complex, are required for further eliminations. And there, as was said above, is much of the fun.
Doyle
 
Posts: 61
Joined: 11 July 2005


Return to Advanced solving techniques

cron