T&E vs. unique solutions

Advanced methods and approaches for solving Sudoku puzzles

Solutions

Postby Guest » Fri Mar 11, 2005 10:24 pm

This is quite interesting. There are essentially two issues here, the first is whether trial and error is ever necessary, and the other is uniqueness of solution.

Addressing the first point, I don't think that trail and error should be necessary. I have completed Thursday's and Friday's puzzles without resorting to guessing. (Friday's did take me two hours though.)

I find with the fiendish puzzles you have an initial burst of easy numbers, and then two, perhaps three, little bast***s, before the rest of the grid falls into place.

I have a few ideas as to how this can be proved/disproved using linear algebra. Essentially you have 27 equations in however many unknowns, along with a bunch of constraints. Not really fully formed my thoughts along those lines though.

As for uniqueness of solution, I think this is tied into the first point. I think (guess) that if you follow the logical path to completion then you can only solve the problem in one way, however, it would make sense that if at some point you resort to trial and error, that you could come to another solution. A hypothetical example of this is, say, if the first and third columns started completely blank (not sure if this is possible, but let's assume it is) then upon completion, you could swap them both and should still have a legal solution. Again, it should, in theory be possible to prove/disprove these ideas.

A method which takes pretty much all of the fun out of solving these things (so don't read any further if that bothers you) is to draw up a grid (in Excel say), with a 3 by 3 grid for each entry. (So where the original grid is 9 x 9 the new one is 27 x 27). In each new 3 x 3 grid write the numbers 1 to 9. Now, where you have a clue, highlight the corresponding number in your 3 x 3 section, and delete all the others. Then delete all of the instances of that number in the rows, columns, and 'neighbourhoods'. Do this for all of the clues. Now identify any numbers which are alone in their row, column, or neighbourhood, these must be the numbers which go in those cells, and repeat the process.

(At any given stage you may have to be slightly more tricksy with this, and, for instance, figure out the a certain column in one neighbourhood has to have a 2 in it, say, and so the 2s in the neighbourhoods above and below must be wrong)

I think this is how a programatical method to solve the problems could work. Instead of ruling numbers into any given cell, rule them out of all the others.
Guest
 

Postby MC » Fri Mar 11, 2005 11:13 pm

That does raise an interesting point. If a Su Doku is solveable with a really tricky bit of logic, but you elect to guess, incorrectly, is your solution still correct?

It could be argued both ways:

1. The T2 puzzles can all be solved by logic so therefore the only solution is the one that is arrived at by the use of logic.

Or:

2. There is nothing in the rules that says you can't guess if you want to and, if you can come up with a valid solution that is not the same as that based purely on logic, who cares? It's still valid.

You are right about swapping 2 rows/columns that are completely blank at the start, but only if they are in the same bank of 3. That said, I've never seen one set that way.

As to your method of actually solving the puzzle using monkey-see, monkey-do rules in a spreadsheet, that, as you say, takes all the fun out of it. You're also in danger of getting nibbled to death by ducks, with too much info on the screen. It's hard enough keeping track of a 9 x 9 grid. Yours has 9 times more info at the start and my gut feeling is that you are therefore at least 9 times more likely to make a mistake.
MC
 
Posts: 10
Joined: 11 March 2005

Postby Sam_M » Fri Mar 11, 2005 11:56 pm

It would not be possible for a puzzle to be set with two rows or colums all blank in a single block of three if the puzzle is intented to be solved by logic because it would involve one guessing which one is which, something that the designers have been trying to get rid of.
Sam_M
 
Posts: 1
Joined: 11 March 2005

Postby MC » Sat Mar 12, 2005 1:56 am

You're right - the bit about pairs of blank rows/columns in the same chute is a bit of a red herring and of mathematical interest only because, as you say, it would lead to an ambiguous solution. It would still be "possible" to set such a puzzle... just a bit pointless, though.
MC
 
Posts: 10
Joined: 11 March 2005

Re: Solving with Excel

Postby Pappocom » Sat Mar 12, 2005 5:08 am

MC wrote:Therefore, I would suggest, the claim that all T2's puzzles have a unique solution is in error.

Hi MC. Would you please post the particulars here of any puzzle you think has two solutions. Please make sure it is a Pappocom puzzle, and say when and where the original was published.

- Wayne
Pappocom
 
Posts: 599
Joined: 05 March 2005

Postby MC » Sat Mar 12, 2005 10:38 am

If I could remember when it was that I "guessed" these 2 puzzles, I'd do it. However, they were some weeks ago. Both puzzles were from T2.

I can fully accept that there is one purely logical way of solving your puzzles. However, the sparsity of clues in the Fiendish puzzles does, in a small number of them, leave room in the grid for different patterns from those intended.

Perhaps I should have said, "Sometimes, guesswork will cause one to arrive at a different, valid solution from the one that can be arrived at by logic alone." That would have been a more tactful way of putting it and I apologise for any offence, if taken.

There is nothing in the rules published in T2 about not guessing. I therefore come back to a point I made on the other thread - do the competition entry checkers check for valid solutions, or do they just compare with the "logical" solution?
MC
 
Posts: 10
Joined: 11 March 2005

Postby Guest » Sat Mar 12, 2005 8:04 pm

My dad has just found sudoku in the telegraph and he's now got me hooked. I have finished one 'tough' puzzle but i'm stuck on another. i can't see a way to solve it apart from T/E. Also, where are you getting the friday etc puzzles from?

Craig
Guest
 

Postby MC » Thu Mar 17, 2005 5:32 pm

I have come to the conclusion that these possible double solutions will only be found by "Intermediate" players before they discover "all the rules" - about the stage where they can do "Difficult" puzzles but still have a problem with "Fiendish". Once you know all the rules, you no longer have need of guesswork and it doesn't even occur to you to hazard a guess in the first place.

Incidentally, Biscuit's linear algebra idea works perfectly. I dimly remembered it from Uni (a lot of years ago) and skated over his post, thinking "Linear Algebra, eh? Can't remember a thing about it..." Whether that triggered something, I don't know, but I worked out a method over the space of the last week or so that works every time a coconut. Having re-read his post, I realise that we've arrived at the same conclusion. There's still a load of skull-sweat to do and a lot of fuzzy logic, so it doesn't take all of the fun out of it - it just relieves a lot of the frustration of forgetting where you'd got to in your train of thought... "If I put a 7 there, that means the next one goes... there, which means the next one goes... Haven't I already got one in that column? If I put a 7 in there, that means the next one goes... I'll try an 8... maybe a 4? How about a 7... Haven't I already tried that? Or was it 5 minutes ago, before I put that 3 in the next cell?" Does this sound familiar?:D
MC
 
Posts: 10
Joined: 11 March 2005

Postby Guest » Thu Mar 17, 2005 8:14 pm

MC, I read your post with interest, and I'm glad to see you have come over to the light side - those of us who know that if one solution is achievable by logic alone (i.e. no guess work), then no other solution can be possible.

May the force be with you.
Guest
 


Return to Advanced solving techniques