In the article " Solving Sudoku using a webcam, " most solutions are implemented very nicely, with the exception of the solver itself. In one of my old projects, “Solver Sudoku”, there was an attempt to select an algorithm with a set of heuristics for solving the standard sudoku problem (field 9x9). The option of direct brute force was not considered.


Several heuristics (algorithms 1-4) and a meta-algorithm for their application are proposed. Experiments have shown that all the proposed tasks were solved regardless of the level of complexity, although I have no formal proof of rigor, completeness or convergence.

Sudoku rules

• A field of 9x9 cells is used, divided additionally into 3x3 blocks of 3x3 cells.
• Each cell can contain a digit from 1 to 9
• It is not allowed that two or more identical figures stand vertically, horizontally and inside each of the 3x3 blocks.
• Purpose : Fill in a partially filled field.

Terminology

Field - all field sudoku 9x9
The complete cell is the cell for which the value is set. This may be a figure given in the formulation of the problem, or found during the operation of the algorithm.
An empty cell is a cell for which a value has not yet been found.
A block is one of the 3x3 blocks to which the cell belongs.
Forecast - a list of possible values ​​for empty cells.
The forecast length is the number of possible values ​​for empty cells.
')

Algorithm number 0. Forecast recalculation

In accordance with the Sudoku rules and the current state of full and empty cells, for each empty cell, collect a list of possible values. If there is only one predictive digit left in the cell, fill it with this digit.

Algorithm number 1. Basic control rules

For each empty cell: from the forecast we remove the numbers from the corresponding full cells (horizontally, vertically and in the block). If there is only one predictive digit left in the cell, fill it with this digit.

Algorithm number 2. We are looking for doubles

For each empty cell, we look for other cells with the same prediction — for the row, column, and block. If the total number of such cells (for a column, row or block) is equal to the length of the forecast, remove the forecast figures from all the other cells except those found. If there is only one predictive digit left in the cell, fill it with this digit.

Algorithm № 3. Excess forecast

For each empty cell + for each predictive digit in this cell, we are looking for at least one other empty cell (in a row, column, or block), where this digit is also present. If not found, fill this cell with this digit.

Algorithm # 4. Partial brute force with negative control

We take the first cell with the shortest forecast and for each digit of the forecast: fill the cell with this digit, repeat the execution of Algorithm 0, while the forecast length for all cells is> 0 and the field is filled correctly in accordance with the Sudoku rules. If we encounter a negative result, we consider that the figure of the forecast taken as a basis leads to a dead end and remove it from the forecast. If the result is positive, but the field is not completely filled, take the next predictive figure or the next field.

META Algorithm

Perform sequential algorithms 1-4. If the result of the operation of any algorithm led to the filling of the cells, check the completeness of the field. If not filled to the end, then return to Algorithm 0. If filled, check the correctness of filling in accordance with the rules of sudoku and complete the work.

The proposed heuristic algorithm has a major drawback - there is no guarantee of convergence. In addition, the proposed four heuristics may be insufficient or they will not be very effective. With gratitude, I will accept any thoughts on improving the algorithm, evaluating its completeness and new ideas on heuristics.