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

 

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.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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