The New Sudoku Players' Forum

[simes]

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.

LOL!

Hey, this line of reasoning could get me out of so much! I just need to persuade the wife that it makes sense.

[Guest]

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

If there is more than one solution, then trial and error won't give you a solution

OK, we need to settle definitions here. I think the exact opposite! T & E is the only way to solve a puzzle with more than one solution. My point that you quoted was that if you get stuck and logic can take you no further then there cannot be exactly one solution - it's either unsolvable or has multiple solutions. T & E is the only way to find out.

I would define T&E as picking one of the available possibilities, and seeing if it leads to a contradiction, which seems to be what you are saying, but how is this different to guessing? It sounds exactly the same to me.

[milobird]

I see what you mean.

I was thinking that T&E would be used to search for a contradiction, and then eliminate the corresponding possible from the original problem.

If the puzzle has more than one solution (or none at all), then this will never lead you to a solution. The only way to reach a solution is to keep trying until you find something that doesn't lead to a contradiction. Once you've solved a puzzle like this ("guessing", in that there isn't any error involved, haha) the only thing you've proved is that the puzzle has one or more solutions. You could continue trialing for other solutions, but isn't that basically a brute force search?

Is it possible to set a puzzle that has no valid solution?

[Guest]

I think guessing is different to trial and error; I would suggest that a guess is random selection without any recourse to reasoning whereas trial and error is actually a rigorous logical process since it tests the suggested solution according to a set of logical conditions.

In the teaching of mathematics in school as experienced by me, iteration was regarded as cheating (because the maths teachers wrongly regarded it as guessing) whereas it is in fact a powerful technique I learned later.The problem is to verify the uniqueness of the solution which in this case it is not necessary to do. I do not believe that the puzzle setters placed any requirement in the game to determine if a solution is unique, merley that it is 1 to 9 once each in each column, row and 3X 3 matrix.

I think we are perhaps using the wrong terminolgy here. In solving the puzzle we are testing for the truth or falsehood of various logical propositions and with that in mind any technique is rigorous. This is of course in accord with Hilbert's definition of mathematics as a logical game played with symbols on a piece of paper.

Maybe one of the old programming languages such as PROLOG would be an interesting one to attempt to use in producing a computational method.??

[Guest]

Well, the point is that the "Trial" in "Trial and Error" is a guess. The "Error" part is seeing what happens. You can't start T&E without a guess - that's what it means. The fact that you go on to find a contradiciton or the solution is self evident really - unless you stop doing the puzzle, then you've only "Trialled", and not "Errored" :o)

[Thumbs]

Well, the point is that the "Trial" in "Trial and Error" is a guess. The "Error" part is seeing what happens. You can't start T&E without a guess - that's what it means. The fact that you go on to find a contradiciton or the solution is self evident really - unless you stop doing the puzzle, then you've only "Trialled", and not "Errored" :o)

Let's examine these goals.
1. to find a solution
2. to prove that the solution is unique

If logic alone is used, and a solution is reached without having to resort to a guess, then we can accept that the solution is unique. Both goals achieved.

If logic is used, and a solution is not reached, then the approach to take is to make a guess for a possible value in a cell. If there are only two possibles in that cell, and the guess leads to a solution via logic alone, then you would know that you have one out of one or more solutions. Goal 1 is achieved, but not 2. By taking the other possible as a guess, and using logic alone, you would know that you had a unique solution if the second guess results in an invalid solution.

Of course, if there were 3 possibles in the chosen cell, you would need to do these steps 3 times instead of 2. Also, if logic did not arrive at a solution, and a second guess was required to advance, then you have more paths to follow to prove whether the solution is unique.

[Guest]

As milobird pointed out, whether you call it logic or proof by reduction or proof by contradiction or trial and error, all methods of solving are fundamentally the same. Most people's distiction between logic and trial and error seems to depend on how much you write down and how much you do in your head.

A good example is part 4 (Raising Numbers) in the "how to solve" section of the web site.

Most people would regard the deduction that 5 belongs in the second box as "logical", but the process to get there looks more like "trial and error".

Following the steps, we can determine that 4 and 7 can both go in either box 1 or 3, but not box 2. As it stands this does not tell us anything about where 5 can go. 5 can still go in any of the boxes without breaking the rules.

To conclude where 5 goes, you actually need to say:

a) If 5 is put in box 1, and 4 in box 3, then 7 would go in box 2 and this would break the rules.
b) If 5 is put in box 1, and 7 in box 3, then 4 would go in box 2 and this would break the rules.
c) If 5 is put in box 2, and 4 in box 1, then 7 would go in box 2 and this would break the rules.
d) If 5 is put in box 2, and 7 in box 1, then 7 would go in box 2 and this would break the rules.

Having eliminated all other possibilities, 5 must go in box 2. This is logical deduction whether you write it down or not.

All steps to a correct solution require comparing the available choices against the rules and looking for contradictions.

In its simplest extreme, every number you put in is actually determined by the process "This number could be any of 1-9, but it must be x because all other numbers would result in one of the rules being broken".

In its most stretched extreme, a totally "trial and error" approach, you could try every possible combination of 1-9 in each of the available squares, and check each completed grid against the rules until you find one that doesn't contain inconsistencies.

Since all of these use the same basis for determining correctness, they are all as valid as each other, and all equally logical.

[Guest]

I guess I'm not most people then! I make no distinction about what's on the page or in my head, just whether or not I trial something and look for an consequent error.

Perhaps it makes it clearer to define non-T&E methods. They all involve recognising a pattern, and making inferences, without trying anything out (either on paper, in the mind, or even supernaturally quickly in another universe).

It's probably normal to use T&E when we see a new pattern to convince ourselves of the validity of the inferences the first, and maybe the second and third times, but once you stop doing this and take it on faith, you are no longer doing T&E. "Logic" is a terrible term to use really - it is not the opposite of T&E at all, nor does it exclude T&E. You call even argue T&E is more logical than pattern recognition.

But, and this is the important point, it is possible to solve these puzzles by pattern recognition alone (once you know enough patterns), and thus never resorting to T&E.

T&E is a learning process, pattern recognition is how you use what T&E taught you.

So, if you can't see a useful pattern, or you can't convince yourself of the validity of the inferences then you will need to try a few things and see what happens.

Unfortunately the example Falkir quotes isn't a very good one - very basic reduction (much simpler than that page suggests) will tell you that the cell r1c2 is a 5: Because there are three digits still needing to be placed in box 1 (4, 5 & 7), and row 2 already has two of them (4 & 7), cell r1c2 has to be a 5. So in this case, the steps Falkir describes are certainly unnecessary, but even in more complicated situations (and there are some), there is always an underlying pattern that can be used to identify the next move - To me, the trick, the challenge and the fun of these puzzles is learning the patterns and getting the knack of spotting them, even when you've stared at the thing for 2 hours without getting anywhere.

I have to say that I am continually baffled by the ambiguity people see in the term "Trial and Error". It is what it says it is.

Rant over!

[Pappocom]

To Jayal (and to Animator and Sue de Coq, who replied to Jayal).

This part of the thread has been moved to the "Non-Pappocom" forum, under the heading "Multiple solutions".

- Wayne

[tannedblondbloke]

If there are multiple solutions, then trial and error is the only way to reach a solution. A "logical" approach (quote marks deliberate, see below) works step by step eliminating impossible cases (erasing pencilmarks, if you like), and eventually you will run out of steam and not make any more progress. The approach can't eliminate possible cases!

What's the simplest "multiple solution" one could construct? Suppose in a completed grid of a puzzle with a unique solution, digit x appeared in cell (row1,col1) and (row2,col2), and y appeared in cell (row1,col2) and (row2,col1), and that of these 4 cells, 2 appeared in one box and two another. At least one of these 4 cells must have been a clue. For if not, within these 4 cells only, we could swap x and y without affecting the number of occurrences of each digit within each unit, and thus we would have another solution. So, let's remove any clues in these 4 cells, and try and solve the problem again. We will eventually fill in at most (I'm sure we can drop the words "at most", but don't fancy proving this right now) the other 77 cells, and have 4 cells left each containing the pencilmarks x and y, with no means of deciding logically which possibilities to eliminate. 2 rows, columns and boxes each have 2 candidates for 2 vacancies.

Ok let's move on - we've covered the multiple solution case. Now suppose there is a unique solution. Then "logic" and trial & error strictly speaking coincide! For "reductio ad absurdum" is a perfectly logical technique proof found in many books on logic. What it says is that if we make just one assumption A, and this leads eventually to a conclusion, than we have LOGICALLY PROVEN that A is FALSE. More generally, if we make assumptions A1, A2, ... An and get a conclusion then at least one is false - so if we continue to assume A1 through An-1, then under those assumptions we deduceAn is false. And this approach underpins the backtracking approach used in an exhaustive search of a solution.

In fact reductio ad absurdum underpins the simplest rules we apply in solving Sudoku. We are applying it every time we erase a pencilmark. ("Sticking 9 in (x,y) means there are too many 9s in column y - so let's erase pencilmark 9 from (x,y)")

So in theory logic and trial and error are the same thing. Of course in practice they are very different. The point is, how far ahead from making a tentative assumption do we need to apply pattern recognition techniques before we find a contradiction? Even if it's 20 or 30 steps ahead, we still have proven logically that the assumption is false, but it's tedious and noone is going to enjoy solving that sort of puzzle. The regular Milo rules, and certain other pattern techniques, allow us to eliminate possibilities immediately (without looking ahead). But we also have a half way house (and here I am on shaky ground as I haven't got my head round these techniques) of swordfish and nishio, where I understand we need to look ahead a handful of steps. And where do we draw the line between this halfway house (where many, though not all, agree this is a "logical" approach) and the 20 to 30 steps of a truly hard T&E approach, or 81-#clues steps ahead of an exhaustive search (which are strictly speaking "logical" under reductio ad absurdum?)

So when we say Pappocom puzzles are solvable without T&E, I guess what we're really saying is that they are solvable without having to make assumptions and then having to look ahead one or more moves to see is that assumption leads to a conclusion. And hence (back to this shakky ground) without needing to resort to techniques sucha s swordfish and nishio?

[Guest]

has anyone published the rules been for constructing sudoku puzzles? (I don't mean the rules that solvers use to complete the puzzles, but the rules for deciding which cells are left blank when a game is presented.) If not, talking about whether all sudoku puzzles have a unique solution is meaningless - for example, depending on the set of rules chosen then a completely blank board (which clearly has multiple solutions) might be possible, though rather boring.

My gut feel is that Pappocom is fair, in that cells are only blanked if the value can be uniquely determined, and that solutions are unique - but I also suspect that Pappocom is not going to tell us, since (a) it adds nothing to the game to know; (b) it might not be true; and (c) telling us would lead to pressure to reveal the construction rules so that people can try proving uniqueness - but knowledge of the rules could make it easier to solve the published problems.

More interesting questions, that can be addressed without knowledge of Pappocom's construction rules, are on the limits: for example, what is the smallest board (eg, with the biggest number of blank cells) for which there is a unique solution? What is the largest board possible with more than one solution?

[Animator]

There are some intresting threads about the creation of puzlles in the 'Solver programs'-board... I suggest you look at it...


The largest puzzle whit multiple solutions is really simple: a puzzle with only 4 empty cells can have multiple solutions (2 solutions to be correct)...

[Guest]

"Trial and Error" is a logical way of discerning impossibilities. It is most commonly used in science. For example I create a hypothesis about pigs sayign all pigs fly, i have no dea weather this is the case but i go find a pig and it does not fly. therefore all pigs fly is use of logic. an example without logic would be all pigs cannot fly where i go out into the world and find a pig which cannot fly. i could then say this pig cannot fly. this is the finding a solution from the trial and error, which tells you nothing. the first example tells you all pigs do not fly actually eliminating a possibility.

This is logic. in the puzles you look and say this number cannot go here because of another number but is that not the same as saying if i place this number here another number cannot go in an adjacent square so the first number is incorrect? really saying this number cannot go here because of this another is saying this number cannot go here because any other number that could go here would be wrong. one action is preformed subconsciously while the other consciously but both are examples of logic, as is brute forcing a problem. think about it, there is a 32bit number and you have to find out what it is. the logical way it to try 1, then 2, then 3...4294967296. that is brute force, and that is logic, if one does not work try another, or said another way, if all these soultions are impossible, this one is possible. if i say there is not 7 or 9 in it you would try all numbers from 1 to 4294967296 that do not contain 7 or 9, this is how logic works. illogical behavior is trying numbers with 7 or 9, knowing they do not work.

[Guest]

Suppose a puzzle has no solution, if you use T&E when do you stop trying and say this puzzle has no solution.
Whereas if you use logic surely you can reach the conclusion that this puzzle has no solution a lot sooner.

[sudokuist]

Surely each puzzle has only one solution if it is logically solveable. If a puzzle starts with only a two in one of the squares then there are a number of variations and many puzzles with this combination. Therefore if a puzzle is incomplete in its outset only it will have many solutions.
If a puzzle is set correctly it will only have one solution.
If a puzzle is a just a minimal amount of random squares completed then it will have many solutions.
Further I agree with those that do not distingush between logic and trail and error. One is just an advanced form of the other.