I'm dredging up this old chestnut because I just caught an article in

Scientific American (March 2006 pp. 74-81) which is related to the idea of complexity versus useful logical theory. The article entitled

The Limits of Reason was written by Gregory Chaitin, the pioneer of algorithmic information theory.

Summarizing the article--Gottfried W. Leibniz made the observation in his 1686 essay,

Discourse on Metaphysics, that a theory has to have an quality of simplicity, otherwise it does not explain anything. If you allow theories and laws unlimited complexity, then you can devise a theory to explain any random set of data; but that theory is essentially meaningless.

The algorithmic information theorists have quantified this concept of complexity versus theory. In essence, they state that for a theory to have any teeth, it must be simpler than the data it explains.

So how does this all relate to a sudoku puzzle and our proposed "logical methods"? Well, say you have a theory which allows you to eliminate a particular candidate in a particular cell. For most cases, your "theory" consists of all of the candidates that you needed to make your deduction. On the other hand, your "data" is the number of candidates you need to consider if you happened to randomly assume that the candidate you eliminated was true and then followed things along until the puzzle crashes. If your number of theory candidates is less than your number of data candidates, then you have the makings of a viable theory or logical method.

Take as an example, the naked pair in the following row...

- Code: Select all
`12 12 13 34 45 56 7 8 9`

The naked 12-pair uses precisely four "theory" candidates to eliminate any other 1's and 2's in the row, in this case, the 1 in the third cell. Now if we assume the third cell is a 1, that is one candidate of data. That eliminates the 1's from the first two cells (3 candidates of data so far). That leaves only a 2 in both those cells for a total of 5 data candidates involved in the crash. The theory is smaller than the data, thus making it useful.

What this is saying, in essence, is that a useful theory must provide some "action at a distance." One apparently necessary requirement for a sudoku method to be less complex than the data it explains is for the deduction to apply to a candidate which is

not a part of the method/theory/pattern.

An article similar to the one appearing in SA is

http://plus.maths.org/issue37/features/omega/Gregory Chaitin's home page with lots of related links is

http://www.umcs.maine.edu/~chaitin/