Solving a Sudoku as a Coloring Problem using Qiskit and QAOA

11 min readSep 28, 2023

Dive into the innovative realm where Sudoku puzzles meet quantum computing. Discover how Qiskit and QAOA can transform a classic game into a colorful quantum challenge.

Motivation:

Sudoku, a logic-based number-placement puzzle, has entertained and challenged individuals for decades. Its timeless simplicity paired with intricate logical sequences have made it a favorite amongst many. However, beyond being a mere puzzle, Sudoku has implications in computer science, particularly when treated as a coloring problem. This article dives into how we can leverage the power of quantum computers, using Qiskit and the Quantum Approximate Optimization Algorithm (QAOA), to solve a Sudoku puzzle.

The Problem: Sudoku

A Sudoku puzzle is represented as a square grid divided into smaller squares called cells. The challenge is to fill each cell with a number, obeying specific rules to ensure a unique solution. In a standard 3x3 Sudoku, the grid consists of 9x9 cells, divided into 9 blocks of 3x3 cells. The rules are:

Every row must have numbers 1 to 9, with no repetition.
Every column must also have numbers 1 to 9, without repetition.
Each of the 9 blocks must have numbers 1 to 9, with no repetition.

For our exploration, we will use a smaller 2x2 Sudoku, which is a 4x4 grid with rules analogous to the standard 3x3 version.

Sudoku as a Coloring Problem:

At its core, Sudoku can be seen as a graph coloring problem. Here, each cell represents a node, and nodes are connected by edges if they belong to the same row, column, or block. The challenge then is to color each node such that no two adjacent nodes (nodes connected by an edge) have the same color. In the Sudoku context, colors are numbers.

Solved sudoku alongside its graph representation with colors.

Note: In the Sudoku graph image, the nodes are connected to all the nodes in their row and column. That is, the first node in position 0 is connected with the nodes in positions 1, 2, and 3. It is also connected with the nodes in its cell, at positions 1, 4, and 5, as well as with the nodes in its column, at positions 4, 8, and 12.

QUBO: Quadratic Unconstrained Binary Optimization:

To translate our Sudoku problem into a language quantum computers can understand, we use QUBO. A QUBO problem aims to find a vector of binary variables that minimizes a quadratic function. For Sudoku, our binary variables represent whether a particular number (color) is present in a given cell or not.

Sudoku Constraints to QUBO:

The representation of QUBO (Quadratic Unconstrained Binary Optimization) for Sudoku constraints can be quite intricate, but I’ll try to detail it in simpler terms.

The QUBO representation for Sudoku constraints in a 4x4 grid involves defining binary variables Xijk where:

i represents the row index (1–4).
j represents the column index (1–4).
k represents the number (1–4).

This encoding means that if a cell at the ith row and jth column contains the number k, then Xijk would be 1, otherwise 0.

Let’s break down the QUBO formulation for a 4x4 Sudoku puzzle.

Cell Constraint: This ensures that each cell contains exactly one number.

2. Row Constraint:

3. Column Constraint:

4. Subgrid Constraint: For a 4x4 Sudoku, there are four 2x2 subgrids. This ensures that no number repeats within any subgrid.

Here, a and b iterate over the subgrids, and δi and δj iterate over the cells within a subgrid.

The complete QUBO Hamiltonian for the 4x4 Sudoku puzzle is:

This Hamiltonian will be minimized when all Sudoku constraints are satisfied.

Quantum Approximate Optimization Algorithm (QAOA):

The Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm designed to find approximate solutions to combinatorial optimization problems. The central idea behind QAOA is to harness the power of quantum interference to explore the vast solution space of optimization problems efficiently.

How it Works:

Encoding the Problem: The optimization problem is encoded as a QUBO (Quadratic Unconstrained Binary Optimization) or Ising model, which can then be represented by a Hamiltonian, H. The Hamiltonian is a crucial concept in quantum mechanics and, in this context, defines the energy landscape of the problem.
Quantum Evolution: Starting from an easily prepared quantum state, the quantum system is evolved under the influence of two Hamiltonians: the problem Hamiltonian H and a mixer Hamiltonian. These evolutions are parameterized by angles, which are varied classically to find the optimal quantum state that represents the solution.
Sampling and Measurement: After the quantum evolution, the quantum state is measured to obtain a sample solution. Repeated measurements provide different solutions, and the best one can be chosen as the output.

Implementations: Many quantum software platforms, such as Qiskit, provide tools and libraries to implement the QAOA and test it on quantum hardware.

COBYLA Optimizer:

COBYLA (Constrained Optimization BY Linear Approximations) is an optimizer that doesn’t require gradient information and is thus well-suited for noisy quantum computations, making it a popular choice in quantum computing.

THE Solution:

Once we grasp the fundamental concepts and methodologies outlined above, we can then apply them to a simplified problem. The primary reason for this simplification is to sidestep the limitations posed by dimensionality constraints when executing the code.

To visually represent our problem as a graph, the code provided below illustrates how a smaller graph can be perceived and utilized in a manner analogous to our main problem.

def draw_graph(n, e):
    G = nx.Graph()
    G.add_nodes_from([i for i in range(1, n+1)])
    G.add_edges_from(e)
    nx.draw(G, with_labels=True)
    return G

n = 5
e = [(1,2), (1,5), (2,3), (2,4), (2,5), (3,4), (4,5)]
G = draw_graph(n,e)

Constructing the QUBO Model for Graph Coloring

To transform the graph coloring problem into a Quadratic Unconstrained Binary Optimization (QUBO) format, we need a matrix representation. This matrix, denoted as Q, will act as a cost function where the solution attempts to minimize the “penalties” or conflicts between nodes with the same colors.


num_nodes = G.number_of_nodes()
num_color = 3
P = 4
Q = np.eye(num_nodes * num_color)
for i in range(1, num_nodes +1):
    l = num_color * i + 1
    for j in range(l-num_color,l):
        for k in range(l-num_color, l):
            if k==j:
                Q[j-1][k-1] = -P
            else:
                Q[j-1][k-1] = P



for i, j in G.edges:
    for k in range(1, num_color+1):
        # (node -1) * num_color + k
        m = (i-1) * num_color + k
        o = (j-1) * num_color + k
        Q[m-1][o-1] = P/2
        Q[o-1][m-1] = P/2        

print(Q)

The matrix Q produced:

[[-4.  4.  4.  2.  0.  0.  0.  0.  0.  0.  0.  0.  2.  0.  0.]
 [ 4. -4.  4.  0.  2.  0.  0.  0.  0.  0.  0.  0.  0.  2.  0.]
 [ 4.  4. -4.  0.  0.  2.  0.  0.  0.  0.  0.  0.  0.  0.  2.]
 [ 2.  0.  0. -4.  4.  4.  2.  0.  0.  2.  0.  0.  2.  0.  0.]
 [ 0.  2.  0.  4. -4.  4.  0.  2.  0.  0.  2.  0.  0.  2.  0.]
 [ 0.  0.  2.  4.  4. -4.  0.  0.  2.  0.  0.  2.  0.  0.  2.]
 [ 0.  0.  0.  2.  0.  0. -4.  4.  4.  2.  0.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  2.  0.  4. -4.  4.  0.  2.  0.  0.  0.  0.]
 [ 0.  0.  0.  0.  0.  2.  4.  4. -4.  0.  0.  2.  0.  0.  0.]
 [ 0.  0.  0.  2.  0.  0.  2.  0.  0. -4.  4.  4.  2.  0.  0.]
 [ 0.  0.  0.  0.  2.  0.  0.  2.  0.  4. -4.  4.  0.  2.  0.]
 [ 0.  0.  0.  0.  0.  2.  0.  0.  2.  4.  4. -4.  0.  0.  2.]
 [ 2.  0.  0.  2.  0.  0.  0.  0.  0.  2.  0.  0. -4.  4.  4.]
 [ 0.  2.  0.  0.  2.  0.  0.  0.  0.  0.  2.  0.  4. -4.  4.]
 [ 0.  0.  2.  0.  0.  2.  0.  0.  0.  0.  0.  2.  4.  4. -4.]]

In this matrix, each node in the graph has its own set of binary variables representing different colors. The goal is to minimize the value produced by this matrix multiplied by a vector of our binary variables.

Modeling with DOcplex

DOcplex is a native Python modeling library for optimization. Here, we model our QUBO problem using DOcplex and then convert it to a quantum-friendly format:

from docplex.mp.model import Model
from qiskit_optimization.translators import from_docplex_mp

mdl = Model(name ="GC")
x = [mdl.binary_var('x%s' % i) for i in range (len(Q))]
objective = mdl.sum([x[i]* Q[i,j] * x[j] for i in range(len(Q)) for j in range(len(Q))])
mdl.minimize(objective)
qp = from_docplex_mp(mdl)

print(qp.prettyprint())

Problem name: GC

Minimize
  -4*x0^2 + 8*x0*x1 + 4*x0*x12 + 8*x0*x2 + 4*x0*x3 - 4*x1^2 + 4*x1*x13 + 8*x1*x2
  + 4*x1*x4 - 4*x10^2 + 8*x10*x11 + 4*x10*x13 - 4*x11^2 + 4*x11*x14 - 4*x12^2
  + 8*x12*x13 + 8*x12*x14 - 4*x13^2 + 8*x13*x14 - 4*x14^2 + 4*x2*x14 - 4*x2^2
  + 4*x2*x5 + 4*x3*x12 - 4*x3^2 + 8*x3*x4 + 8*x3*x5 + 4*x3*x6 + 4*x3*x9
  + 4*x4*x10 + 4*x4*x13 - 4*x4^2 + 8*x4*x5 + 4*x4*x7 + 4*x5*x11 + 4*x5*x14
  - 4*x5^2 + 4*x5*x8 - 4*x6^2 + 8*x6*x7 + 8*x6*x8 + 4*x6*x9 + 4*x7*x10 - 4*x7^2
  + 8*x7*x8 + 4*x8*x11 - 4*x8^2 + 8*x9*x10 + 8*x9*x11 + 4*x9*x12 - 4*x9^2

Subject to
  No constraints

  Binary variables (15)
    x0 x1 x2 x3 x4 x5 x6 x7 x8 x9 x10 x11 x12 x13 x14

This produces a clear representation of our problem, highlighting the objective function (which we wish to minimize).

Seeking Solutions with QAOA

Quantum Approximate Optimization Algorithm (QAOA) is a quantum algorithm that helps find the solution to combinatorial problems like ours. With Qiskit, we can run QAOA:

algorithm_globals.random_seed = 12345
qaoa_mes = QAOA(sampler=Sampler(), optimizer=COBYLA())
qaoa = MinimumEigenOptimizer(qaoa_mes)

qaoa_result = qaoa.solve(qp)
print(qaoa_result.prettyprint())

objective function value: -20.0
variable values: x0=0.0, x1=1.0, x2=0.0, x3=0.0, x4=0.0, x5=1.0, x6=1.0, x7=0.0, x8=0.0, x9=0.0, x10=1.0, x11=0.0, x12=1.0, x13=0.0, x14=0.0
status: SUCCESS

This tells us the most optimal solution found by the QAOA: an objective function value of -20, with specific binary variable values.

Assigning Colors to Nodes

Given our results, how do we interpret them in terms of our graph coloring problem? With the function assign_color, we can take the quantum result and convert it into recognizable colors:

def assign_color(result, num_color):
    colors = ["BLUE", "GREEN", "RED", "YELLOW", "ORANGE", "PINK", "BLACK", "BROWN", "WHITE", "PURPLE", "VIOLET"]
    color_map = list()
    for pos, val in enumerate(result.x):
      if int(val) == 1:    
            node = pos//num_color + 1
            color = pos%num_color
            color_map.append(colors[color])
            print("for node %s with bin var %s the assigned color is %s"%(node, pos, colors[color]))
    return color_map
    
qaoa_color_map = assign_color(qaoa_result,3)

for node 1 with bin var 1 the assigned color is GREEN
for node 2 with bin var 5 the assigned color is RED
for node 3 with bin var 6 the assigned color is BLUE
for node 4 with bin var 10 the assigned color is GREEN
for node 5 with bin var 12 the assigned color is BLUE

Each node in our graph has now been assigned a unique color such that adjacent nodes do not have the same color — solving our graph coloring problem!

Visualizing the Solution

Lastly, to make this journey visually appealing, we can draw our graph with the colored nodes:


def draw_color_graph(n, e, color_map):
    G= nx.Graph()
    G.add_nodes_from([i for i in range(1, n+1)])
    G.add_edges_from(e)
    nx.draw(G, node_color=color_map, node_size=600, with_labels= True)

    return G

gra = draw_color_graph(n, e, qaoa_color_map)

This graphical representation showcases the power and utility of quantum computing in solving problems like graph coloring. Not only does it provide a solution, but it also ensures that the solution is both aesthetically pleasing and meets our conditions of no two adjacent nodes sharing the same color!

Note: For the actual solution of the Sudoku problem, these calculations would need to be made considering that there is an initial state where certain cells have been provided to us filled with a number.

Summary and Conclusion:

In this exploration, we’ve viewed Sudoku, a traditionally simple logic puzzle, through the lens of quantum computing and combinatorial optimization. We demonstrated how a Sudoku puzzle can be framed as a graph coloring problem and then modeled for quantum computation using QUBO. Leveraging the capabilities of Qiskit and the QAOA algorithm, we sought solutions that respect Sudoku’s inherent constraints. This approach not only offers an intriguing perspective on solving Sudoku but also underscores the vast potential of quantum algorithms in tackling complex combinatorial challenges. As quantum technology continues to evolve, its applicability in diverse domains, from games to real-world problems, becomes increasingly evident.

Notebook: https://github.com/Morcu/sudoku-colouring-problem-QAOA/blob/main/Sudoku_QAOA.ipynb

Diving Deeper: Practical Applications of the Coloring Problem

While the coloring problem has its roots in pure mathematics, it’s fascinating to see how it intertwines with real-world scenarios. When people hear about the coloring problem, they might picture a playful activity involving crayons and a coloring book. However, in the context of graph theory and combinatorics, the coloring problem plays a crucial role in solving some of the most intricate issues we face in diverse fields. Here are some of the practical applications:

Frequency Assignment for Cellular Networks: In the realm of telecommunications, the coloring problem aids in the frequency assignment for cell towers. Ensuring that two geographically close towers don’t use the same frequency band is crucial to avoid interference. This problem is analogous to ensuring neighboring nodes (representing towers) in a graph don’t share the same color (frequency).
Register Allocation in Computer Compilers: When a computer program gets compiled, the compiler must allocate memory registers for variables. If two variables are used at the same time, they can’t be stored in the same register. The graph coloring problem helps in efficiently allocating these registers, where each variable is a node, and an edge indicates concurrent use.
Examination Scheduling: In educational institutions, scheduling exams so that no two subjects with common students occur at the same time can be represented as a coloring problem. Here, subjects are nodes, and an edge between two nodes indicates that there’s a common student between those subjects.
Traffic Signal Scheduling: Imagine traffic intersections where signals need to be scheduled in a way that they don’t conflict with one another. By representing each signal as a node and edges between conflicting signals, the coloring problem can help in optimizing signal timings.
Sport Scheduling: In sports leagues, teams need to be scheduled in a way that they don’t play multiple games simultaneously or in quick succession. This scheduling issue can be visualized as a coloring problem, ensuring adequate rest and logistical feasibility.
Map Coloring: This is the classic problem that gave birth to the entire concept. It revolves around coloring a map in such a way that no two adjacent regions share the same color. This has implications not just in cartography but in determining territories, zones, or divisions in various applications.

These are just a few glimpses into the myriad ways in which the coloring problem, a concept that seems so abstract at first, finds its practical footing in our day-to-day world. From ensuring clear cell phone calls to optimizing computer programs, this mathematical challenge continues to shape and improve numerous aspects of modern life.