Leetcode 37: Sudoku Solver

This was an interesting problem that highlights that sometimes it is better to write an algorithm for a computer to execute in a different way to how we would solve the problem with a human mind. So I first attempted to code this in a way in which I would manually solve a sudoku puzzle by walking through each number and analysing the impact of rows and columns on boxes. This resulted in complicated code and did not work on hard sudoku puzzles.

My second attempt at a solution used backtracking. The result was simpler code and the ability to solve the hardest sudoku puzzles. The algorithm stops at every space sequentially and tries every number until it finds a number that results in a valid board. If it gets to a square where no number will work then it backtracks to the previous square and continues its search through the numbers. Here is a nice visualisation of backtracking from wikipedia:

Here is my c++ source code for the solution:

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *