The question "how do you generate a Sudoku?" led me to write this simple random Sudoku generator, which also lets you play the puzzle right in the browser. The generator is written in TypeScript and the interface is built with React.
The initial idea was to find a mathematical algorithm to create a sequence of numbers (81 for a 9x9 grid) that satisfies the rules of Sudoku (numbers are never repeated within a row, a column, or a box), but despite several attempts and reading several articles on the subject, I could not find a satisfactory solution.
While waiting to reach that goal, I wrote the rest of the game by generating the Sudokus randomly with a backtracking algorithm, which uses the following process:
- The grid is initialized with 17 random numbers in equally random positions, checking each time a number is added that the board satisfies the rules of Sudoku;
- The result of this first step is given as input to an algorithm that tries to solve the puzzle through backtracking, that is, by finding the first empty cell, trying to put a number in it, and checking that the resulting grid satisfies the rules of Sudoku; if the resulting grid does not satisfy the rules, the number is removed and another number is tried, and once all possible numbers have been tried the solver goes back to the previous cell and tries another number; if the resulting grid satisfies the rules, the solver moves on to the next cell and repeats the process;
- If the puzzle is solvable, the result of this process is a complete Sudoku, which can be used for play simply by hiding from the user a number of cells that matches the desired difficulty level;
- If the puzzle is not solvable, or a maximum number of attempts is exceeded, the puzzle is discarded and the process is repeated.
This approach is, of course, neither perfect nor particularly efficient, but it is good enough for the average case and it is the one used by many other Sudoku generators, although many similar games have a list of predefined puzzles loaded in memory instead of generating them in real time.
The game has the following features:
- Selecting a cell and setting its value;
- Adding and removing notes for each cell;
- Action history, with the ability to undo and redo every action taken;
- Choosing the difficulty level, which determines the number of cells visible at the start;
- Turning on hints, which show for each cell the numbers that can be entered (making the game easier);
- Turning off error display, making the game harder;
- A timer that counts the time taken to complete the puzzle;
The game is very simple and can be played right in the browser, on both desktop and mobile.
- On desktop, you can select a cell by clicking it, enter notes by typing the numbers, and set the number by pressing CTRL + the desired number, or use the numbers below the grid: left-clicking enters the number as a note, while right-clicking sets the number; CTRL+Z and CTRL+Y undo or redo a previous action;
- On mobile, you can select a cell by tapping it, enter notes with the numbers at the bottom of the screen, and enter a number by pressing and holding the desired number; there are also two buttons to undo and redo a previous action.
The game is available at this address.