Sudoku is one of my favorite number puzzles and I have played it quiet a lot. However, my curiosity has pushed me a bit further than just playing Sudoku puzzles, I started wondering how are sudokus generated and what differentiates an easy sudoku to a challenging one, and so on. So, for my university personal project subject, I challenged myself to create a sudoku generator that produces unique sudoku puzzles with the option of choosing the difficulty as well.
Patterns
At first, I was wondering if there are any hidden patterns within the sudoku solutions, patterns that perhaps can be used to generate sudoku puzzles. So, without wasting any time, I started writing down all the combinations and permutations of the range of numbers from 1 to 9; found a sample of 9 million sudoku puzzles online, for which I had to create a small C# program for splitting this data into smaller chunks and loading it into my Unity project, and started testing out and keeping notes on whatever patterns I could find.
During this phase, I was constantly seeking any advice or insights I could get from my colleagues and professors, online forums and so on, in order to back up my findings. Moreover, my current findings at the time seemed to have little to no importance at all, because the sample of puzzles I was working with, was really small compared to the actual number of possible unique sudoku puzzles, which is 6.6 sextillion (6,670,903,752,021,072,936,960) puzzles, so 9 million makes up 0.00000000000013491425351884718% of the total number of possible unique sudoku puzzles. Based on the immense number of possible puzzles, I concluded that I am trying to find a needle in a hay stack the size of the universe. Therefore, I took a step back and started researching again and completely changed my approach towards the process of generating sudokus.
During this phase, I was constantly seeking any advice or insights I could get from my colleagues and professors, online forums and so on, in order to back up my findings. Moreover, my current findings at the time seemed to have little to no importance at all, because the sample of puzzles I was working with, was really small compared to the actual number of possible unique sudoku puzzles, which is 6.6 sextillion (6,670,903,752,021,072,936,960) puzzles, so 9 million makes up 0.00000000000013491425351884718% of the total number of possible unique sudoku puzzles. Based on the immense number of possible puzzles, I concluded that I am trying to find a needle in a hay stack the size of the universe. Therefore, I took a step back and started researching again and completely changed my approach towards the process of generating sudokus.
Unique Sudoku Puzzles & Solving Techniques
During my research on sudokus, I stumbled upon lots of forums and tutorials on how to generate the sudoku puzzles, however, most of them were really simple and disregarded the difficulty options and possible sudoku solving techniques. I spent a few hours on trying to find something relevant to what I was looking for, and finally managed to land on a couple of pages that were worth it. Sudoku Of The Day proved to be an invaluable resource for me to learn about sudoku solving techniques and generating unique sudokus as well. Even though there are many sudoku solving techniques, this site explained the ~14 most used solving techniques by sudoku players.
The sudoku techniques I wanted to implement are: Naked Singles, Hidden Singles, Candidate Lines, Multiple Lines, Naked Pairs, Hidden Pairs, Naked Triples, Hidden Triples, X Wing, Y Wing, Forcing Chains, Naked Quads, Hidden Quads, Swordfish.
I have slightly changed the names of some of the techniques to names that are more common, since there are a few techniques that have different names and it can get confusing at times. Regarding the difficulty of the puzzles to generate, there was already work done on rating the difficulty of each solving technique in numbers. I still made some minor changes to scores and adjusting them for my needs.
The sudoku techniques I wanted to implement are: Naked Singles, Hidden Singles, Candidate Lines, Multiple Lines, Naked Pairs, Hidden Pairs, Naked Triples, Hidden Triples, X Wing, Y Wing, Forcing Chains, Naked Quads, Hidden Quads, Swordfish.
I have slightly changed the names of some of the techniques to names that are more common, since there are a few techniques that have different names and it can get confusing at times. Regarding the difficulty of the puzzles to generate, there was already work done on rating the difficulty of each solving technique in numbers. I still made some minor changes to scores and adjusting them for my needs.
Implementation
After setting up the view for the sudoku board, I went on to implement the basis methods for generating the sudokus:
- Solution generator - fills the sudoku grid with in numbers in a random order while following sudoku rules for each region, row and columns.
- Recursive Backtracker Solver - a recursive function that returns true if the given sudoku puzzle has one solution only, otherwise false if more than one solution is found.
- Human Based Solver with Techniques - a function that tries to solve a sudoku puzzle by applying sudoku solving techniques, returns true if it is able to solve a given puzzle, otherwise false. The human based solver uses an array of bools as notes for every sudoku cell candidates, and most of the sudoku techniques are meant to eliminate candidates from an empty cell, except the Naked Single and Hidden Single techniques which can place an actual number on a sudoku cell.
- Solution generator - fills the sudoku grid with in numbers in a random order while following sudoku rules for each region, row and columns.
- Recursive Backtracker Solver - a recursive function that returns true if the given sudoku puzzle has one solution only, otherwise false if more than one solution is found.
- Human Based Solver with Techniques - a function that tries to solve a sudoku puzzle by applying sudoku solving techniques, returns true if it is able to solve a given puzzle, otherwise false. The human based solver uses an array of bools as notes for every sudoku cell candidates, and most of the sudoku techniques are meant to eliminate candidates from an empty cell, except the Naked Single and Hidden Single techniques which can place an actual number on a sudoku cell.
The reason I decided to use the recursive backtracker is because I wanted to generate unique puzzles as well, and on the other hand this would allow me to keep track of used techniques needed to solve a generate puzzle. Therefore, for a sudoku puzzle, its uniqueness and difficulty makes it necessary to apply some of the techniques in order to be solved.
Implemented Techniques
Currently there are only a few of the techniques implemented, 7 out of 14 technique in total, however with these base techniques, it is possible to generate playable and challenging sudoku puzzles with four different difficulties: Beginner, Easy, Medium and Hard. The implemented techniques are: Naked Single, Hidden Single, Candidate Lines (Pointing Pairs), Multiple Lines, Naked Pairs, Hidden Pairs and Naked Triples.
Currently there are only a few of the techniques implemented, 7 out of 14 technique in total, however with these base techniques, it is possible to generate playable and challenging sudoku puzzles with four different difficulties: Beginner, Easy, Medium and Hard. The implemented techniques are: Naked Single, Hidden Single, Candidate Lines (Pointing Pairs), Multiple Lines, Naked Pairs, Hidden Pairs and Naked Triples.
All the techniques have almost the same searching patterns in terms of direction within the grid, from the top left corner towards the bottom right corner of the grid, row by row, column by column. Though some of the techniques can still be optimized, regarding the searching pattern in the grid and the way they check for applicability, such using group theory algorithms, unions by set and rank, etc.
For this sudoku generator algorithm, I focused more on lowering time complexity at the cost of increasing the space complexity, for the reason of making the generation process quicker at least, and for further development for an android platform build.
The current build is a hi-fi prototype and its development is to be continued in the near future. The higher the difficulty the longer it takes to generate a sudoku puzzle. I got many solution ideas about this but for now it is not as important, as making the generator work with all intended techniques.
For this sudoku generator algorithm, I focused more on lowering time complexity at the cost of increasing the space complexity, for the reason of making the generation process quicker at least, and for further development for an android platform build.
The current build is a hi-fi prototype and its development is to be continued in the near future. The higher the difficulty the longer it takes to generate a sudoku puzzle. I got many solution ideas about this but for now it is not as important, as making the generator work with all intended techniques.
