Sudoku

A 9x9 Sudoku puzzle isn't just a random assortment of numbers. If a developer just placed numbers randomly, it's highly likely the puzzle would be completely unsolvable.

To create a valid puzzle, the computer first creates a completely full, fully solved 9x9 board. It does this using a computer science technique called Backtracking.

1. The computer looks at the first empty cell and guesses a number (e.g., 1).
2. It moves to the next cell and guesses another number, ensuring it doesn't violate Sudoku rules (no duplicates in the row, column, or 3x3 box).
3. If it reaches a cell where no valid numbers can be placed, it realizes it made a mistake earlier. It "backtracks" to the previous cell, erases the guess, and tries a different number.

This algorithm aggressively searches through the tree of possibilities. Because computers process millions of operations per second, a backtracking algorithm can perfectly fill a 9x9 board in a fraction of a millisecond.

Once the full board is generated, the game starts deleting numbers one by one to create difficulty. To ensure the puzzle still has exactly one unique solution, the backtracking algorithm is run again after every deletion to verify that a human could still logically deduce the missing number.