| page_type | languages | products | description | |||
|---|---|---|---|---|---|---|
sample |
|
|
This sample uses Grover's search algorithm to solve Sudoku puzzles. |
This program demonstrates solving Sudoku puzzle using Grover's algorithm. The code supports both 4x4 and 9x9 Sudoku puzzles.
For 4x4 puzzles, the same rules apply:
-
The numbers 0 to 3 may only appear once per row, column and 2x2 sub squares.
As an example has solution _________________ _________________ | | 1 | | 3 | | 0 | 1 | 2 | 3 | ----------------- ----------------- | 2 | | | 1 | | 2 | 3 | 0 | 1 | ----------------- ----------------- | | | 3 | 0 | | 1 | 2 | 3 | 0 | ----------------- ----------------- | 3 | | 1 | | | 3 | 0 | 1 | 2 | ----------------- -----------------
Sudoku is a graph coloring problem where graph edges must connect nodes of different colors. In our case, graph nodes are puzzle squares and colors are the Sudoku numbers. Graph edges are the constraints preventing squares from having the same values. In the above example, the constraints for the top row are
_________
| ______ \ _____
|| __ \ \ | __ \ __
_|||__\___\_ _\__ ______||__\___\__ _________|___\__
| | 1 | | 3 | | | 1 | | 3 | | | 1 | | 3 |
----------------- ----------------- -----------------
To reduce the number of qubits, we only use qubits for empty squares. Each empty square gets 2 qubits to encode the numbers 0 to 3. We define the puzzle using 2 data structures.
- A list of edges connecting empty squares
- A list of constraints on empty squares to the initial numbers in the puzzle (starting numbers)
For example, for the row above the empty squares have indices:
_________________
| 0 | | 1 | |
-----------------
and emptySquareEdges is the array of edges.
For example, cell 0 can't have the same number (color) as cell 1, so emptySquareEdges = [(0, 1)].
Similarly, startingNumberConstraints is the array of (Cell#, constraint).
For example, the constraint that empty cell 0 can't have value 1 or 3 is encoded as startingNumberConstraints = [(0, 1), (0, 3), (1, 1), (1, 3)].
Note that the puzzles are initially defined in C# using numbers from 1 to 4, or 1 to9. However, when solving this using a quantum program and encoding these values into qubits, the numbers are changed to 0 to 3 and 0 to 8 and then converted back. This allows a 4x4 puzzle to be solved using 2 qubits per missing number.
The code can also solve 9x9 Sudoku puzzles using 4 qubits per number. However, trying to use more than 8 qubits (2 empty squares) in a simulation becomes very slow, so here we only run it for 1 or 2 missing squares in a 9x9 puzzle.
The graph coloring code is based on the Graph Coloring Kata with the following changes:
- allow for varying qubits per color
- constraints on Vertex colors based on initial colors when you start
- for 9x9 puzzles, 4 bits per color are used but the colors in the solution can only be 0 to 8
- The Microsoft Quantum Development Kit.
To run the sample, use the dotnet run command from your terminal.
This will run all the test puzzles.
You can also choose a specific puzzle to solve by adding the puzzle name as below
- 4x4-classic : test classic algorithm on a 4x4 puzzle
- 4x4-1: test Quantum solution of 4x4 puzzle missing 1 number
- 4x4-3: test Quantum solution of 4x4 puzzle missing 3 numbers
- 4x4-4: test Quantum solution of 4x4 puzzle missing 4 numbers
- 9x9-1: test classic algorithm and Quantum solution on a 9x9 puzzle with 1 missing number
- 9x9-2: test Quantum solution on a 9x9 puzzle with 2 missing numbers
- 9x9-64: test classic algorithm and Quantum solution on a 9x9 puzzle with 64 missing numbers
For example, dotnet run 4x4-4 will run the Quantum solution for a 4x4 puzzle with 4 missing numbers
- ColoringGroverWithConstraints.qs: Q# code implementing graph coloring with flexible number of bits per color and ability to specify constraints on the colors found per Vertex. A custom oracle for coloring with only 9 colors is also implemented.
- Program.cs: C# code with Sudoku test problems to solve using classical or Quantum code. It then checks and displays the results.
- Sudoku.qs: Q# code which accepts edges and constraints and calls Grover's algorithm with the coloring oracle. Also checks the result is correct.
- SudokuClassic.cs: C# code to solve a Sudoku puzzle using classical code.
- SudokuQuantum.cs: C# code to solve a Sudoku puzzle by transforming it into a graph problem (edges and starting number constraints), and call the Quantum SolvePuzzle operation to solve it.
- SudokuGroverSample.csproj: Main project for the sample.
dotnet run 4x4-4
Quantum Solving 4x4 with 4 missing numbers.
-----------------
| | | 3 | 4 |
-----------------
| | | 1 | 2 |
-----------------
| 2 | 3 | 4 | 1 |
-----------------
| 4 | 1 | 2 | 3 |
-----------------
Running Quantum test with #Vertex = 4
Bits Per Color = 2
emptySquareEdges = [(1, 0),(2, 0),(3, 0),(3, 1),(3, 2)]
startingNumberConstraints = [(0, 1),(0, 3),(0, 2),(1, 2),(1, 0),(1, 3),(2, 1),(2, 3),(2, 0),(3, 2),(3, 0),(3, 1)]
Estimated #iterations needed = 12
Size of Sudoku grid = 4x4
Trying search with 1 iterations...
Trying search with 2 iterations...
Trying search with 3 iterations...
Got Sudoku solution: [0,1,2,3]
Got valid Sudoku solution: [0,1,2,3]
Solved puzzle.
Result verified correct.
-----------------
| 1 | 2 | 3 | 4 |
-----------------
| 3 | 4 | 1 | 2 |
-----------------
| 2 | 3 | 4 | 1 |
-----------------
| 4 | 1 | 2 | 3 |
-----------------
dotnet run 9x9-2
Solving 9x9 with 2 missing numbers using Quantum Computing.
-------------------------------------
| | 7 | 3 | 8 | 9 | 4 | 5 | 1 | 2 |
-------------------------------------
| 9 | | 2 | 7 | 3 | 5 | 4 | 8 | 6 |
-------------------------------------
| 8 | 4 | 5 | 6 | 1 | 2 | 9 | 7 | 3 |
-------------------------------------
| 7 | 9 | 8 | 2 | 6 | 1 | 3 | 5 | 4 |
-------------------------------------
| 5 | 2 | 6 | 4 | 7 | 3 | 8 | 9 | 1 |
-------------------------------------
| 1 | 3 | 4 | 5 | 8 | 9 | 2 | 6 | 7 |
-------------------------------------
| 4 | 6 | 9 | 1 | 2 | 8 | 7 | 3 | 5 |
-------------------------------------
| 2 | 8 | 7 | 3 | 5 | 6 | 1 | 4 | 9 |
-------------------------------------
| 3 | 5 | 1 | 9 | 4 | 7 | 6 | 2 | 8 |
-------------------------------------
Running Quantum test with #Vertex = 2
Bits Per Color = 4
emptySquareEdges = [(1, 0)]
startingNumberConstraints = [(0, 8),(0, 7),(0, 6),(0, 4),(0, 0),(0, 3),(0, 1),(0, 2),(1, 6),(1, 3),(1, 8),(1, 1),(1, 2),(1, 5),(1, 7),(1, 4)]
Estimated #iterations needed = 12
Size of Sudoku grid = 9x9
Trying search with 1 iterations...
Trying search with 2 iterations...
Got Sudoku solution: [5,0]
Got valid Sudoku solution: [5,0]
Solved puzzle.
Result verified correct.
-------------------------------------
| 6 | 7 | 3 | 8 | 9 | 4 | 5 | 1 | 2 |
-------------------------------------
| 9 | 1 | 2 | 7 | 3 | 5 | 4 | 8 | 6 |
-------------------------------------
| 8 | 4 | 5 | 6 | 1 | 2 | 9 | 7 | 3 |
-------------------------------------
| 7 | 9 | 8 | 2 | 6 | 1 | 3 | 5 | 4 |
-------------------------------------
| 5 | 2 | 6 | 4 | 7 | 3 | 8 | 9 | 1 |
-------------------------------------
| 1 | 3 | 4 | 5 | 8 | 9 | 2 | 6 | 7 |
-------------------------------------
| 4 | 6 | 9 | 1 | 2 | 8 | 7 | 3 | 5 |
-------------------------------------
| 2 | 8 | 7 | 3 | 5 | 6 | 1 | 4 | 9 |
-------------------------------------
| 3 | 5 | 1 | 9 | 4 | 7 | 6 | 2 | 8 |
-------------------------------------