Solving a Sudoku puzzle with Grover's Algorithm.

A Sudoku puzzle is an $n^2 \times n^2$ array, where each cell contains a number from $1$ to $n^2$. The initial puzzle usually contains several blank cells, which must be filled in according to the following rules:

• Each row must contain exactly one of each number
• Each column must contain exactly one of each number
• Each of the $n^2$ sub blocks of dimension $n\times n$ that form the puzzle must contain exactly one of each number.

Here I implement Grover's Algorithm to solve an $n^2 \times n^2$ Sudoku puzzle. The functions in the document are as follows:

Indexing functions:

The Sudoku puzzle is given as a string instead of its normal cell/matrix form. When figuring out what rules correspond to things like "each row can only contain one of each number," it's easier to reference row i and column j. Since the Sudoku puzzle is a string however, the cell at the ith row and jth column is at the (N*j + i)th place in the string. Since this is confusing to compute every time a row and column need to be referenced, these two functions translate back and forth between row-column list indexing and a global index.

"globalindex"

• Translates Python matrix indexing of $M[i,j]$ for $n\times n$ matrix $M$ to C array indexing of $n*i+j$.

"matrixindex"

• Translates C array indexing to Python matrix indexing.

"initialize_rules"

• Processes the puzzle and initializes rules.
• Args:
  • "puzzle": The Sudoku puzzle as a string, with 0's in the places of missing numbers.
• Returns:
  • A list of lists, where the sublists are each a "rule" of the puzzle, in that the indices of two empty cells are together in a sublist if they cannot have the same value.
  • A list of the empty spots in the puzzle (in global indexing).

"make_diffuser"

• Makes the diffuser circuit for Grover's Algorithm.
• Args:
  • "q_reg": A QuantumRegister item, with dimension that is the product of the number of possibilities one cell can be, and the number of empty cells in the puzzle.
• Returns:
  • A Qiskit QuantumCircuit of the diffuser circuit for Grover's Algorithm.

"make_oracle"

• Makes an oracle that implements the rules of the puzzle, where the empty cells cannot be solved as having the same value as another empty cell in the same row, column, or subgrid.
• Args:
  • "q_reg": A QuantumRegister item, with dimension that is the product of the number of possibilities one cell can be, and the number of empty cells in the puzzle.
  • "ar_reg": An AncillaRegister item with dimension that is the sum of the number of empty cells in the puzzle, and the number of rules. Holds the true/false value of each "rule".
  • "ac_reg": An AncillaRegister item with dimension 1, that holds the true/false value of whether or not this assignment of solution cells is valid.
  • "rules": The list of lists in which two (global) indices are in a sublist together if and only if they cannot be the same value.
  • "empties": The list of the (global) indices of all the empty spots in the puzzle.
• Returns:
  • A Qiskit QuantumCircuit of the oracle circuit for Grover's Algorithm.

"moracle"

• Adds to an existing oracle circuit the restrictions that arise from the input puzzle.

"make_grover_circuit"

• Uses initialize_rules, make_diffuser, and make_oracle.
• Computes the number of necessary iterations of Grover's Algorithm on a problem of the given size.
• Constructs the Grover's Algorithm circuit.
• Args:
  • "puzzle": The Sudoku puzzle as a string
• Returns:
  • A Qiskit QuantumCircuit that implements Grover's Algorithm.

"get_results"

• Translates the output of the Grover Algorithm circuit into two lists of the possible results and the probabilities of obtaining those results.
• Args:
  • "output_state": A Statevector of a circuit.
• Returns:
  • A list of the possible states one can get from this circuit.
  • A list of the corresponding probabilities of getting those states.

"sudoku_solver"

• Solves a given Sudoku puzzle using Grover's Algorithm.
• Args:
  • "puzzle": An $n^2\times n^2$ Sudoku puzzle in the form of a string of the given numbers in the puzzle, where empty cells are represented with a $0$.
• Returns:
  • Prints all relevant information to the puzzle:
  • The number of qubits the algorithm needs.
  • The state vector with the highest probability, along with that associated probability.
  • The initial puzzle.
  • The computed solution numbers that go in the empty cells.
  • The solved puzzle.