Help with end-game

Advanced methods and approaches for solving Sudoku puzzles

Help with end-game

Postby octogenarian » Wed Oct 12, 2005 10:22 pm

I have recently discovered the fascination of Sudoku and have been

working through the Pappocom puzzles.

My analytical skills are perhaps not as finely honed as they should be

and I am having a bit of a struggle with some of what I read in the

solutions forum.

Below is the code for the end-game of a puzzle that has me stumped.

Rows 1, 3, 4, 5 and 8 are where the problem lies. I am assuming that if

I could reason out one more number the rest would come easily.

Particularly vexatious are the pairs of candidates 3 and 9 in R1C9,

R3C4 and R3C9.


{5}{8}{1} {4}{37}{79} {2}{6}{39}
{3}{2}{9} {1}{5} {6} {8}{4}{7}
{6}{4}{7} {39}{2}{8} {1}{5}{39}

{9}{5}{6} {37}{37}{1} {4}{2}{8}
{2}{3}{8} {69}{46}{49} {5}{7}{1}
{7}{1}{4} {5} {8} {2} {9}{3}{6}

{1}{7}{2} {6} {9} {5} {3}{8}{4}
{8}{9}{3} {2} {47}{47} {6}{1}{5}
{4}{6}{5} {8} {1} {3} {7}{9}{2}

Any line of reasoning anyone can offer to unlock this puzzle will be

appreciated. (I have solved it by trial and error but that is not

really the objective, is it?)
octogenarian
 
Posts: 4
Joined: 12 October 2005

Re: Help with end-game

Postby Condor » Wed Oct 12, 2005 10:56 pm

Have a look at column 4 and the whole puzzle will fall into place.

octogenarian wrote:(I have solved it by trial and error but that is not really the objective, is it?)


You can solve by any means you like, but it is far less satisfing than by logic. Pappocom's only need loic.
Condor
 
Posts: 62
Joined: 19 June 2005

Re: Help with end-game

Postby Lummox JR » Thu Oct 13, 2005 12:47 am

Condor wrote:You can solve by any means you like, but it is far less satisfing than by logic. Pappocom's only need loic.

All valid sudoku only need logic. It might be extremely complex logic, or something complex like trial and error, but if you need to guess then the puzzle has multiple solutions and is therefore invalid.
Lummox JR
 
Posts: 125
Joined: 22 September 2005

Postby QBasicMac » Thu Oct 13, 2005 1:57 am

Cell r5c4 cannot have pencilmarks {69} as you have shown because of the 6 at r7c4, right?

Therefore r5c4=9, making r3c4=3 and r5c6=4.

Etc. (The rest are automatic)

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Re: Help with end-game

Postby Cec » Thu Oct 13, 2005 4:29 am

octogenarian wrote:I have recently discovered the fascination of Sudoku and have been

working through the Pappocom puzzles.

My analytical skills are perhaps not as finely honed as they should be

and I am having a bit of a struggle with some of what I read in the

solutions forum.


Hi Octogenarian and good to know somebody else shares my same problem re analytical skills.

If you haven't already looked at these, the following sites provide hints/terminology,etc. to help with these puzzles:

(a) http://www.simes.clara.co.uk/programs/sudoku.htm
(b) http://www.angusj.com/sudoku/hints.php

In (b) above, downloading the free "Simple Sudoku" program is well worth considering.

Bonsai Cec
Cec
 
Posts: 1039
Joined: 16 June 2005

Help with end-game

Postby octogenarian » Thu Oct 13, 2005 1:35 pm

Condor and others--

The solution was so obvious--once you pointed it out to me. I had checked, double checked and double checked again, and still missed it.

Thanks for your help.:D
octogenarian
 
Posts: 4
Joined: 12 October 2005

Re: Help with end-game

Postby Condor » Thu Oct 13, 2005 10:52 pm

octogenarian wrote:Condor and others--

The solution was so obvious--once you pointed it out to me. I had checked, double checked and double checked again, and still missed it.

Thanks for your help.:D


Glad I could help. It's amzing what a fresh set of eyes sees.
Condor
 
Posts: 62
Joined: 19 June 2005

Re: Help with end-game

Postby simes » Fri Oct 14, 2005 7:10 am

Lummox JR wrote:All valid sudoku only need logic. It might be extremely complex logic, or something complex like trial and error, but if you need to guess then the puzzle has multiple solutions and is therefore invalid.

I don't see the distinction you're making here, nor agree that a solution must have multiple solutions if you need to guess. Surely a guess is the first step in a T&E strategy?

At the point where you can't see any further moves, and so you decide to try T&E, you have to make a guess. If you then find a solution, then you may have found one solution out of many, or you may have found the only solution.

I'm not arguing that T&E is not a logical BTW (I don't want to open that can-o-worms again) just that in order to implement T&E, you have to guess at some point, and that making that guess doesn't show the puzzle has multiple solutions.

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby stuartn » Fri Oct 14, 2005 11:04 am

Simes wrote:

in order to implement T&E, you have to guess at some point


Disagree..... If I say to myself - 'once I've exhausted all usual strategies I'll start at the first digit in the first double cell I come to - I'll test that digit and move on to the next digit. If I find an inconsistency I'll remove the relevant candidate'

Now where am I guessing in that?

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby simes » Fri Oct 14, 2005 11:18 am

stuartn wrote:Now where am I guessing in that?

Well, the point I'm trying to make, is that at some point you enter a number in a cell without have any particular reason to do so. You enter it to see where it leads, without knowing it will lead to the solution. That's the trial part of the T&E.

You have a a particular strategy for chosing which cell and candidate to try - but that candidate is no more or less likely to lead to a solution than any other - so it's just as good, or bad, as a complete guess. And anything that's only as good as a guess, well, might as well call it a guess.

So do you agree with the Lummox's assertion that puzzles that require a guess have multiple solutions, but that those that merely require T&E can have a single solution?

S
simes
 
Posts: 324
Joined: 11 March 2005
Location: UK

Postby emm » Fri Oct 14, 2005 12:10 pm

This is a doppleganger for the other thread. It does all come down to what you call guessing.

In T & E techniques like chains or colouring the initial choice of candidates is not what I call a guess. A guess is when I get to the point in the puzzle when I have no idea what to do next, so I try anything.
emm
 
Posts: 987
Joined: 02 July 2005

Postby stuartn » Fri Oct 14, 2005 12:42 pm

Simes asked:

So do you agree with the Lummox's assertion that puzzles that require a guess have multiple solutions, but that those that merely require T&E can have a single solution?


In short.... no. I'm sure Tso shared a '9 guess' grid with us some time ago - and I'm sure it had a unique solution (CMIIW). As I've postulated before - many times - we can't be sure that we've exhausted all the avenues of logic to solve these beasts - the fact that we (presently) label some as unsolvable or 'invalid' is a red herring imposed upon ourselves by ourselves as a 'get out clause' when our knowledge of strategies fails.... and I'm certainly not asserting that this implies all grids ARE solvable by logic... just that we are not in a position to prove otherwise.

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Postby QBasicMac » Fri Oct 14, 2005 12:51 pm

stuartn wrote:Now where am I guessing in that?


Your technique is still called "guessing" for lack of a better name. Perhaps "serial exhaustion of candidates by means of reductio ad absurdum" would be more accurate.

Of course true guessing would be to pick one of the candidates on hunch and assume it is correct and confidently fill in the puzzle cell and continue. If the puzzle solves, smirk and say "I did it!" If the puzzle does not solve, throw it in the garbage and wait for tomorrow's.

Scientific solving by means of an algorithm such as you named is not "true guessing" because a) it will always find the solution (if there is one) and b) it will discover if there are duplicate solutions.

I'm surprised there isn't already a jargon term for that on this forum. I'll invent one: "serial hacking."

Serial hacking – the technique whereby a) the puzzle solution so far is saved and b) an unsolved cell is selected and it's pencilmarks are recorded in a separate list. Thereafter, for every pencilmark on the list, the saved puzzle solution is restored and that pencilmark is taken to be a "naked single" and one proceeds as usual, ending with one of the following cases.

Case 1: A solution is then found. As a result, the pencilmark is left on the list.

Case 2: An impossibility occurs. As a result, the pencilmark is removed from the list

Case 3: Unable to make any further progress. As a result, it is necessary to nest the process to determine whether the pencilmark is to be kept or removed.

Nesting means to make a copy of the current solution so far including the assumed naked single and to pick some other unsolved cell and process all it's pencilmarks, possibly leading to even further nesting. Eventually this will return to the top level as Case 1 or Case 2.

I have used this technique on puzzles that required me, at least, to nest 3 deep. It is a lot of bookkeeping.

Mac
QBasicMac
 
Posts: 441
Joined: 13 July 2005

Postby PeterH » Fri Oct 14, 2005 1:46 pm

After you do a couple of hundred puzzles you get to see where the problems lie and where the work should start. I haven't found any reason for not starting at the easiest point. Every square filled is a good square filled.

One tip is to circle the numbers that are given in the clue or the absolute "must be's" that follow on from that. Make sure you are 100 percent sure because an early error can be fatal later.

I sometimes note a puzzle to a point that has a high percentage chance of being right (so far) because a lot fits. Then I can second attack from that point if it doesn't follow through. It is also wise to see if there is a second option - a close variation that is still right with the board so far.

(How many puzzles are abandoned when the thing is only two to four square swaps from being right? Sadly it is impossible to say whether you are working towards a near miss that may - sadly - be nothing like!)

One of the truths is that the puzzle is about angles. Sometimes you get stuck and the only way to get out of it is to note three must be numbers. Say you have a bottom left and down of 123XXX789. You know the numbers 456 are in those three squares - only you don't know the position. You may HAVE to use these numbers ("they can't be anywhere other than here" and any other clues) to go forward.

If you are only using two "possibles" for a square then it might be impossible to go beyond a set point from the angle you are approaching. Ironically if you have taken another route you may have been able to solve the thing with a square that had only two possibles.
PeterH
 
Posts: 1
Joined: 26 September 2005

Postby stuartn » Fri Oct 14, 2005 1:56 pm

Your technique is still called "guessing" for lack of a better name


Just to reassure you- it's not MY technique... I'm a true Sudonaut - although my Excel sheet will allow 'chain hunts' using this method.

stuartn
stuartn
 
Posts: 211
Joined: 18 June 2005

Next

Return to Advanced solving techniques