A simpler approach uses mixed-integer LP (MIP) and a mathematical programming DSL like julia/JuMP or python/pyomo.
Here's a trivial and fast MIP solution using python/pulp, which would be essentially the same in any mathematical programming DSL:
from collections import defaultdict
import pulp
board = [
["P", "P", "P", "P", "P", "P", "P", "P", "P"],
["P", "P", "R", "S", "S", "S", "L", "L", "L"],
["P", "R", "R", "W", "S", "L", "L", "L", "L"],
["P", "R", "W", "W", "S", "O", "O", "L", "L"],
["P", "R", "W", "Y", "Y", "Y", "O", "O", "L"],
["P", "R", "W", "W", "Y", "O", "O", "L", "L"],
["P", "R", "R", "W", "Y", "O", "B", "L", "L"],
["P", "R", "R", "G", "G", "G", "B", "B", "L"],
["P", "P", "R", "R", "G", "B", "B", "L", "L"],
]
# group by color for color constraint
def board_to_dict(board):
nr = len(board)
res = defaultdict(list)
for i, row in enumerate(board):
if len(row) != nr:
raise ValueError("Input must be a square matrix")
for j, color in enumerate(row):
res[color].append((i, j))
return res
color_regions = board_to_dict(board)
N = len(color_regions)
prob = pulp.LpProblem("Colored_N_Queens", pulp.LpMinimize)
x = [[pulp.LpVariable(f"x_{i}_{j}", cat="Binary") for j in range(N)] for i in range(N)]
# Row constraints
for i in range(N):
prob += pulp.lpSum(x[i][j] for j in range(N)) == 1
# Column constraints
for j in range(N):
prob += pulp.lpSum(x[i][j] for i in range(N)) == 1
# Color region constraints
for positions in color_regions.values():
prob += pulp.lpSum(x[i][j] for (i, j) in positions) == 1
# No diagonal adjacency
for i in range(N):
for j in range(N):
for di, dj in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
ni, nj = i + di, j + dj
if 0 <= ni < N and 0 <= nj < N:
prob += x[i][j] + x[ni][nj] <= 1
# Trivial objective
prob += 0
res = prob.solve()
print(f"Solver status: {pulp.LpStatus[prob.status]}")
if pulp.LpStatus[prob.status] == "Optimal":
for i in range(N):
row = ""
for j in range(N):
row += ("#" if pulp.value(x[i][j]) > 0.5 else " ") + board[i][j] + " "
print(row)
#P P P P P P P P P
P P R S S #S L L L
P R R W S L L L #L
P R #W W S O O L L
P R W Y Y Y O #O L
P R W W #Y O O L L
P #R R W Y O B L L
P R R #G G G B B L
P P R R G B #B L L