Kakuro - a constraint satisfaction problem

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.

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.