Solving Sudoku with Graph Theory

https://rakhman.info/blog/solving-sudoku-with-graph-theory/

by cypressious • 6 years ago

52 3 6 years ago

nwallin2• 6 years ago

I think I'm misreading the article. If I'm reading it right, the author is on the right track but didn't make it all the way to the station.

The right way to do this is to make this a bipartite maximally connected directed graph. Then calculate the strongly connected components of the graph. Then remove all the edges that bridge different strongly connected components. All of this is linear in terms of the number of edges.

cypressious• 6 years ago

OP here: Just to clarify, I wasn't aiming for performance/complexity, only for making the algorithm easier to visualize.

However, I'm intrigued. Are you saying that the strongly connected components are the tuples and if they have edges to other components, they correspond to possible eliminations?

nwallin2• 6 years ago

Let me start over. My first post was a little terse.

Construct a directed bipartite graph. An edge between a number node and a square node indicates that it may be possible for that number to go in that square. The lack of an edge means that the possibility of that number going into that square has been completely excluded. (there are 9 rows, 9 columns, 9 groups in a sudoku, so you'll need 27 such graphs)

Initially, all edges will go from numbers to squares. Switch the directions of 9 edges so that each square has one out edge that points to a number, and all numbers have only one edge pointing into it. (aka, make a maximally connected graph) There will typically be many valid ways to do this; narrowing it down to just one correct way is to solve that row/column/group, and that's what our goal is.

An edge is valid if and only if any of the following are true:

1. The edge is part of the arbitrarily chosen maximally connected set.

2. The edge connects two vertices which are part of the same strongly connected component.

3. (this does not apply to sudoku) The edge is part of an even alternating path starting from a free number/color. This doesn't apply to sudoku. If you had a sudoku variant where you had the numbers 1-27, but still only 9 squares, by the pigeon hole principle some of your numbers would be free- there's no square which is assigned to it. If you can construct a path that starts at a number that hasn't had a square assigned to it, and ends at another number, it will be a part of at least one maximally connected set.

(I forgot what that theorem is called)

So now, you number each vertex by its strongly connected component. Iterate over all edges starting from each number, and eliminate the edge if it goes from one strongly connected component to a different strongly connected component.

Does that make sense?

Solving Sudoku with Graph Theory

Related Stories