How to generate Sudoku boards with unique solutions

by

Here is the way my own SuDoKu program does it:

  1. Start with a complete, valid board (filled with 81 numbers).

  2. Make a list of all 81 cell positions and shuffle it randomly.

  3. As long as the list is not empty, take the next position from the list and remove the number from the related cell.

  4. Test uniqueness using a fast backtracking solver. My solver is – in theory – able to count all solutions, but for testing uniqueness, it will stop immediately when it finds more than one solution.

  5. If the current board has still just one solution, goto step 3) and repeat.

  6. If the current board has more than one solution, undo the last removal (step 3), and continue step 3 with the next position from the list

  7. Stop when you have tested all 81 positions.

This gives you not only unique boards, but boards where you cannot remove any more numbers without destroying the uniqueness of the solution.

Of course, this is only the second half of the algorithm. The first half is to find a complete valid board first (randomly filled!) It works very similar, but “in the other direction”:

  1. Start with an empty board.

  2. Add a random number at one of the free cells (the cell is chosen randomly, and the number is chosen randomly from the list of numbers valid for this cell according to the SuDoKu rules).

  3. Use the backtracking solver to check if the current board has at least one valid solution. If not, undo step 2 and repeat with another number and cell. Note that this step might produce full valid boards on its own, but those are in no way random.

  4. Repeat until the board is completely filled with numbers.

More Related Contents:

  1. Expand a random range from 1–5 to 1–7
  2. How to find list of possible words from a letter matrix [Boggle Solver]
  3. How to find all combinations of coins when given some dollar value [closed]
  4. Finding a single number in a list [duplicate]
  5. Algorithm to generate anagrams
  6. Efficiently reverse the order of the words (not characters) in an array of characters
  7. Programming Riddle: How might you translate an Excel column name to a number?
  8. Fastest algorithm for circle shift N sized array for M position
  9. How to print all possible balanced parentheses for an expression?
  10. Find a pair of elements from an array whose sum equals a given number
  11. Find all paths between two graph nodes
  12. Sort points in clockwise order?
  13. How do you calculate the average of a set of circular data? [closed]
  14. Algorithm to check similarity of colors
  15. Why do we use Base64?
  16. Heap vs Binary Search Tree (BST)
  17. Mapping N-dimensional value to a point on Hilbert curve
  18. Find the paths between two given nodes?
  19. Finding all the shortest paths between two nodes in unweighted undirected graph
  20. Fastest primality test
  21. Efficient maths algorithm to calculate intersections
  22. How to calculate or approximate the median of a list without storing the list
  23. Sort Four Points in Clockwise Order
  24. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  25. Obfuscating an ID
  26. Algorithm for autocomplete?
  27. An inverse Fibonacci algorithm?
  28. Design an efficient algorithm to sort 5 distinct keys in fewer than 8 comparisons
  29. Check if array B is a permutation of A
  30. Algorithm to list all unique permutations of numbers contain duplicates

Leave a Comment