Sudoku is a commonly known logic puzzle game, and had been one of my favorite puzzle games.
Having the experience for creating the simple Tic-Tac-Toe AI, I started to take on this challenge for creating an AI that can solve Sudoku.
Figure 1. The initial and complete board state of an expert-level Sudoku game.
I had written this AI program when I was in junior high school using Visual Basic 6.0. Having no prior knowledge for algorithms and data structures (which I learned in senior high school), I came up with a rough version of the backtracking algorithm myself, and implemented it on the AI. Here, the backtracking algorithm is a kind of depth-first search (DFS), and is guaranteed for finding a valid solution. Constraint programming is also integrated with the backtracking algorithm, since it is a very intuitive way for solving the puzzle.
Here is a clip demonstrating the Sudoku Solver program solving a hard-level Sudoku in around 5 seconds:
Here is another one that solved an expert-level Sudoku in around 44 seconds:
[Download program for the Sudoku Solver]
[Source code for the Sudoku Solver (Visual Basic 6.0 form file)]