# How to implement graph search to solve Sudoku puzzle

My teacher pointed out to us during lectures that we could use Graph Search to help us solve Sudoku puzzles which has left me puzzled .

I dont see how this is possible as Graph Search is mostly about getting from Node A to Node B. He mentioned about how its a directed graph where the nodes correspond to partially completed puzzle

What is the general idea behind using Graph Search to solve Sudoku Puzzle

A graph is defined abstractly as a set of vertices together with a set of edges connecting those vertices. You have to give the vertices/edges meaning to make sense of the problem. For Sudoku, a vertex is a board configuration and an edge from configuration $a$ to configuration $b$ exists if $b$ is obtained from $a$ by inserting a number in an empty cell of $a$. There are $(9^2)^9$ possible configurations; searching this graph for a solution will take a lot of time but you will find one eventually. Many of the configurations are invalid Sudoku grids so you can eliminate lots of them.

A typical Sudoku solver would search an implicit graph: the solver is not given a graph as input but it is given a procedure to generate candidate configurations given some configuration. One such procedure may be described as:

generate_candidates(config) {
candidates = [] is a list of configs
for every empty cell (call it C) in config
for every number in [1..9]
C = number
if config is a valid grid
add copy of config to candidates
}

In the implicit graph, the edges are the ones that look like 'config $\to$ candidate' where config is the input to generate_candidates and candidate is a configuration generated by generate_candidates. Of course you have to generate new candidates from the ones just generated; you keep growing that list of candidates until no more can be generated or you've found a solution.

Let node A be start state of sudoku. Suppose, you are in some state $s$ of sudoku, now you can put a number in some square without violating the conditions. At this stage, you don't know if putting such number will yield the final solution or not. You just check that it doesn't violate any conditions now. Let the state of sudoku obtained after putting the number be $t$. Put $t$ as a node and put an edge from $s$ to $t$. Continue this process starting from A. Your aim is to reach a state in which every square is filled. Look for all such nodes that you have obtained in this graph. Let a set of them be called $S$. In this graph, if A has a solution, then there is a path from A to some element in $S$. This is the path finding problem but with a modification that destination vertex is not a single node, but rather a set of nodes.

One graph searching technique you can use for solving a Sudoku puzzle is backtracking. Suppose you are given a partially filled Sudoku puzzle. Choose some empty cell, and assign 1 to it. Check if there are any conflicts. If so, erase that 1 you just put in, and put in 2. Keep repeating this until you find a number that causes no conflicts. Now repeat this procedure until the puzzle is solved. It is not hard to see you will eventually find a solution using this strategy, because it will in the worst case try all possible ways filling the puzzle.

And when you think of it, the Sudoku puzzle actually is about getting from node $A$ to node $B$. In this setting, your node A is the partially filled puzzle given to you initially. Node $B$ is a completely filled puzzle with no conflicts. Choosing an empty cell and assign a value to it (corresponding to the situation described in the first paragraph), means you are moving from $A$ to $A_2$, where $A_2$ is a partially solved puzzle. Moving along from here will hopefully make you eventually find $B$, which is a goal state. In this way, you can indeed see the puzzle solving process as a directed graph.

You can see backtracking in action here.

One way to solve Sudokus using graph theory:

Construct a graph of 81 (9x9) vertices. These are the squares of the puzzle. Now, for each vertex in the graph; add an edge from all vertices in the same row, the same column and in the same box. Use the "colors" {1..9} and color vertices already "filled in" in the puzzle to solve. The problem is now solveable using graph coloring algorithms.

https://en.wikipedia.org/wiki/Graph_coloring#Greedy_coloring