![sudoku puzzle generator algorithm sudoku puzzle generator algorithm](https://media.geeksforgeeks.org/wp-content/uploads/sudoku.jpg)
It also does well with naked tuples, giving branching factors of 2 for naked pairs, 3 for naked triples, and so on.
![sudoku puzzle generator algorithm sudoku puzzle generator algorithm](https://codepumpkin.com/wp-content/uploads/2017/03/sudoku.png)
The solver described above does well when the puzzle contains naked singles, requiring no backtracking. However, this naive approach does not correlate well with actual difficulty unless a modification is made to the solver algorithm. E is included to bias the puzzle generator in the direction of fewer clues, given multiple puzzles with the same branch-difficulty.Ī puzzle which requires no backtracking ends up with a final score of less than 100. Where B is the branch-difficulty score and E is the number of empty cells. The final score is given by: S = B * 100 + E A solution which requires no backtracking at all would thus have a branch-difficulty score of 0. We compute a branch-difficulty score by summing (B i - 1) 2 at each node, where B i are the branch factors. A quick and easy method that correlates roughly with difficulty is to keep track of the branch factor at each step on the path from the root of the search tree to the solution. Difficulty estimationĮstimating the difficulty of a Sudoku puzzle is a tricky problem because of the variety of techniques human solvers use. We can then distinguish between three cases:įor a puzzle to be valid, it must be uniquely solvable.
![sudoku puzzle generator algorithm sudoku puzzle generator algorithm](https://lvngd.com/media/images/solvedsudoku.2e16d0ba.fill-500x500.png)
The modified solver terminates when the search tree is exhausted, or when at least two solutions have been found. However, for generating puzzles we need a solver which continues after finding a valid solution. In order to solve a puzzle, we normally terminate the algorithm once a valid solution is found or the search tree is exhausted. This is O(N) in the size of the puzzle, whereas analysing from scratch is O(N 3). When analysing the candidate values for empty cells, it’s much quicker to start with the analysis of the previous step and modify it by removing values along the row, column and box of the last-modified cell. As values are added to the grid, the number of candidates for other cells reduces too. When choosing a cell, always pick the one with the fewest candidate values. There are two optimizations which greatly improve the performance of this algorithm: If the cell has no candidate values, the puzzle is unsolvable.įor each candidate value in that cell, place the value in the cell and try to recursively solve the puzzle. If none are available, the puzzle is solved. Generate, for each cell, a list of candidate values by starting with the set of all possible values and eliminating those which appear in the same row, column and box as the cell being examined.Ĭhoose one empty cell. The basic approach to solving a Sudoku puzzle is by a backtracking search of candidate values for each cell. In the following, the time complexities are specified with N being the width/height of the grid (9 for regular Sudoku).
Sudoku puzzle generator algorithm code#
Source code for an implementation of this algorithm is also provided. It also gives an algorithm which can be used to generate difficult puzzles reliably and efficiently. This article explains a simple method to quickly estimate the difficulty of a Sudoku puzzle which correlates reasonably well with human estimates of difficulty. Generating difficult Sudoku puzzles quickly