The New Sudoku Players' Forum

[Sparrow]

Hi All,

I have just been reading with interest your threads on whether you think that more than one solution is possible or not, especially to the fiendish puzzles.

I personally have not had much trouble finding solutions to fiendish puzzles by logic alone, although sometimes it can take me a while. As some of you have already pointed out, the problem is how to keep all the valid combinations of possibilities in your head (i.e. which 'pencil marks' go with which ones), and sometimes I have to resort to pencil marking my pencil marks - which makes me think that I really should write out the grid on a bigger bit of paper. (At the moment I just use a fine pen on my copy of T2).

Anyway it occurrs to me that the problem of whether any other solutions are possible or not could be shown by computer. Two approaches to programming can be taken*, the first being to code what you believe are the rules, and the second to do an exhaustive search (if that proves to be too intensive then you could resort to simulated annealing or some other such directed search technique). Of course this will only show whether more than one solution is possible or not to a given puzzle and will not prove the general problem. Easter is coming, and if I have time I might try to write a couple of programs to give these two approaches a go, but I do have to redecorate my bathroom also. I would be most interested to hear if anyone else has tried to write a solution program.

[P.S. *I also think that su doku puzzles would make good examples for showing the power of quantum computation as they rely on the collapse of multiple possibilities.]

[Pappocom]

Hello Sparrow. This forum is meant to be for "by-hand" solvers, whereas your post raises the possibility of computer-soving - so it should really go in the "Solver programs" forum. Tomorrow I will move this thread into the Solver programs forum.

- Wayne.

[Guest]

Hi Sparrow, You may have seen a heated debate I was having with MC on this subject on the "Solving with Excel" thread.

As you say, this is actually extremely difficult to prove with a computer because taking a few puzzles and trying them just proves the case for those puzzles. To prove it conclusively you will have to come up with a generic definition of the requirements of a solvable puzzle, and then write an algorithm to generate all solvable puzzles, and prove that you haven't missed any. Not a simple task by any means. Once you've done that, you can get on with the task of testing them. All of them!

Thankfully, however, it is entirely unnecessary because it is in fact a logical tautology - Solvable by logic = Unique Solution

That is, if logic can be used to find a solution then by definition no other solution is possible, because it must contravene the logic (which is defined by the rules of the puzzle). To put it another way, if Logic says a cell must be a specific number, then to put another number there is clearly contrary to what the logic says it must be, and will therefore inevitably end in cells contravening the rules further down the line (though an eager puzzler may miss this). Because the correct values can be derived from the clues, the only way an incorrect value (i.e. not the logical choice) could be right is if the clues from which the correct value can be derived were incorrect - which obviously makes no sense!

It is perfectly possible for puzzles to have more than one solution, this is dependent on the clues given (e.g. if no clues are given, then there a very large number of valid answers - the value of this very large number has been discussed elsewhere). But if a puzzle does have more than one solution, none of the solutions can be derived from logic alone.

Make sense?

BTW Wayne - I felt that this question was more about the nature of the puzzle itself, rather than specifically about computer programs. Could it not live in the General section?

[Guest]

Just because a puzzle is solvable entirely by logical inference doesn't mean that it must have a unique solution. It could be that a puzzle has two solutions, and both these are reachable from the starting configuration without guesswork. If I correctly understand these puzzles, the idea is that at each step it is possible to infer at least one correct element and hence this process must reach a unique final configuration.

Your second point about the difficulty of solving these problems is an interesting one. Sudoku (played on an n x n grid) is well-known to be at least as hard as a game called 'Latin squares', which is in a class of problems known to be of maximal difficulty for today's computers. Unforunately the instances of these puzzles where one can logically infer the next step are not those that are hardest for a computer to solve.

Andrew

Computer Laboratory,
Cambridge University

[simes]

Just because a puzzle is solvable entirely by logical inference doesn't mean that it must have a unique solution.

But it does.

To arrive at a solution by a logical series of steps, each time you put a number in a cell, you're saying "this number must be in this cell". If that number need not be in that cell, then it's not a logical step. So by the time you've completed the entire puzzle logically, you've said a particular number must be in each and every cell.

So if a specific number must be in each cell, then there can be no other number in that cell. Therefore, there can be no other solution to a logically solvable puzzle. QED.

Simon

Computer Laboratory
Simon's House

[Guest]

Spot on Simes - as ever.

Now, I've just spent the last day and a half decorating at my parents' house; hours that I occupied thinking about this question, and I would like to forward a new hypothesis. I'm not quite willing to state it as fact, but I think it stands up to analysis. Hold on tight now :o)

If a puzzle cannot be completed without recourse to trial and error, there must either be no solutions or more than one.

Similarly, if a puzzle only has one solution, it must be solvable without T&E.

I could explain this outrageous claim, but I'll see if anyone bites first!

[Sparrow]

If a puzzle cannot be completed without recourse to trial and error, there must either be no solutions or more than one.

Similarly, if a puzzle only has one solution, it must be solvable without T&E.

I could explain this outrageous claim, but I'll see if anyone bites first!

Go on, go on, go on (imagine voice of Mrs Doyle from Father Ted..)
Sounds reasonable but can you prove it ?
(Is this abit like the four colours for any map problem - in that it is quite hard to actually prove properly ?)

Also, when I was thinking about whether it might be possible that a puzzle has two solutions which can both be accessed by logic, I was wondering whether the order in which you discounted possibilities was important. If the order is not important then presumably a logically solvable puzzle should only have the one solution, but if order is important doesn't this raise the possibility that there may be other valid solutions ?

[Guest]

Well, I wasn't claiming it was a simple proposition! :o)

Also, when I was thinking about whether it might be possible that a puzzle has two solutions which can both be accessed by logic, I was wondering whether the order in which you discounted possibilities was important. If the order is not important then presumably a logically solvable puzzle should only have the one solution, but if order is important doesn't this raise the possibility that there may be other valid solutions ?

I think we need to define "Logic". What I mean by logic is any method of deduction that reduces possibilities, but does not involve trial and error.

So, with this in mind it is clearly not possible to have two solutions that can be attained by logic, because logic means eliminating possibilities for cells until they all only have one possibility. This is why I (and others) make the point that if any solution is attainable by logic then there can only be one solution whether logic is actually used or not - Trial and error could be used from start to finish, but it could only end up with the same solution.

I make that statement so confidently because it is actually the definition of "Logic" - that the possibilities for a cell can be whittled down to a single digit based on the available clues. i.e. each cell must be the digit that the logic says it is.

So, this also means that if there is more than one solution, that none of them can be reached by logic.

Now, as I said, I think, but can't quite be certain that this also means that if there is only one solution it must be solvable by deductive logic. Thinking of it another way - under what circumstances could it be possible that logic can't get to a solution? I think the answer is that either there isn't a valid solution, or there must be more than one.

BTW - I don't have a TV, so I have no idea who Mrs Doyle is, but somehow I imagine an elderly Irish lady - Am I close?

[Sparrow]

IJ > I think we need to define "Logic". What I mean by logic is any method of deduction that reduces possibilities, but does not involve trial and error.

So if a square could be A or B, and then you follow the implications of A for a few squares and then decide that choosing A cannot be not a valid solution - this is logic ?. Whereas it is trial and error if you follow A for a while and don't manage to prove it's incorrectness, so you choose it anyway because you have a hunch ?

Alas not being a mathematician ! I am now getting confused between branching logic and trial and error !

Oh well, thanks anyway. I am now fairly convinced that puzzles solvable by logic have only the one solution. I am frankly quite relieved too, otherwise I would feel the urge to find the other ones.

IJ > BTW - I don't have a TV, so I have no idea who Mrs Doyle is, but somehow I imagine an elderly Irish lady - Am I close?

Yes spot on it was a very funny series. Impressed that you don't have a TV, can't quite bear to be rid of the thing myself, even though I despise it most of the time. Actually I started doing sudoku when we had a power cut the other week, hmm perhaps it was a sign ?

[Guest]

No - logic is neither of those, both definitely count as guessing, or T&E as it seems to be called here. Logic is using the information available to eliminate possibilities without ever trying a value and following the consequences.

I still occasionally can't see the logical way out of some puzzles, but that's the beauty of it - I know it can be done with just deductive reasoning, so I get to spend hours hating myself for not being able to do it!

And yes, not having a TV is fine - I thoroughly recommend it.

[Guest]

IJ made the

If a puzzle cannot be completed without recourse to trial and error, there must either be no solutions or more than one.

Similarly, if a puzzle only has one solution, it must be solvable without T&E.

I would like to add my say and to contradict both of the above assertions:

Consider those phrases in the context of the 'puzzle' of finding the prime factors a given very large composite number.

By the fundamental theorem of arithmetic, the factorisation is quaranteed to be unique i.e. there is exactly one solution. But it may be that we cannot find that solution without recourse to trial and error because:

A. A workable technique for factorising large numbers using pure logic may simply not exist or may not have been (and may never be) discovered.
B. If a deterministic (i.e. purely logical) factorising technique DOES exist, it may simply take so many resources (e.g. millions of years) to implement that the factorisation cannot be completed.

To summarise: just because we cannot complete the factorisation without trial and error does not mean there is no solution or more than one. It may simply be that we have inadquate knowlege or resources to solve it deterministically.
I believe the above argument applies generally to all 'puzzles' where a solution is known to exist.

-------------------

Conversely, if a trial and error approach is adopted, it is still possible [in a good many cases] to prove that the solution is unique.
Here's how it can be done with Su Doku puzzles:

1. Solve, using pure logic, as much of the puzzle as possible.

2. Select any unsolved cell, preferably one in which the choice of digits that may validly fit [on the information available so far] in that cell is very limited, ideally just 2 possibilities.

3. [Trial and error] Select one of those digits, enter it in the cell and using pure logic, deduce the logical consequences of doing this (e.g. other cells that may now be filled in).

4. [Backtrack] Remove the digit from the cell and rollback all the consequences deduced in step 3.

5. There are three possible outcomes from those consequences:
A. They lead to no conclusion and no progress has been made.
B. They lead to a solution of the puzzle, and we can make a mental note that at least one solution exists, but this does not prove the solution is unique. It is best to treat this situation as leading to no conclusion with no progress having been made.
C. [Pure logic] They lead to a contradiction. So now we make the purely logical conclusion that the digit entered in the cell at step 3 above MUST be wrong and needs to be removed from the list of digits that may possibly fit in that cell. This is genuinely making progress towards any unique solution to the puzzle. If only one digit remains in the list of valid possibilites for the cell, then enter that digit into the solution grid in the full knowlege that it MUST be correct.

4. If any progress has been made (because of steps 1 and C), repeat this algorithm from step 1.

5. When this step is reached, no further progress can be made. But, in practice, in a high proportion of cases, the puzzle is now actually solved.
Assuming it is solved, the solution must be unique as all cells contain only digits placed there by purely logical deductions, many at step C above. If it is not solved uniquely, that at least one possible solution may have been revealed at step B.

I have used the above algorithm within a Su Doku solver program I have written in PureBasic. So far it has rapidly (well within 5 seconds on my 300 MHz PC) analysed every Su Doku puzzle I have presented to it, correctly indicating whether a solution exists and, if it does, whether the solution is unique or not.

[Guest]

You should not infer that a trial and error solution is in any way a guess or is illogical. The way I do these puzzles is to write on a large set of squares all the candidate numbers for each box then eliminate them by entirley logical processes. viz: in each row and in each three by three matrix if there is only one correct candidate for a box then that is were the single possibility goes and that is a unique solution. Sometimes when there are pairs of possibilities around the grid an iterative solution can be used. If you choose the wrong number of a pair as the occupant of the box then as you collapse possibilities and chase your search thread around the grid, you find a logical inconsistency which clearly demonstrates itself, therefore, in these cases the initial choice was wrong so the other possible choice you made must then be the correct and only possible one.(IE because you are iterating from a binary position).. I cannot produce a uniqueness theorem for this as I am not as clever as Godel was.

It takes a bit of time, a rubber and a pencil but it never fails which is why I see no further point in doing these puzzles; they are in fact entirely logical which therefore makes them entirely uninteresting once you have an algorithmic approach like that decribed.. I am of the school which says if there is a logical solution why bother to find it. I apply this reasoning to thrillers on televison. ie since I know someone did it I regard it a boring detail to know who it actually was. This saves a lot of time since I dont then have to watch the programme.

It has of course taken me weeks of neglect of my family responsibilities to reach this illogical position but now I have I shall return to the crossword as these are insoluble by any anorak approach and are therefore of great interest and I can do them in company.

What I would like to know is if the setter of the puzzles can devise one which cannot be solved other than by guessing. I doubt it; I have mis transcribed a grid once from the paper to my large squared pad but have still solved the newly created puzzle ; albeit it became a super fiendish one but it yielded to iteration. In fact most dont need the iteration but its an elegant way of doing it for someone like me who has just retired from a life of iterating difficult non linear problems.


Regards
Fermat's ghost

[milobird]

"Trial and error", as it has been referred to, is in fact a logically sound process. It should more accurately be described as proof by contradiction, as it enables you to eliminate a possiblity with the same level of certainty as pure reduction.

However, I would suggest that under no circumstances is it necessary to use proof by contradiction to solve a puzzle.

Consider this: what are you actually doing when you use the rules of reduction? If you see that only three cells in a box contain a 6, and all three are in the same row, and therefore you eliminate the possiblity of a 6 being in the other cells in that row, what exactly are you saying? You aren't following the rules of Sudoku. It doesn't contradict the rules to place a 6 elsewhere in the row -- all you are really saying is that putting a 6 elsewhere in that row would lead to a contradiction later.

The lines between reduction and proof by contradiction are much more blurred than people seem to think, but the important thing is that all contradictions can be spotted in advance, and logically ruled out, without actually having to "try them out".

If you cannot solve the puzzle using reduction, then by definition the puzzle is not unique. If the puzzle is not unique, then proof by contradiction will not help you solve it either, as more than one solution can be reached without contradiction.

Hence, all puzzles that can be solved using proof by contradiction can also be solved using logical reduction.

[Guest]

I thought that might get people interested!

Firstly Fermat, this is probably just terminology, but for the purposes of discussing these puzzles it's important to distinguish between pure deductive logic based on the current state of the puzzle, as opposed to following iterations of possibilities. The assertion by the author of the puzzles is that the iterative approach is never necessary. So, in your situation where there are two cells with two possibilities, then yes you can try one and see what happens, and this will lead you to the right answer, but there will always be a cell somewhere else in the puzzle where further reductions will be possible without resorting to this method. Eventually one of these reductions will come back and resolve one half of the original pair, and thus the other. So, yes, itereration is logic, but unnecessary, thus the need to distinguish between Trial and Error (i.e. using iterative elimination) and Logic (Just for want of a better word). Make sense?

Anthony - Wow, interesting stuff! I suspect you have a higher pedigree than me - a maths degree perhaps? On the last point I wasn't arguing that Trial and Error can't be used to prove uniqueness, just that if the puzzle can be solved without T&E that this is a proof, and thus my conjecture that the inverse is also true. I should point out that this is only really relevant when talking about non-Pappacom puzzles, which always have only one solution and never require T&E.

On the question of factorisation, your points A & B seem to be practical issues with a different problem rather than logical issues with this one. I think I'd like to see a proof that these are actually the same problem before defering to your view.

It still seems clear to me that if a puzzle comes to a point where it cannot be solved without trial and error (not that I can't solve it, just that it is not possible to solve it by methods that may or may not be known), then the only reason this could be is that there is more than one possibility (or none). I spent a long time trying to think of a situation where T&E was necessary, but only had one possible outcome, and could not. I only have a small brain, so I accept this is not a proof! Can you think a situation where this is not true? About the T&E, that is - not my brain :o)

[milobird]

Yes, but I take issue with this:

If a puzzle cannot be completed without recourse to trial and error, there must either be no solutions or more than one.

The puzzle can only be solved by so-called "trial and error" if there is one solution.

If there are no solutions, it can't be completed.

If there is more than one solution, then trial and error won't give you a solution. When trialing you might hit upon a number that gives you a valid solution, but this gives you no indication of how many solutions there are. I prefer to call this "guessing".

True "trial and error" can only be used to eliminate contradictions, unless of course your goal is to enumerate the solutions to a puzzle that has multiple solutions.