Chromatic Polynomials 06 – Sudoku

The news article that first introduced me to Chromatic Polynomials touted Timme et al.’s work as applicable to Sudoku. The article didn’t explain how to solve Sudoko with CPs, and Timme et al.’s paper didn’t mention it at all. I guess some journalist decided that Sudoku made for a flashier headline than “Counting complex disordered states”.

But the seed was planted, and I wanted to work out how it could be done. The CP expression for Sudoku is straightforward, but very, very cumbersome:

Sudoku Approach 1

We first define a vertex for each spot in a Sudoku puzzle. Each vertex will have a value, 1 - 9, for the number placed in that position:

We need to specify that each vertex in a 3x3 block must have a unique value. For example, in the first block, we require that σ_o is different from σ₁, σ₂, σ₉, σ₁₀, σ₁₁, σ₁₈, σ₁₉, and σ₂₀:

That gives us these eight terms:

We need another 28 terms to cover the rest of the comparisons in the first block, and another 36 * 8 = 288 terms for the other eight 3x3 blocks.

All 324 terms can be encoded like this:

To specify that no two vertices in the same row can be set to the same number, we need to compare each vertex to the other six vertices that are in the same row but not in the same block. For σ_o we need:

To do the same for all vertices, we need 243 terms:

We need another 243 terms to represent the condition that each number can only occur once in column:

Altogether, this defines 810 terms for Sudoku. Summing over all 81 vertices from 1 to 9 would yield the number of possible Sudoku puzzles. Unfortunately, this is more than my CP symbolic math engine can handle – I would need to make some significant memory and speed optimizations.

But in writing this formula, I learned there can be more than one way to specify logical constraints with CPs. Here is an alternate approach:

Sudoku Approach 2

Let's look at the ways to place nine digits in each block. We'll use one vertex to represent each digit's row and one vertex to represent each digit's column. Let σ_r:0 be the row position (0, 1, or 2) of the 1 digit in the top left block. Let σ_c:0 be the column position (0, 1, or 2) of the 1 digit in the top left block. Define similar vertices for digits 2-9:

Top Left Block

Position of the 1 digit: σ_r:0 and σ_c:0

Position of the 2 digit: σ_r:1 and σ_c:1

Position of the 3 digit: σ_r:2 and σ_c:2

Position of the 4 digit: σ_r:3 and σ_c:3

Position of the 5 digit: σ_r:4 and σ_c:4

Position of the 6 digit: σ_r:5 and σ_c:5

Position of the 7 digit: σ_r:6 and σ_c:6

Position of the 8 digit: σ_r:7 and σ_c:7

Position of the 9 digit: σ_r:8 and σ_c:8

To specify that the 1 digit and the 2 digit can't occupy the same position, we write:

To require that the 1 digit's position doesn't match any of the other digits, we need 8 terms:

We'll need another 28 terms to ensure that every digit in the top left block occupies a unique position. We'll need a total of 162 vertices for the entire puzzle and a total of 324 terms to specify that every digit occupies a unique position. They can all be specified with this:

Now we need to consider that there is a 1 digit in each block:

σr:0, σc:0 = row and column of the 1 digit in this block.	σr:9, σc:9 = row and column of the 1 digit in this block.	σr:18, σc:18 = row and column of the 1 digit in this block.
σr:27, σc:27 = row and column of the 1 digit in this block.	σr:36, σc:36 = row and column of the 1 digit in this block.	σr:45, σc:45 = row and column of the 1 digit in this block.
σr:54, σc:54 = row and column of the 1 digit in this block.	σr:63, σc:63 = row and column of the 1 digit in this block.	σr:72, σc:72 = row and column of the 1 digit in this block.

To specify that every 1 digit must be in a unique row, we can write these 9 terms:

We'll need another 72 terms to specify the same for digits 2 through 9. In all, we write 81 terms to ensure that no two matching digits appear in the same row:

We write another 81 terms to specify that no two matching digits appear in the same column:

This approach produces the same number of block terms, 324. The number of row terms is reduced from 243 to 81. The number of column terms is similarly reduced. The total number of terms is reduced from 810 to 486 – 40% fewer terms!

This shows us that there can be efficient and inefficient ways to specify logical constraints in CPs, and that we should consider multiple approaches to each problem.

Representing a Specific Sudoku Puzzle

To encode a specific Sudoku puzzle in CPs, all we have to do is take one of the expressions above and, in every spot where there is a hint given (a number given in a specific position), replace a vertex with a constant.

For example, if we are using the first approach and if row 1 column 2 (σ₁) contains a 7, we would replace every instance of σ₁ with {7}. We would replace (1-δ_σ0σ1) with (1-δ_σ0{7}), and so on.

Summing over all remaining vertices should yield the number of solutions to the Sudoku puzzle. If the answer is 1, then the Sudoku puzzle is a well-formed puzzle. If the answer is 0, then the puzzle is impossible to solve. If the answer is greater than 1, then there is more than 1 solution.

Solving a Sudoku Puzzle

We can use the same trick to solve a Sudoku puzzle. Take a guess that σ₀ is 1. Replace σ₀ with 1 and compute the number of solutions. If the number of solutions is still 1, then the guess is correct and σ₀= 1 in the solution. If the guess produces 0 solutions, then the guess is wrong - σ₀ is not 1. We continue to guess 2, 3, 4, etc. until we find the right value for σ₀. We then move on to σ₁, and so on.

This means we can not just use CPs to count the number of solutions - we can use them to find the solutions themselves.

Previous Article:

www.solutionslookingforproblems.com

Chromatic Polynomials 05 – Counting Quoridor Fence Arrangements

In this article, I showed how to calculate the number of ways that walls can be placed in the game of Quoridor (please see that article for a description of the game). Now I will show how to do it with CPs.We will define one vertex for each intersection where a wall can be placed, σ0 through σ63. The first row contains σ0 through σ7, from left to right. The second row contains σ8 through σ15, and so on:Named ConstantsEach vertex can take one of three values – no fence (or an empty intersection),

Next Article:

Chromatic Polynomials 07 of 16 - Coming Soon