Scientific American Puzzle - Is Guessing Required?

All about puzzles in newspapers, magazines, and books

Scientific American Puzzle - Is Guessing Required?

Postby michel » Fri Jun 09, 2006 3:20 am

Hello all,

The following puzzle is given in the current Scientific American issue.
URL: http://www.sciam.com/media/pdf/sudoku_solutions_REV.pdf
(In the pdf, the bold numbers are the puzzle - the gray numerals are the solution.)

I have reproduced it below:

Code: Select all
 +-------+-------+-------+
 | 9 . . | 6 3 . | . . 4 |
 | . 1 . | 2 5 8 | . . . |
 | . . . | 7 . . | . . 8 |
 +-------+-------+-------+
 | 6 4 . | . 2 . | 5 . . |
 | . . . | . . . | . . . |
 | 8 2 . | 5 . . | . 9 . |
 +-------+-------+-------+
 | . . . | . . . | 8 7 . |
 | 3 . . | . . 5 | . 4 . |
 | . . 1 | . 7 6 | . . . |
 +-------+-------+-------+


This is where I bogged down:

Code: Select all
  9      58    28   | 6      3     1     | 7     25     4   
  7      1     4    | 2      5     8     | 369   36     369 
  25     36    36   | 7      49    49    | 12    125    8
  ------------------+--------------------+-------------------
  6      4     379  | 189    2     379   | 5     138    137
  1      359   3579 | 489    4689  3479  | 2346  2368   2367
  8      2     37   | 5      146   347   | 1346  9      1367
  ------------------+--------------------+-------------------
  45     569   569  | 1349   149   2     | 8     7      1359 
  3      7     28   | 189    189   5     | 1269  4      1269
  245    589   1    | 3489   7     6     | 239   23     2359


Can anybody suggest a non-guessing strategy at this point?

Thank you in advance.
michel
 
Posts: 3
Joined: 08 June 2006

Postby ravel » Fri Jun 09, 2006 8:37 am

First simple coloring (or turbot fish or 2 strong links) for number 2 over the cells r9c1-r3c1-r1c3-r1c8 eliminates 2 from r9c8 (either r9c1 or r1c8 must be 2).
Then (with the 3 in r7c4) there is an empty rectangle for number 1 in box 9/strong link in r48c4, which eliminates 1 in r4c9 (either r4c4 is 1 or r8c4 and r7c9).
But both do not help much. So i needed this chain to eliminate 2 from r9c1:
r9c1=2 => r3c1=5 => r1c2=8 => r9c2<>8 => r9c4=8 => r9c1=4
contradiction => r9c1<>2 => r3c1=2
This solves the puzzle.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby daj95376 » Fri Jun 09, 2006 8:37 am

Applying Colors, Multi-Colors, and additional fundamental techniques, Simple Sudoku reduces the puzzle (further) to this point before stopping.


Code: Select all
 *-----------------------------------------------------------*
 | 9     58    28    | 6     3     1     | 7     25    4     |
 | 7     1     4     | 2     5     8     | 39    6     39    |
 | 25    36    36    | 7     49    49    | 12    125   8     |
 |-------------------+-------------------+-------------------|
 | 6     4     379   | 18    2     379   | 5     18    37    |
 | 1     359   3579  | 489   4689  3479  | 2346  28    2367  |
 | 8     2     37    | 5     146   347   | 1346  9     1367  |
 |-------------------+-------------------+-------------------|
 | 45    569   569   | 3     149   2     | 8     7     159   |
 | 3     7     28    | 189   189   5     | 1269  4     1269  |
 | 245   589   1     | 489   7     6     | 29    3     259   |
 *-----------------------------------------------------------*


Now, apply BUG+1 to get r3c8=5 and the remainder is trivial. No guessing involved.

(Thanks to Ruud for introducing me to BUG+1!)
(Thanks to angusj for Simple Sudoku!)
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby ravel » Fri Jun 09, 2006 8:44 am

daj95376 wrote:Now, apply BUG+1 to get r3c8=5 and the remainder is trivial. No guessing involved.

Sorry, but there is no BUG+1. (Same problem like here ?)
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Sped » Sat Jun 10, 2006 1:27 am

Code: Select all
 *-----------*
 |9..|63.|..4|
 |.1.|258|...|
 |...|7..|..8|
 |---+---+---|
 |64.|.2.|5..|
 |...|...|...|
 |82.|5..|.9.|
 |---+---+---|
 |...|...|87.|
 |3..|..5|.4.|
 |..1|.76|...|
 *-----------*


Simple Sudoku gets this far using basic techniques, plus it eliminates the 2 in r9c8 on colors and the 1 in r4c9 on multiple colors:

Code: Select all
 
 *-----------------------------------------------------------*
 | 9     58    28    | 6     3     1     | 7     25    4     |
 | 7     1     4     | 2     5     8     | 39    6     39    |
 | 25    36    36    | 7     49    49    | 12    125   8     |
 |-------------------+-------------------+-------------------|
 | 6     4     379   | 18    2     379   | 5     18    37    |
 | 1     359   3579  | 489   4689  3479  | 2346  28    2367  |
 | 8     2     37    | 5     146   347   | 1346  9     1367  |
 |-------------------+-------------------+-------------------|
 | 45    569   569   | 3     149   2     | 8     7     159   |
 | 3     7     28    | 189   189   5     | 1269  4     1269  |
 | 245   589   1     | 489   7     6     | 29    3     259   |
 *-----------------------------------------------------------*


The simple discontinuous nice loop:

[r3c8]-1-[r3c7]-2-[r3c1]=2=[r9c1]=4=[r9c4]=8=[r9c2]-8-[r8c3]-2-[r1c3]=2=[r1c8]=5=[r3c8] => r3c8<>1

eliminates the 1 in r3c8. It's all singles from there.
Sped
 
Posts: 126
Joined: 26 March 2006

Postby michel » Sat Jun 10, 2006 2:21 am

Thanks for the illumination and patience Ravel. I'm not new to Sudoku but I've not looked into it this deeply before. Your walking me through the colouring technique was very helpful and informative.

So I can follow how one gets to the board shown by Sped and daj.

If I assume (as you did Ravel):
r9c1=2 => r3c1=5 => r1c2=8,
then that forces r8c3=2 but r9c1=2 which is in conflict
so then: r9c1<>2 hence r3c1=2

This seems like a short loop that one might argue as directly observable or self-evident.

Not meaning to offend, this still strikes me as a guess vs a directed strategy. Is such guessing typically required to deal with "hard" puzzles?
michel
 
Posts: 3
Joined: 08 June 2006

Postby Sped » Sat Jun 10, 2006 3:29 am

michel wrote:If I assume (as you did Ravel):
Ir9c1=2 => r3c1=5 => r1c2=8,
then that forces r8c3=2

No. r1c3 is forced to a 2 and r8c3 is forced to an 8. No contradiction yet.

Not meaning to offend, this still strikes me as a guess vs a directed strategy. Is such guessing typically required to deal with "hard" puzzles?


The whole question of what is guessing and what is logic has been gone over here and elsewhere at length. It's really a philosophical question with no answer. A reasonable (to me) place to draw the line between logic and guessing is between basing a deduction on the observation of a static grid (logic) and making an assumption and stepping through a dynamic grid to see if the assumption leads to a contradiction (guessing).

Ravel didn't just plug a 2 into r9c1 for the heck of it to see if it would lead to a contradiction. There are definite rules concerning strongly linked cells (cells with the only two instances of a certain candidate in a group so that if one cell is true for that candidate the other is false and vice versa), weakly linked cells (cells that share a candidate and a group so that if one cell is true for that candidate the other is false), and bivalue cells (cells with just two candidates).

A person (or program) familiar with these rules can look at the 5 cells in his solution and deduce that r9c1 cannot be a 2. No guessing required.

The clearest explanation of these rules is probably here:

http://forum.enjoysudoku.com/viewtopic.php?t=2143

The above link describes simple nice loops. Ravel didn't express his solution as a loop, but he very well could have:

[r9c1]=4=[r9c4]=8=[r9c2]-8-[r1c2]-5-[r3c1]-2-[r9c1] => r9c1<>2

My nice loop solution is longer than his, so that makes his better:)

If nice loops aka forcing chains are guessing then I suggest that exclusions based on naked pairs are guessing also. Afterall, if there are a pair of (1,2) cells in a row, and some other 1s and 2s in the row also, a person unfamiliar with the naked pair concept might try putting a 1 or a 2 in one of the cells outside the pair and working out the consequences. BTW, though no one ever bothers to do it, naked pairs can be expressed as nice loops.

To answer your question: Yes. Harder puzzles seem to require techniques like this.
Sped
 
Posts: 126
Joined: 26 March 2006

Postby Carcul » Sat Jun 10, 2006 10:14 am

Michel wrote:Not meaning to offend, this still strikes me as a guess vs a directed strategy.


Read carefully the thread pointed by Sped, try to draw some bilocation/ bivalue plots, and you will see in front of your eyes a direct strategy. No guess is required.

Carcul
Carcul
 
Posts: 724
Joined: 04 November 2005

Postby ravel » Sat Jun 10, 2006 6:18 pm

Maybe i should say, how i found the loop, to clarify this question.
In a situation like above i (also) look for xy-wings and (and xy-chains) and check the bivalue calls. The first one is r1c2. Looking at the 8 i saw that in column 1 the numbers 5,4,and 2 would follow. On the other hand the 8 in r9c4 and a 4 in r9c1 (the rest was formulating a chain).
So, what i did was just a deeper form of looking for xy-wings and i suppose that only a few people would say that xy-wings are guessing. But in both cases you have a form of trial & error.
ravel
 
Posts: 998
Joined: 21 February 2006


Return to Published puzzles