Kakuro - a constraint satisfaction problem

SEE WINNING SOLUTIONS

Background

Kakuro is a logic puzzle, often referred to as a mathematical transliteration of the crossword. The puzzle is played on a grid of filled and empty cells. The filled cells contain the required sum for the matching empty cells. The objective of the puzzle is to fill the empty spaces under two constraints:

Two cells on the same row/column cannot have the same number.
The sum of the cells on each row/column should equal the matching filled cell.

The Problem

Your goal is to solve this Kakuro puzzle using Grover’s algorithm.

UPDATE: Here (on the competition support site) is the list of constraints that you should use.

FINAL UPDATE: The winning solutions are now posted here

The puzzle for the challenge

Metric

You need to submit the oracle you used for the puzzle, and your score will be the number of 2- qubit gates in your oracle. Use only CX gates as your 2-qubit gates. Your goal is to minimize the number of 2-qubit CX gates.

The submission should include the following:

The oracle you created before transpilation. This will be used to score the submission.
The full Grover Circuit (including state preparation, the number of Grover operators required, and measurement at the end). This will be used to test the submission.
An explanation of the optimization you used - you should convince us that the oracle is indeed correct and flip the sign only for all the good states.

Questions?

Post your questions or see what others have asked on our Competition support site.

Additional details

UPDATE: Here (on the Discourse support site) is the list of constraints you should use in your Grover search.

The rules are Kakuro’s basic rules, mentioned above, with these additional rules:

1. Each empty cell should contain a number between 0 and 3. Note that, unlike the original Kakuro, we will be counting 0-based.

2. You are not allowed to solve the puzzle manually, or to assign a fixed value to variables, even if you know what value they hold! Each empty cell should hold its variable (a variable is a quantum register).

  • For example, let's say you know that x1 = 2 since it is the only viable option.
  • Even if you know that x1 must be 2, you still need to define a variable for x1 and add constraints that say it must equal 2.
  • If you have other constraints that involve x1, such as (x1 + x2 = 3), you cannot change that constraint to (2 + x2 = 3) – That would amount to solving the puzzle manually!

3. You may define the problem as you wish, as long as it stays true to the real problem (i.e., the solutions are the same, no more and no less). That includes:

  • Define the variables per the puzzle.
  • Remove/combine unnecessary constraints based on the puzzle.
For Example:
To clarify some of the optimization techniques you are allowed to use, let us define the next Kakuro puzzle as an example:
The initial set of constraints is to make sure the numbers in each row and column are different and that their sum is correct. The constraints are:
1.
x0 != x1
2.
x2 != x3
3.
x0 != x2
4.
x1 != x3 
5.
x0 + x1== 3
6.
x2 + x3== 4 
7.
x0 + x2== 3 
8.
x1 + x3== 4 

However, exploring the problem can allow you to reduce some of the constraints:

1. Since x0 + x2 = 3, they are inherently different since this is an odd sum of two variables. It allows us to remove constraint 3. The same goes for constraint 1.

2. Adding constraints 5 and 6 tells us that x0 + x1 + x2 + x3 = 3 + 4 = 7. Subtracting constraint 7 from this result gives us x1 + x3 = 4 , which is constraint 8. This means we can drop constraint 8, as it is built into constraints 5, 6, and 7.

These rules eliminate three constraints in this example, leaving us with a smaller problem. Now we can find a solution to the problem using Grover’s algorithm. In this case, the solution is:

x0 = 2, x1 = 1, x2 = 1, x3 = 3

submit your solution here

We look forward to reviewing your solution. Here are some things to know:

You are welcome to submit multiple solutions. If you submit something today, and find an improvement later on, you're welcome to submit the new solution as well.
Each problem requires slightly different information. Please make sure you carefully review the problem instructions.
The description of the approach is very helpful to the judges in understanding your work. Please include as much detail as you wish. We're interested in how you approached this problem, how your solution works, how long it took you to develop it, and whether there were particular problems that you overcame. We'd love to hear as much as you want to tell us. You can submit this in the 'description' field or include it as the 'Additional file (optional)' attachment.
The QASM code is how we can verify the 2-qubit gate count and/or circuit depth. It should include only CX and single-qubit unitary gates. This note on our Discourse support site might help.
If you created the circuit in something other than QASM, please submit the source code as well.
You will receive an email confirming the submission within a few minutes.
Submissions are closed. the results are here. Thank you!
0
DAYS
:
0
Hours
:
0
Minutes
:
0
Seconds
Don't remember your password?
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Submission
*QASM Code
Uploading...
fileuploaded.jpg
Upload failed. Max size for files is 10 MB.
Source code
Uploading...
fileuploaded.jpg
Upload failed. Max size for files is 10 MB.
Additional file (can be a detailed description)
Uploading...
fileuploaded.jpg
Upload failed. Max size for files is 10 MB.
Logout
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.