When solving Sudoku games of higher difficulty levels, I find that I am unable to accurately solve the puzzle without guessing entries at least twice. My main motivation for this project is to learn whether a guess-free approach can be employed in Sudoku, as well as gain image-processing experience via the use of a Pixy camera. Additionally, I hope to gain an understanding of current algorithms used to solve Sudoku puzzles and eventually develop a more efficient method of solving Sudoku puzzles as a pastime, without the use of computers and processors.
What it does
The Sudoku hint master either allows a user to supply a Sudoku game or it generates one for the user. Once a Sudoku board is generated, it determines whether the game is solvable or unsolvable, solving the Sudoku if it is. For solvable games, the user is allowed to check their entries for any cell without penalty, but can only receive a correct solution for a specific cell up to 5 times. The user can restart or exit the master when they want.
How I built it
The main components or stages in the Sudoku Hint Master were the board input or generation stage, the solution stage, and finally, the hint- or cell-solution- accessing stage. For the input stage, the membrane switch module was used to fill a “sudo” array with all the elements in an initial Sudoku game, or it was used to input the number of rows and columns desired for an auto-generated game. Once a Sudoku was entered, it was solved using the backtracking method enhanced by first finding the markup of each empty cell (i.e. a cell containing the number “0”). After marking and in the process of backtracking, the solvability of the array was determined and if the game was solvable, the user was allowed access to the solutions of some entries.
A markup of an empty cell in a Sudoku game is a list of elements in the range 1 to 9, in this case, that can be entered into that cell without violating the rules of the game.
The backtrack method involves guessing an entry for an unfilled cell, checking to make sure that the entry does not violate the rules of Sudoku -- only one instance of the numbers from 1-9 in each row, column, and 3x3 subregion of a 9x9 matrix --, backtracking to previous guesses if no entry for the current empty cell being worked on passes the rules of the game.
Challenges I ran into
The Pixy camera failed to detect the images and objects such as marker dot labels that I used to represent numbers, perhaps because they were too small -- making them bigger would mean that a user would need to move the pixy around to scan a board, however, to fill in the software version of the Sudoku array, a common reference point for each "numeral" is required.
Accomplishments that I'm proud of
- Getting the Hint Master to work
- Learning new Sudoku algorithms
- Honing my debugging skills
What I learned
I started this project with the goal of determining whether it is possible to solve a Sudoku without guessing an entry. Intriguingly, I found that guessing is an integral part of effectively solving Sudoku games. I learnt the importance of starting coding only after drafting a pseudo code, of proper debugging skills, and of thinking through a number of outlier outcomes and including checks for them.
What's next for the Sudoku Hint Master (SHM)
Moving forward, I will integrate a Raspberry Pi camera into the SHM and include a scan mode feature that allows users to draw Sudoku games in line with a predetermined color scheme and fill the software array by taking images of the drawn game.