Sudoku Solver

Sudoku is a logic puzzle consisting of filling a 9x9 grid with the digits 1 through 9. Each digit must appear exactly once in each row, each column, and each of the nine 3x3 blocks.

Variations exist with different grid sizes or with symbols (letters, icons). The mathematical structure remains the same: it is a constraint satisfaction problem where each symbol must adhere to local uniqueness rules.

The grid can be filled by copying and pasting a sequence of 81 characters (numbers or symbols), or by directly entering the values into the cells.

The numbers $ 1 $ to $ 9 $ are accepted. For Wordoku-style variants, letters can also be used, provided that 9 distinct symbols are employed.

The program solves 9x9 Sudoku puzzles like a human would, by combining logical deductions.

— Candidate calculation: For each empty cell, dCode determines the set of possible values compatible with the row, column, and block constraints.

— Only possible value: If a cell has only one candidate, that value is validated.

— Only possible cell: If, for a given number, only one cell in a row, column, or block can contain it, that value is validated.

In a standard 9x9 grid, a block (also called a region, group, sector, or subgrid) is a 3x3 square. There are 9 blocks in total.

dCode calculates all the solutions for the sudoku, not only the first one. To check a homemade sudoku, the solver can confirm that there is only one solution.

The modern form of Sudoku was published in 1979 by Howard Garns in the American magazine Dell under the name Number Place.

The game was later popularized in Japan in the 1980s by the Nikoli company, which named it Sudoku, a contraction of Sūji wa dokushin ni kagiru, meaning numbers must remain unique.

A single row can consist of $ 9! $ (Factorial of 9) different ways, same for the columns, but the whole sudoku has a number of possibilities much less than $ 9!^9 $, because some permutations can lead to identical grids. The total number of grids is $ 9! \times 72^2 \times 2^7 \times 27704267971 = 6670903752021072936960 $ combinations (result demonstrated in 2005).

For a sudoku to have only one solution, it must have at least 17 pre-filled boxes out of the 81 total. Gary McGuire and his team proved this here by using an algorithm to perform a systematic computer search. They first cataloged the 5,472,730,530 distinct sudoku puzzles. Next, they created a program to check whether sudoku puzzles with 16 pre-filled squares had a unique solution. Their exhaustive search found no sudoku with only 16 pre-filled squares having a unique solution, thus confirming the minimum number of 17 pre-filled squares needed.

By keeping the sudoku NxN rules that require the N characters to be used on each row and column, then it is impossible to respect them if the sudoku is not square.

Some variants of the square sudoku, however, use non-square inner blocks (see sudoku 6x6, sudoku 7x7 or sudoku 8x8)