Demo - killer sudoku

killer_demo.py

import pulp

prob = pulp.LpProblem("Sudoku Problem2")
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(
    "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

prob.solve()

# map choices to list of lists
res = [
    [v for i in range(9) for v in range(1, 10) if choices[i][j][v].value() == 1]
    for j in range(9)
]

# checking a few constraints match
assert res[8][7] + res[8][8] == 8
## assertion error

assert res[0][0] + res[0][1] == 8
print(res)

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)

Thanks this is amazing