Coloring a Sudoku graph with Neo4j

I was happy to see that a recent release of the Neo4j graph algorithms contains the K-1 Coloring algorithm. This algorithm tries to assign colors to the nodes of a graph in such a way that adjacent nodes are different colors.

One of my favorite puzzles, Sudoku, can be represented as a graph coloring problem. If you’re not familiar with the puzzle, you are given a 9x9 grid with some digits filled in. You complete the puzzle by filling in the blank squares so that each row, and column, as well as the 3x3 blocks indicated by the heavy lines, contain each digit from 1 to 9.

You can think of a Sudoku grid as a graph with nodes representing the squares. Edges connect each node with the other nodes on the same row, column, and block. David Eppstein created this diagram of a 4x4 Sudoku graph.

The version of the K-1 Coloring algorithm that was just released doesn’t support adding colors to a partially colored graph. That means it’s not ideal for solving Sudoku puzzles. However, we can still try it out on a blank Sudoku graph to get familiar with the algorithm. In my next blog post, I’ll demonstrate a way to write a Neo4j-based Sudoku solver.

To follow along with my code at home, you will need a Neo4j database with a recent release of graph algorithms installed. At the time of this blog post, the latest sandbox instances didn’t include the new coloring algorithm. You will want to download the latest Neo4j desktop version to run this code, selecting/upgrading to the 3.5.14 version of the database.

First, create nodes for our grid. We’ll use a parameter to describe the size of our parameter grid. I’ll demonstrate a 9x9 grid, and you can try other possibilities like 4x4, 16x16.

:params {gridSize:9}

Now we execute a query to create all the cell nodes with their row, column, and block properties.

WITH toInteger(sqrt($gridSize)) AS blockSize
UNWIND RANGE(1,$gridSize) AS row
UNWIND RANGE(1,$gridSize) AS column
CREATE (m:Cell {row:row, column:column})
SET m.block = blockSize * ((m.row-1)/blockSize) + (m.column-1)/blockSize + 1

Let’s add edges between adjacent cells.

MATCH (c1:Cell), (c2:Cell)
WHERE (c1.row = c2.row OR c1.column = c2.column OR c1.block = c2.block)
AND id(c1) < id(c2)
MERGE (c1)-[:IS_ADJACENT_TO]->(c2)

Now we can run the coloring algorithm and assign a “number” property to each of the nodes.

CALL algo.beta.k1coloring("Cell", "IS_ADJACENT_TO", {write:true, writeProperty:"number", iterations:15}) YIELD didConverge, ranIterations, colorCount, computeMillis, nodes
RETURN *
╒════════════╤═══════════════╤═════════════╤═══════╤═══════════════╕
│"colorCount"│"computeMillis"│"didConverge"│"nodes"│"ranIterations"│
╞════════════╪═══════════════╪═════════════╪═══════╪═══════════════╡
│12          │2              │true         │81     │13             │
└────────────┴───────────────┴─────────────┴───────┴───────────────┘

The documentation explains that since graph coloring is an NP-complete problem, the algorithm finds a good coloring, but maybe not the best possible.

It is neither guaranteed that the result is an optimal solution, using as few colors as theoretically possible, nor does it always produce a correct result where no two neighboring nodes have different colors.

The algorithm used 12 colors, when we know that 9 is possible. It’s still not a bad approximation in 2 milliseconds! How did it do at avoiding adjacent cells of the same color?

MATCH (c1:Cell)-[:IS_ADJACENT_TO]->(c2:Cell)
RETURN 
SUM(case when c1.number = c2.number then 1 else 0 end) AS conflicts,
COUNT(*) AS edges,
SUM(case when c1.number = c2.number then 1.0 else 0 end)/count(*) AS pctConflicts
╒═══════════╤═══════╤═════════════════════╕
│"conflicts"│"edges"│"pctConflicts"       │
╞═══════════╪═══════╪═════════════════════╡
│4          │810    │0.0049382716049382715│
└───────────┴───────┴─────────────────────┘

The algorithm avoided conflicts on 99.5% of the edges.

I tried the algorithm on a 4x4 board, and it avoided conflicts on 100% of the edges using 5 colors. On a 25x25 board, It avoided conflicts on 99% of the edges using 34 colors.

I hope playing with Sudoku graphs gives you a fun taste of the new K1 Coloring algorithm. Check out my next post to see a Sudoku solving algorithm built in Neo4j.