Sudoku Solver

1. Problem

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character ‘.’. You may assume that there will be only one unique solution. Below is a Sudoku puzzle and a solution to it.



Sudoku solution

2. Idea

Previously, we have worked on validating whether a Sudoku puzzle is valid (LeetCode – Valid Sudoku). This problem goes further to ask for a solution. If you have heard about N Queens Puzzle (a famous one is eight queens puzzle), you may find similarities between them, and adopt a similar solution from it to this one. Basically, we can make a DFS-like exploration, put in a possible character at each empty cell. Once we reach a cell where no character can fit without violating the Sudoku rules, we backtrack to its preceding cell and try next possible character. A solution is found after we have filled the board and encounter no conflict. The one-pass algorithm for validating a puzzle as in LeetCode – Valid Sudoku can be used as a subroutine. But since we work on one cell at a time, applying and updating the checkers is incremental during the exploration process.

3. Implementation

4. Wrap-up

The above backtracking solution is in essence a trial-and-error algorithm. But since it can prune the brunches that have been found unfeasible in the midway, it is still much better than listing and verifying all possible candidates.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s