Unique-solution puzzles that cannot be solved with logic

Advanced methods and approaches for solving Sudoku puzzles

Postby petef » Mon Jun 20, 2005 10:01 pm

That is my experience solving the Times puzzles. In principal at least, I work by saying that every cell can take all values and then eliminating possibilities until I am left with the unique solution. There is never a need to undo an elimination.

There are puzzles which do have a unique solution but have not (yet?) yielded to logic that does not backtrack. For example

Code: Select all
*2*|***|5**      721|436|598
**9|7**|***      639|758|241
***|**1|*3*      548|291|736
---+---+---      ---+---+---
4**|*7*|**9      412|375|689
3**|*2*|**7  =>  396|824|157
8**|*6*|**4      857|169|324
---+---+---      ---+---+---
*6*|9**|***      163|982|475
***|**3|8**      974|513|862
**5|***|*1*      285|647|913

--
Pete Forman
petef
 
Posts: 30
Joined: 17 May 2005

Is it me?

Postby stuartn » Fri Jul 15, 2005 11:27 am

Or is the Times Fiendish getting easier? - this week the worst it could do was a couple of hidden pairs - or wasn't I looking? and the Excel helper at
www.brightonandhove.org/sudoku/solver5c.xls did it in just two iterations.

:(

stuartn
www.brightonandhove.org
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby Observer2 » Fri Jul 15, 2005 11:34 pm

Petef,

I’m new to all this... I found the Sudoku puzzles in the Washington Post last week, and I was instantly hooked! The puzzles I’ve seen in the paper so far have been fairly easy (I’ve missed a couple of the daily papers, but what I’ve gotten so far, I do in pen...), so naturally I was intrigued by the puzzle you showed above. I’ve been playing around with it – it’s the first time I’ve actually used the ‘pencilmark’ system – and I haven’t been able to fill in a single unit yet, though I have some down to two candidates.

I don’t have a program (yet) that can apply filters, so looking for a swordfish pattern is extremely tedious (checking for x-wings by hand was bad enough!). Would you tell me whether you checked for swordfish at this opening stage of the puzzle, and if so, whether you found any? If you did, please don’t tell me what they are. I just want to know if that is the first step to get a square filled in from the opening setup.

If there was no swordfish, was there some other logical strategy (not including proof by contradiction) that was helpful at this stage? Or did you have to go to proof by contradiction at the outset?
Observer2
 
Posts: 2
Joined: 11 July 2005

Postby scrose » Sat Jul 16, 2005 3:15 pm

The puzzle can be reduced by looking for naked and hidden pairs, and candidate restrictions. The swordfish technique does not need to be applied to reach this point.

Code: Select all
 {167}   2       {13478} | {468}   {3489}  {468}   | 5       {79}    {168}
 {156}   {138}   9       | 7       {358}   {2568}  | {246}   {246}   {1268}
 {567}   {478}   {478}   | {24568} {4589}  1       | {79}    3       {268}
-------------------------+-------------------------+-------------------------
 4       {15}    {126}   | {13}    7       {58}    | {1236}  {2568}  9
 3       {59}    {16}    | {458}   2       {4589}  | {16}    {58}    7
 8       {1579}  {127}   | {13}    6       {59}    | {123}   {25}    4
-------------------------+-------------------------+-------------------------
 {127}   6       {38}    | 9       {1458}  {24578} | {247}   {247}   {235}
 {1279}  {147}   {147}   | {256}   {15}    3       | 8       {2679}  {256}
 {279}   {38}    5       | {2468}  {48}    {24678} | {24679} 1       {236}

At this point, I am stuck. Forcing chains might offer a solution. Note that the puzzle can be solved easily if a guess is made by placing a 5 at r8c4 -- highlight the text to reveal the clue.
Last edited by scrose on Thu Jul 28, 2005 10:50 am, edited 1 time in total.
scrose
 
Posts: 322
Joined: 31 May 2005

4's

Postby stuartn » Sat Jul 16, 2005 4:55 pm

Scrose - I'm being dense here - or perhaps it's the weekend - but what stops R2C2 from having 4 as a candidate?

S
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby scrose » Sat Jul 16, 2005 5:18 pm

  1. There is a hidden pair of candidates 7 and 9 in box 3. Therefore the candidate 2, 4's, 6's, and 8 can be eliminated from the cells r1c8 and r3c7.
  2. All of the candidate 4's in box 3 are located in row 2. Therefore all other candidate 4's in row 2 (r2c2, r2c5, and r2c6) can be eliminated.
scrose
 
Posts: 322
Joined: 31 May 2005

Postby petef » Sat Jul 16, 2005 7:51 pm

scrose wrote:highlight the text to reveal the clue.

Heh, have you been reading US military reports?
http://www.theregister.co.uk/2005/05/03/military_report_secrets/
petef
 
Posts: 30
Joined: 17 May 2005

Postby Observer2 » Mon Jul 18, 2005 10:19 pm

Thanks, Scrose. I haven’t read much of the forum yet, but I’ve read enough to know that if you’re stuck, I might as well pack it in!

Petef, do you have a record of the date and what paper that puzzle ran in? Doesn’t Pappocom post hints for the published puzzles, as well as the solution? Maybe the hint would tell what technique to use to get to the next step without guessing.
Observer2
 
Posts: 2
Joined: 11 July 2005

Postby petef » Tue Jul 19, 2005 9:26 pm

A copy was published on this site in a non-pappocom topic. The original was in Google Groups. It was definitely not a Pappocom puzzle.
petef
 
Posts: 30
Joined: 17 May 2005

Postby Nick70 » Tue Jul 19, 2005 10:19 pm

scrose wrote:At this point, I am stuck. Forcing chains might offer a solution.


Yes. The problem is solvable using forcing chains. Double forcing chains are not enough, however; you need triple and even quadruple forcing chains.

My program solves it in 109 iterations, not being able to place a big number until iteration 30.

It uses 2 Turbot Fishes, 15 double forcing chains, 5 triple forcing chains, and 1 quadruple forcing chain.

It is surely one of the hardest problems that can be solved without backtracking.

The following one, however, is probably even harder:

Code: Select all
..2.9.1.7
.386.....
4........
.....5...
..9.1.3..
...4.....
........4
.....792.
8.6.3.7..
Nick70
 
Posts: 156
Joined: 16 June 2005

Postby SudokuBart » Wed Jul 20, 2005 8:49 pm

Great puzzlegame, great site.. Let's see if I can help u solving your Sudoku.
SudokuBart
 
Posts: 2
Joined: 20 July 2005

Postby George » Thu Jul 21, 2005 12:39 am

Guys

You have all been tricked by the creator of the puzzle.

The original puzzle posted by Petef has only 21 numbers in it. Don't forget it is up to the creator of the puzzle to reveal the amount of initial numbers. 21 numbers is far too few for a non-bifurcation solution. Forget it unless you want to propogate in the round-about forever. Just apply all your known tricks once or twice and if you can't solve it, move on.

The latest one posted by Nick also only has 21 numbers in it. By the way, Nick, does the term "Forceing Chain" mean bifurcation or trial and error.

Cheers
George
George
 
Posts: 20
Joined: 20 July 2005

Postby simes » Thu Jul 21, 2005 8:35 am

George wrote:21 numbers is far too few for a non-bifurcation solution.
No it's not. Seehttp://www.csse.uwa.edu.au/~gordon/sudokumin.php

George wrote:...does the term "Forceing Chain" mean bifurcation or trial and error.
Nope, it means considering all candidates (usually 2) of a cell, and seeing that they all lead to the same logical conclusion on another cell. See www.sadmansoftware.com/sudoku/forcingchain.htm
Last edited by simes on Sun Dec 11, 2011 9:30 am, edited 1 time in total.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby George » Thu Jul 21, 2005 2:58 pm

George wrote:21 numbers is far too few for a non-bifurcation solution. Simes replied: No it's not. See http://www.csse.uwa.edu.au/~gordon/sudokumin.php.


In the above web site, it suggests that "there are examples of 17-hint uniquely completable Sudoku puzzles, but no known 16-hint examples." What that means is that 17 initial numbers are the minimum required to give a unique solution. But, have you considered what should be the minimum initial numbers given such that bifurcation (including forcing chain) is not required to solve it.

George wrote:...does the term "Forceing Chain" mean bifurcation or trial and error. Simes replied: Nope, it means considering all candidates (usually 2) of a cell, and seeing that they all lead to the same logical conclusion on another cell. See http://www.simes.clara.co.uk/programs/sudokutechnique7.htm


The conclusion at the end of the forcing chain may be logical, but the process in getting to that conclusion is definitely bifurcation, simply because you have to make a guess of a number to start with and then return to the same point when that chain experiences contradiction. To me, working with boolean with no return is pure logic.

Cheers
George
George
 
Posts: 20
Joined: 20 July 2005

Postby simes » Thu Jul 21, 2005 5:06 pm

George wrote:But, have you considered what should be the minimum initial numbers given such that bifurcation (including forcing chain) is not required to solve it.

It's still 17. Some (if not most) of those examples can be solved logically - even excluding forcing chain.
Last edited by simes on Sun Dec 11, 2011 9:31 am, edited 1 time in total.
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Next

Return to Advanced solving techniques

cron