Add random Sudoku generation feature

[pavolmarak]

According to the post titled "Sudoku Generator" written by David Bau in his web blog A Dabbler's Weblog, my early strategy for generating/filling the Sudoku board will be based on seeding the board with few numbers and than solving it with my own Sudoku solving algorithm. The most important thing to bear in mind is that a generated Sudoku grid must have a single solution. Another aspect of creating a Sudoku grid is the number of hints revealed. Currently, Sudoku boards with no less than 17 cells revealed are considered to be puzzles with smallest number of hints that still have a single solution.

David Bau says that he employed his own Sudoku solver to empty grid to get fully filled board. At the beginning, all the squares are considered hidden. Then, he starts revealing squares (hints) of the board in a way that the puzzle must still have a single solution with minimal hints. The procedure has 2 stages:

1. He goes through each square in random order and reveal it only if it cannot be deduced by other revealed squares. This produces around 30-40 hints, what is still too much.
2. Then he narrows down this number by examining each of the revealed squares, again in random order, and tries to drop it. He drops the hints until he finds two (or more ???) solutions.

He remarks that this requires to solve the Sudoku board around 20 times, so generating is harder than solving.

[pavolmarak]

Ross Harrison wrote the excellent article titled Generating Sudoku Boards pt. 1: Structure & Algorithm that is published at medium.com. In the article, he discusses the algorithm for Sudoku board generation he invented. I was happy to find this piece of information because it matches my own thoughts on how to create the Sudoku generator. His whole idea is based on a naive approach where one generates numbers beginning at the top-left corner and continues from left to right and row by row. As we soon discover, this algorithm will often fail because we may get into situation when it is not possible to place a number at the given cell, because its neighbors have already exhausted all valid numbers.

This technique was the first to come across my mind and I thought I am so stupid that I could not find anything better. It was a great pleasure to discover I was not the only one to start with this idea. The author fixed the algorithm's dead end by adding backtracking using recursion. In short, for each cell we loop through all possible valid numbers that can be placed in it, we assign the cell first possible valid number (or option) and than recursively repeat the same procedure for the next cell. This ensures that if the cell in question cannot be assigned any number, than we backtrack to change some of the previous cells in order to fix it. This way we can always fill the Sudoku board. The author also provided the nice animation of Sudoku board filling along with some backtracking situations.

In my final words, I would like to thank Ross Harrison for giving me a crazy good kick-off point for my own Sudoku puzzle generator in Qt.

[pavolmarak]

It is very important to generate Sudoku puzzle that has only one solution. The fewer the number in the board, the higher the chance of having more solutions. Number of revealed Sudoku cells also influences the difficulty of the puzzle. Minimum number of Sudoku clues while keeping a single solution is still probably unsolved problem. I have found that 17 is the number that many believe to be the limit for minimum number of clues of a single-solution Sudoku board.

Gordon Royle maintains a database of Sudoku boards with 17 clues. He states there are no known examples of Sudoku boards with 16 clues. It can be acquired here. In case of having difficulties generating such boards, it is more than good starting point for my application. This way I can provide a player more difficult boards and I can also test performance of my solving algorithm.