How to Solve Sudoku with Depth-first Search Algorithm (DFS) in Python

Sudoku first appeared in Japan in 1984 and since then has become one of the most popular mind games in newspapers and magazines. Today, we will try to solve a Sudoku puzzle using a Search Algorithm called Depth-first Search.

First, let’s talk about how it is played. A Sudoku board consists of a 9x9 grid of squares, subdivided into 3x3 squares, therefore, the total number of slots is 81. At the end of the game, each slot will contain exactly one number.

In the beginning, some slots have numbers, and the player tries to complete the other slots using the following rules: (1) each slot must contain a single number between 1 and 9, (2) each column can only contain numbers from 1 to 9 once, (3) each row must contain numbers from 1 to 9 once, and (4) each 3x3 square must contain numbers from 1 to 9 once.

Now that we know the rules of the game, let’s talk about the search algorithm we will use to solve this puzzle. The Depth-first Search is a “blind” search algorithm that can be used to find a solution to problems that can be modeled as graphs.

It’s called “blind” because this algorithm doesn’t care about the cost between vertices on the graph. The algorithm starts from a root node and explores as far as possible along each branch before backtracking. if the algorithm finds a solution then it returns the solution and stops the search. The pseudocode of the DFS algorithm is the following:

procedure dfs_algorithm(graph, initial_vertex):
  create a stack called frontier
  create a list called visited_vertex
  frontier.push(initial_vertex)

while True:
  if frontier is empty then
    print("No Solution Found")
    break
  
  selected_node = frontier.pop()
  visited_vertex.append(selected_node)
  
  // Check if the selected_node is the solution
  if selected_node is the solution then 
    print(selected_node)
    break
  
  // Extend the node
  new_nodes = extend the selected_node

  // Add the extended nodes in the frontier
  for all nodes from new_nodes do
    if node not in visited_vertex and node not in frontier then
      frontier.push(node)

In our example, the root (initial_vertex) is the initial state of Sudoku. To extend a node, we find the first empty slot and put a valid number. A number is valid when satisfies all the rules that we discussed above.

A node is a solution when all slots have a valid number. Last but not least, to reduce the search space, we check if a new node has been visited in the past or the node already exists in the frontier.

Now, it’s time to implement the Depth-first Search Algorithm. The first step is to read the Sudoku from the text file. The text file contains the initial state of the game, including the initial numbers and the empty slots represented by the zeros, and has the following structure.

8 5 0 9 0 0 7 2 0
9 2 6 1 7 0 3 0 0
0 0 3 6 5 2 0 0 0
5 6 8 0 0 0 0 1 3
1 9 7 0 0 6 0 0 4
3 0 0 5 0 9 6 0 7
0 0 0 4 0 7 0 0 0
0 0 4 8 0 0 0 0 0
6 0 0 2 3 1 0 0 0

Now let’s create the class Node. To use the same structure of the algorithm for other problems, we have to create an interface. To do this we define abstract methods that users must implement appropriately according to the problem to use the algorithm.

After that, it’s time to create the class that represents the main algorithm. This class will contain all the necessary methods to add a new node to the frontier, remove a node from the frontier, check if the frontier is empty and finally search for a solution in the search space.

After that, we create a class that represents Sudoku. This class implements the interface Node, implementing all the necessary methods.

Finally, we create the objects and execute the program. In a few seconds, we will have the response from the algorithm which is the solution to the Sudoku puzzle.

Conclusion

In this article, we saw how to use the Artificial Intelligence “blind” Depth-first Search Algorithm to find a solution to a very popular mind game like Sudoku.

Although there are plenty of other “more clever” algorithms, we can use the same algorithm for lots of other problems and games.

You can see the entire source code and some starter files from the link below. Thank you for reading.

If you like reading my articles follow me on LinkedIn and Twitter. Also, you can sign up to become a Medium member. As a member, you have unlimited access to thousands of articles. The membership costs 5$ per month. You can use the following link to become a medium member.

More content at plainenglish.io