SudokuSolver

Nikolas Ioannou

April, 2019




Description

SudokuSolver is a Swift playground that enables users to solve a Sudoku board by taking a photo of it.


Data collection

Building the dataset was a project on its own. I started at my local bookstore, where I purchased three Sudoku books. I took a photo of each Sudoku board and passed it into a custom script that splits the image of the board into its 81 cells. Now, with over 300 images of boards, and 25,000 images of cells, I had to classify each of the images of cells into ten categories, digits one-nine and an empty cell.


Machine learning

I used Tensorflow with Keras and transfer learning on InceptionV3 to develop SudokuSolver's image classification algorithm. After training, I received 93% validation accuracy.


Board solving algorithm

Finally, I brainstormed ideas for a Sudoku solver, the most challenging step of the entire project. Not only did I have to create an algorithm that would provide the correct solution to any valid Sudoku board, but the process had to be very fast. My starting point was that of a “brute-force” solver, which took over ten seconds to compute an answer. After several hours of brainstorming and implementation testing, I landed on a recursive solver. The solver works by finding an empty cell the Sudoku board, checking which number values are valid, and creating a new copy of this board with that valid value filled in at the empty cell. This process repeats and backtracks until either a solution is given or the board is unsolvable - this process occurs within 100 milliseconds!


Awards

Layers: SudokuSolver won a scholarship to the Layers conference in 2019 in San Jose.