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.