"Solvable by logic" versus "Not solvable by l

vindaloo

I was thinking about what would make a meaningful distinction between the 2 cases - solvable and not solvable by logic. For example where does nishio fit in?

Well one objective definition would be:

1. Solvable by logic = a fast algorithm exists to solve it
2. Not solvable by logic = no (known) fast algorithm exists

Note we are only considering deterministic algorithms here (probabilistic algorithms would give you another consideration).

For a computer given a 3x3 sudoku puzzle for practical purposes it doesn't matter whether you use a fast algorithm (i.e. using "rules") or a slow algorithm (i.e. trial and error). However clearly as we scale up the size of the sudoku grid the distinction does become apparent.

A 100x100 sudoku will not be solvable any time soon by brute-force (trial and error).

Indeed we know that Sudoku is an NP-complete problem. In other words there exists no fast (poynomial time) algorithm to solve the general nxn sudoku problem (unless P=NP).

So where does nishio fit in? Well in nishio we choose a box and commit a choice, then see if any contradictions result. As long as we don't allow recursive application of this rule then it is a fast algorithm (although perhaps because it is fast it is of limited use).

There may be other rules out there that could be useful in the generalized nxn sudoku problem, but in general sudoku puzzles (even if they have a unique solution) are not solvable by logic - if you define logic as I have to mean a fast deterministic procedure.

Vin.