The New Sudoku Players' Forum

[normxxx]

I discovered Sudoku less than two weeks ago. The main problem in solving such puzzles is usually that you have to keep track of many things and make sure you do not make any careless errors. This does not appeal to me. However, as a retired computer scientist, the technical problem of programing a Problem Solver appealed to me, especially as two possible algorithms immediately occurred to me. (I believe these were the two 'logical' algorithms that occurred to your mathematician.)

What we have is a matrix of three sets of nine nine-cell vectors (box, line, and column) which overlap since, as defined, there are only 81 total cells, with each cell having a representation in each of the three vector sets.

The program starts by placing a "123456789" in each cell of the matrix.

Algorithm 1:
For each nonsingleton cell of the matrix, the program reduces its original set of numbers by any unique singletons in that cell's box, line, and column vectors. This is an iterative process which does not complete until no more cells 'reduce' to singleton cells.

Algorithm 2:
For each nonsingleton cell of the matrix, the program checks that there are duplicates for every remaining number in that cell for each box, line, and column vector. If it finds any number in a cell which is unique to any of that cell's vectors, it forces that cell to that number. Whenever a cell is forced to a singleton, we redo Algorithm 1.

This approach solved all of the easy and (so far) all of the medium puzzles I have encountered. It does not work for the "hard" ones.

I have a third algorithm which has been tested (but not yet programed). Unfortunately for "purity," it is a "trial and error" approach, which are shunned alike by "purists," mathematicians, and computer scientists-- they are not "elegant."

Algorithm 3:
Look for dupleton cells. Having found one, proceed only if there is another dupleton in that cell's vector set which matches at least one of its numbers. If so, force the cell to that number and redo Algorithms 1 and 2 until there are no more changes. If we have a solution, fine. Otherwise, we try the second number for the cell (if it passes the 'nonuniqueness test'), or go on to the next dupleton. This has solved the "hard ones" I've tried so far.

However, I recogize that this cannot be proved to produce a solution. In anticipation, I am working on a generalization of Alg-3 (e.g., a 'multi-pass' trial and error), or Alg-4 (no ideas yet).

[normxxx]

Several days ago, I posted the following message (in italics, with corrections):

I discovered Sudoku less than two weeks ago. The main problem in solving such puzzles is usually that you have to keep track of many things and make sure you do not make any careless errors. This does not appeal to me. However, as a retired computer scientist, the technical problem of programing a Problem Solver appealed to me, especially as two possible algorithms immediately occurred to me.

What we have is a matrix of three sets of nine nine-cell vectors (box, line, and column), or 27 9-cell vectors in all, which are not independent since, as defined, there are only 81 total cells, with each cell having a representation in each of the three vector sets.

The Program is an Elimination Algorithm Process.

The program starts by placing a "123456789" in each cell of the matrix which is not already occupied by a single digit (singleton).

Algorithm 1:
For each nonsingleton cell of the matrix, the program reduces its original set of numbers by any unique singletons in that cell's box, line, and column vectors. This is an iterative process which does not complete until no more cells 'reduce' to singleton cells.

Algorithm 2:
For each nonsingleton cell of the matrix, the program checks that there are duplicates for every remaining number in that cell for each box, line, and column vector. If it finds any number in a cell which is unique to any of that cell's vectors, it forces that cell to that number. Whenever a cell is forced to a singleton, we redo Algorithm 1.

This approach solved all of the easy and (so far) all of the medium puzzles I have encountered. It does not work for the "hard" ones.

I have a third algorithm which has been tested (but not yet programed). Unfortunately for "purity," it is a "trial and error" approach, which are shunned alike by "purists," mathematicians, and computer scientists-- they are not "elegant."

Algorithm 3:
Look for dupleton cells. Having found one, proceed only if there is another dupleton in that cells vector set which matches at least one of its numbers. If so, force the cell to that number and redo Algorithms 1 and 2 until there are no more changes. If we have a solution, fine. Otherwise, we try the second number for the cell (if it passes the 'nonuniqueness test'), or go on to the next dupleton. This has solved the "hard ones" I've tried so far.

However, I recognize that this cannot be proved to produce a solution. In anticipation, I am working on a generalization of Alg-3 (e.g., a 'multi-pass trial and error), or Alg-4.

@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

Old Algorithm 3 is a Trial and Error algorithm; but I have since determined that there is (at least) another set of logical, deterministic, related algorithms which can be employed. Therefore, I have dubbed these NEW algorithms Algorithm 3 and 4, and renamed the old, T&E Algorithm 3 to Algorithm 20.

For each of the following algorithms, when any number(s) eliminated from any cell results in a singleton digit remaining for that cell, we restart with Algorithm 1 (followed by Algorithm 2).

Algorithm (NEW) 3a:
Search for matching dupletons in each of the 27 vectors. If a matching pair of dupletons is found, both of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these two digits.
Algorithm (NEW) 3b:
Search for matching tripletons in each of the 27 vectors. If three matching tripleton cells are found in a vector, all three of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these three digits.
Algorithm (NEW) 3c:
Search for matching quadrupletons in each of the 27 vectors. If four matching quadrupleton cells are found in a vector, all four of their digits can be eliminated from every other cell in the vector in which they occur, since these matching cells absolutely determine the only legal locations of these four digits. (This can be repeated for five matching quintupletons, six matching sextupletons, etc.)

Algorithm (NEW) 4a:
Search for three dupletons in each of the 27 vectors, such that they share only three unique digits. If such a triple cell set of dupletons is found, all three of their three (unique) digits can be eliminated from every other cell in the vector in which they occur, since these three cells absolutely determine the only legal locations of these three digits.
Algorithm (NEW) 4b:
Search for four tripletons in each of the 27 vectors, such that they share only four unique digits. If such a quadruple cell set of tripletons is found, all four of their (unique) digits can be eliminated from every other cell in the vector in which they occur, since these four cells absolutely determine the only legal locations of these four digits.
Algorithm (NEW) 4C:
Search for five quadrupletons in each of the 27 vectors, such that they share only five unique digits. If such a quintuple cell set of quadrupletons is found, all five of their (unique) digits can be eliminated from every other cell in the vector in which they occur, since these five cells absolutely determine the only legal locations of these five digits. (This can be repeated for six quintupletons, seven sextupletons, etc.)