Enter your Logical Genetics login details here or **Register Now!**

## LoginEnter your Logical Genetics login details here or ## Recent Activity on the ForumsWiPi by ballista (Friday 20:11) WiPi by genious (Monday 15:03) WiPi by genious (Friday 05:58) Mono C# on the Raspberry Pi by genious (Monday 10:59) Google Maps API by genious (Monday 06:51) Interesting Linux Webcam Project by genious (Saturday 16:47) Mono C# on the Raspberry Pi by genious (Saturday 15:55) Mono C# on the Raspberry Pi by genious (Monday 06:58) ## Latest Photos
## Mobile Photo...
## Online Articles
- Hacked
- Evolution in a 3D Fitness Landscape
- Titanic Survivor Prediction
- Solving Sudoku Puzzles using Depth First Search
- Architecture of Artificial Neural Networks
- Evolutionary Algorithms
- Emergent Behaviour and Artificial Life
- Artificial Immune Systems and Negative Selection
- Return to the Animal Kingdom
- Neural Networks in Nature
## Search |
## Solving Sudoku Puzzles using Depth First Search## 1. IntroductionIn 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 PuzzlesSudoku 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.
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.
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.
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. |