» next  » last 

Jump to:

Solving Sudoku Puzzles using Depth First Search

1. Introduction

In this article I hope to show how we can develop a solution to just about any problem using one of the most simple and generic problem solving techniques: a simple depth first search. I'm going to use Sudoku puzzles as an example.

Though I can guarantee that it will solve any Sudoku puzzle, I'm not trying to say that the technique I'm using is in any way the fastest or the most impressive. In fact, I can start this article by categorically stating that this is not the best way to solve sudoku. What I can say about the depth first method, however, is that it could be one of the most simple and generic ways to solve sudoku puzzles!

This page continues with a quick introduction to Sudoku puzzles and how people tend to solve them. The next page talks about depth-first search and how I applied it in my Suduko solving application. Finally, the third page has some concluding discussion on why this isn't the optimum method and what we could do to improve it, along with code downloads.

2. Sudoku Puzzles

Sudoku has recently become a very popular puzzle and has started to appear in just about every national newspaper alongside the crossword. The basic rules of the game are very simple, we must fill every square in a 9x9 grid with one of the digits 1-9. We are constrained by rules which state that no two of the same number can appear on the same row or column, or within the same 3x3 box (see figure).

Generally the puzzles will have enough numbers filled in to get us started. Those numbers are shown in Figure 1 in grey boxes. Our job is to fill in the white boxes.

A simple Sudoku puzzle
Figure 1: A simple Sudoku puzzle

Figure 2 shows a possible first step. The bottom row has two numbers missing, 8 and 1. The 1 must go in the left hand box, since there is already a 1 in the bottom right 3x3 square. Therefore, the 8 must go on the right.

First steps to solving the puzzle
Figure 2: First steps to solving the puzzle

Figure 3 shows how we can take another step towards a solution. We must have a 2 in each of the 3x3 squares. Since we have a few 2's on the board already we can easily see where the 2 must go in the middle-left 3x3 square.

Second step to solving the puzzle
Figure 3: Second step to solving the puzzle

We can continue in this way until all the squares have been filled. Our answers will help us to make more decisions as we go along.

The next page gives details of a very simple sudoku solver.

» next  » last 

Jump to: