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:
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
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:
Post your questions or see what others have asked on our Competition support site.
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).
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:
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.
We look forward to reviewing your solution. Here are some things to know: