by **tannedblondbloke** » Sat Apr 23, 2005 8:44 pm

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?