Sudoku

Rules

The main rules are quite simple and was discovered by Howard Garns. So they are:

• in the table 9×9 fill numbers 1-9
• each row must contain all numbers 1-9 (so none can repeat)
• each column must contain all numbers 1-9 (so none can repeat)
• each square 3×3 starting on 0,0; 3,0; 6,0; 3,0; 3,3; 6,3; 6,0; 6,3; 6,6 must contain all numbers 1-9 (so none can repeat)
• that's it.

Math background

Mathematically, Sudoku can be seen as a type of constraint satisfaction problem (CSP). A CSP is a formal framework for representing and solving problems where you have a set of variables, each with a domain of possible values, and a set of constraints that specify the allowed combinations of values for the variables. In the case of Sudoku:

Variables: Each cell in the 9x9 grid is a variable.

Domain: The domain of each variable is the set of integers from 1 to 9.

Constraints: The constraints are the rules of Sudoku, which state that no row, column, or 3x3 subgrid can contain repeated digits.

The goal is to find a solution that assigns a value to each variable (fills in each cell) such that all constraints are satisfied.

Sudoku puzzles can have varying levels of difficulty, with some puzzles requiring more complex solving strategies than others. There are techniques and strategies that can be employed to solve Sudoku puzzles, ranging from simple elimination and candidate checking to more advanced methods like "naked pairs ¹⁾," "hidden singles ²⁾," and "X-wing ³⁾." These strategies are based on the logical deductions derived from the mathematical properties of the puzzle.

Mathematicians and computer scientists have also studied the complexity of Sudoku and have found that it is NP-complete, meaning that finding a solution to a Sudoku puzzle is a computationally difficult problem. However, for typical human-designed Sudoku puzzles, efficient algorithms can quickly find solutions.

In summary, Sudoku is a mathematical puzzle that can be formalized as a constraint satisfaction problem, and it has been the subject of mathematical analysis and algorithmic study.

1) Naked Pairs:

• In a row, column, or box, if you find two cells that both contain the same pair of possible numbers (candidates), these cells form a "naked pair."
• You can then eliminate those two candidate numbers from the rest of the cells in the same row, column, or box.
• It simplifies the puzzle by revealing additional numbers.

2) Hidden Singles:

• A hidden single occurs when there is only one candidate number left in a particular row, column, or box for a given cell.
• Even though there may be multiple candidates listed for a cell, only one of them is a valid option when considering the other numbers in the related row, column, or box.
• Identifying and placing this hidden single can lead to further deductions.

3) X-wing:

• The X-wing technique is applied when there are two rows and two columns where a particular digit can only appear twice in each row and twice in each column, forming the shape of an "X" in the grid.
• In this situation, you can eliminate the possibility of that digit in other cells in the intersecting rows and columns.
• It's a bit more complex but powerful when applicable.