Pulp Killer sudoku - check choices are distinct for choice of variables

Question

I am trying to solve killer Sudoku using Python linear optimization library, Pulp.

https://en.wikipedia.org/wiki/Killer_sudoku

Here is my attempt so far, adding a constraint that each row must add up to 45.

import pulp
prob = pulp.LpProblem("Sudoku Problem")
prob += 0, "Arbitrary Objective Function"

# 9 by 9 grid of 'choices', integers between 1-9
choices = pulp.LpVariable.dicts(
"Choice", (range(9), range(9)), cat="Integer", lowBound=1, upBound=9)

# identify puzzle rows that must have only 1 of every value 
row_groups = [[(i, j) for i in range(9)] for j in range(9)]

# Seems to work, make every row add up 45
for distinct_group in row_groups:
    for i, j in distinct_group:
        distinct_group_constraint = [choices[i][j] for i, j in distinct_group]
    prob += pulp.lpSum(distinct_group_constraint) == 45


# ... Code to add additional constraints for columns, boxes and 'cages'. Excluded for brevity.

prob.solve()

The problem is I'm struggling to add a stricter constraint that each value in a row must be different. For example, if a row had these values

[1,9,1,9,1,9,1,9,5]

It would pass the constraint above, but would not be a valid sudoku row because each value is not unique.

Below is my attempt to add a stricter constraint, it seems not work, since the problem doesn't solve

for n in range(1, 10):
    for distinct_group in row_groups:
        for i, j in distinct_group:
            distinct_group_constraint = [choices[i][j] == n for i, j in distinct_group]
        prob += pulp.lpSum(distinct_group_constraint) == 1

I have seen several examples online, resolving this by reframing this optimisation as a 9x9x9 choice of binary flags, rather than 9x9 optimisation of choices of integers 1-9. The issue is, I find it hard to see how to check the sums of 'cages' easily in the 9x9x9 case, whist this is quite simple in 9x9 case.

Here is an example of the 9x9x9 setup for a 'non-killer' sudoku. https://github.com/coin-or/pulp/blob/master/examples/Sudoku1.py

# cells (0,0) and (0,1) must sum to 8
cage_constraints = [(8, [[0, 0], [0, 1]])]

for target, cells in cage_constraints:
    cage_cells_constraint = [choices[i][j] for i, j in cells]
    prob += pulp.lpSum(cage_cells_constraint) == target

I am looking to (a) find a way to add this stricter constraint that no choices can be duplicated in the 9x9 setup, or (b) a way to easily add constraints of the 'sum' of cages in the 9x9x9 case. If you would like the entire list of cage-constraints to test on, here are a list of cage-constraints from this puzzle.

CAGE_CONSTRAINTS = [
(8, [[0, 0], [0, 1]]),
(9, [[0, 6], [0, 7]]),
(8, [[0, 2], [1, 2]]),
(12, [[0, 3], [0, 4], [1, 3]]),
(15, [[0, 5], [1, 5], [2, 5]]),
(19, [[1, 6], [1, 7], [2, 7]]),
(16, [[0, 8], [1, 8], [2, 8]]),
(14, [[1, 0], [1, 1], [2, 0]]),
(15, [[2, 1], [2, 2]]),
(10, [[2, 3], [3, 3]]),
(12, [[1, 4], [2, 4]]),
(7, [[2, 6], [3, 6]]),
(24, [[3, 0], [3, 1], [4, 1]]),
(17, [[3, 7], [3, 8], [4, 8]]),
(8, [[3, 2], [4, 2]]),
(12, [[4, 3], [5, 3]]),
(19, [[3, 4], [4, 4], [5, 4]]),
(4, [[3, 5], [4, 5]]),
(15, [[4, 6], [5, 6]]),
(12, [[4, 0], [5, 0], [5, 1]]),
(7, [[4, 7], [5, 7], [5, 8]]),
(8, [[5, 2], [6, 2]]),
(10, [[6, 4], [7, 4]]),
(14, [[5, 5], [6, 5]]),
(12, [[6, 6], [6, 7]]),
(18, [[6, 8], [7, 7], [7, 8]]),
(15, [[6, 0], [7, 0], [8, 0]]),
(13, [[6, 1], [7, 1], [7, 2]]),
(12, [[6, 3], [7, 3], [8, 3]]),
(15, [[7, 5], [8, 4], [8, 5]]),
(7, [[7, 6], [8, 6]]),
(10, [[8, 1], [8, 2]]),
(8, [[8, 7], [8, 8]]),
]

https://www.dailykillersudoku.com/search?dt=2020-02-15

and here is the solution https://www.dailykillersudoku.com/pdfs/19664.solution.pdf

EDIT - if I try changing to a 9x9x9 problem with binary choices, I get results that don't match my desired cage constraints. Here is a snippet.

choices = pulp.LpVariable.dicts(
    "Choice", (range(9), range(9), range(1, 10),), cat="Binary"
)

# add constraints that only one choice for each 'distinct_group'
for n in range(1, 10):
    for distinct_group in distinct_groups:
        for i, j in distinct_group:
        distinct_group_constraint = [choices[i][j][n] for i, j in 
distinct_group]
        prob += pulp.lpSum(distinct_group_constraint) == 1

# add constraints that cells in cages must equal 'cage_total'
for target, cells in CAGE_CONSTRAINTS:
    cage_cells_constraint = [
        choices[i][j][n] * n for i, j in cells for n in range(1, 10)
    ]
    prob += pulp.lpSum(cage_cells_constraint) == target

and here is full example https://gist.github.com/olicairns/d8e222526b87a62b2e175837b452c24a

Answer 1

I would reccomend the use of binary variables - as per the examples you have found. It may seem like more variables but as far as I know use use of a smaller number of integer variables will not help solution time at all - the way the 'branch-and-bound' algorithm for solving a problem with integer variables will mean it's just as inefficient as having more binary variables (someone more familiar with this may be able to correct me).

So to answer the second half of your question:

(b) a way to easily add constraints of the 'sum' of cages in the 9x9x9 case.

This is quite straightforward - you just to a sum-product of the binary variables for a cell by the index which each varaible represents.

If you've already developed all the code assuming your choice of variables (9x9 integer variables), you can add the 9x9x9 binary variables, and then constraint your 9x9 integer variables (which would now be auxiliary variables) as follows:

for i in range(1, 10):
    for j in range(1, 10):
        pulp += choices[i][j] == pulp.lpSum([binary_choices[i][j][k]*k for k in range(1,10)])

You now have both sets of variables - one lot of binary variables, and one lot of integer variables which are linked with equality constraints to behave as required. If you want to avoid all the auxillary variables then you would just need to replace a sum-product with the index value as above anywhere you are currently using your integer variables.

Full working code for completeness:

import pulp

prob = pulp.LpProblem("Sudoku_Problem_KA")
prob += 0, "Arbitrary Objective Function"

CAGE_CONSTRAINTS = [
    (8., [[0, 0], [0, 1]]),
    (9., [[0, 6], [0, 7]]),
    (8., [[0, 2], [1, 2]]),
    (12., [[0, 3], [0, 4], [1, 3]]),
    (15., [[0, 5], [1, 5], [2, 5]]),
    (19., [[1, 6], [1, 7], [2, 7]]),
    (16., [[0, 8], [1, 8], [2, 8]]),
    (14., [[1, 0], [1, 1], [2, 0]]),
    (15., [[2, 1], [2, 2]]),
    (10., [[2, 3], [3, 3]]),
    (12., [[1, 4], [2, 4]]),
    (7., [[2, 6], [3, 6]]),
    (24., [[3, 0], [3, 1], [4, 1]]),
    (17., [[3, 7], [3, 8], [4, 8]]),
    (8., [[3, 2], [4, 2]]),
    (12., [[4, 3], [5, 3]]),
    (19., [[3, 4], [4, 4], [5, 4]]),
    (4., [[3, 5], [4, 5]]),
    (15., [[4, 6], [5, 6]]),
    (12., [[4, 0], [5, 0], [5, 1]]),
    (7., [[4, 7], [5, 7], [5, 8]]),
    (8., [[5, 2], [6, 2]]),
    (10., [[6, 4], [7, 4]]),
    (14., [[5, 5], [6, 5]]),
    (12., [[6, 6], [6, 7]]),
    (18., [[6, 8], [7, 7], [7, 8]]),
    (15., [[6, 0], [7, 0], [8, 0]]),
    (13., [[6, 1], [7, 1], [7, 2]]),
    (12., [[6, 3], [7, 3], [8, 3]]),
    (15., [[7, 5], [8, 4], [8, 5]]),
    (7., [[7, 6], [8, 6]]),
    (10., [[8, 1], [8, 2]]),
    (8., [[8, 7], [8, 8]]),
]

# groups that should only have 1 of each number 1-9
row_groups = [[(i, j) for i in range(9)] for j in range(9)]
col_groups = [[(j, i) for i in range(9)] for j in range(9)]
box_groups = [
    [(3 * i + k, 3 * j + l) for k in range(3) for l in range(3)]
    for i in range(3)
    for j in range(3)
]
distinct_groups = row_groups + col_groups + box_groups

# binary choices: rows, columns and values 1-9
choices = pulp.LpVariable.dicts(
    "choices", (range(9), range(9), range(1, 10)), cat="Binary"
)

# add constraints that only one choice for each 'distinct_group'
for n in range(1, 10):
    for distinct_group in distinct_groups:
        prob += pulp.lpSum([choices[i][j][n] for i, j in distinct_group]) <= 1

# add constraints that cells in cages must equal 'cage_total'
for target, cells in CAGE_CONSTRAINTS:
    prob += pulp.lpSum([choices[i][j][n] * n for i, j in cells for n in range(1, 10)]) >= target

# only pick one binary value per cell:
for i in range(9):
    for j in range(9):
        prob += pulp.lpSum([choices[i][j][n] for n in range(1, 10)]) <= 1

prob.solve()

print('Status:',pulp.LpStatus[prob.status])

# Extract results
res = [[sum([choices[i][j][n].varValue*n for n in range(1,10)]) for j in range(9)] for i in range(9)]

# checking a few constraints match
assert res[8][7] + res[8][8] == 8
assert res[0][0] + res[0][1] == 8

print(res)