from ortools.sat.python import cp_model
def solve_slant_puzzle(puzzle):
n = len(puzzle)
# Create an instance of the CP-SAT model
model = cp_model.CpModel()
# Define the decision variables as a matrix representing the grid cells
x = []
for i in range(n):
row = []
for j in range(n):
row.append(model.NewIntVar(0, 1, f"x[{i}][{j}]"))
x.append(row)
# Circled number constraint
for i in range(n):
for j in range(n):
if isinstance(puzzle[i][j], int):
k = puzzle[i][j]
neighbors = []
if i > 0 and j > 0:
neighbors.append(x[i-1][j-1])
if i > 0 and j < n-1:
neighbors.append(x[i-1][j])
if i < n-1 and j > 0:
neighbors.append(x[i][j-1])
if i < n-1 and j < n-1:
neighbors.append(x[i][j])
model.Add(sum(neighbors) == k)
# No loop constraint
for i in range(n-2):
for j in range(n-2):
model.Add(x[i][j] + x[i+1][j+1] + x[i][j+1] + x[i+1][j] != 2)
# Solve the model using the CP-SAT solver
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
solution = [[solver.Value(x[i][j]) for j in range(n)] for i in range(n)]
# Print the solution with diagonal lines for an (N-1)x(N-1) matrix
for i in range(n-1):
line = ""
for j in range(n-1):
if solution[i][j] == 0:
line += "\\ "
else:
line += "/ "
print(line)
else:
print("No solution found.")
# Example puzzle
puzzle = [
[1, "*", "*", 1],
["*", "*", 2, "*"],
["*", 2, "*", "*"],
[1, "*", "*", 1],
]
solve_slant_puzzle(puzzle)