Skip to content

Instantly share code, notes, and snippets.

@Parcly-Taxel

Parcly-Taxel/knights.py

Last active February 27, 2025 08:51
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Parcly-Taxel/3482aeec506a6effc54f09e97f9fe722 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Parcly-Taxel/3482aeec506a6effc54f09e97f9fe722 to your computer and use it in GitHub Desktop.
Download ZIP
PSE 94766 and 130763
Raw
knights.py
#!/usr/bin/env python3
from ortools.sat.python import cp_model
# https://puzzling.stackexchange.com/q/94766/75318
class CB(cp_model.CpSolverSolutionCallback):
def __init__(self, litmap):
cp_model.CpSolverSolutionCallback.__init__(self)
self.litmap = litmap
def on_solution_callback(self):
w = []
for i in range(8):
for j in range(8):
if self.value(self.litmap[(0,i,j)]):
w.append("W")
elif self.value(self.litmap[(1,i,j)]):
w.append("B")
else:
w.append(".")
w.append("\n")
print("".join(w))
def place_knights(k):
board = [(i,j) for i in range(8) for j in range(8)]
model = cp_model.CpModel()
litmap = {}
for sq in board:
litmap[(0,*sq)] = model.NewBoolVar(f"w{sq}")
litmap[(1,*sq)] = model.NewBoolVar(f"b{sq}")
model.AddBoolOr(litmap[(0,*sq)].Not(), litmap[(1,*sq)].Not())
for sq in board:
for c in (0,1):
nbs = [litmap[(1-c,*ot)] for ot in board if abs((sq[0]-ot[0])*(sq[1]-ot[1])) == 2]
model.add(sum(nbs) == 3).only_enforce_if(litmap[(c,*sq)])
model.add(sum(litmap[(0,*sq)] for sq in board) == k)
model.add(sum(litmap[(1,*sq)] for sq in board) == k)
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 2
solver.parameters.enumerate_all_solutions = True
solver.Solve(model, CB(litmap))
place_knights(16)
"""
*4
...BW...
.WB..WB.
W.W..B.B
BWB..WBW
WBW..BWB
B.B..W.W
.BW..BW.
...WB...
*16
..W..W..
....B..B
.BWBBWB.
..BWBBWB
..WBWWBW
.WBWWBW.
....W..W
..B..B..
*4
..W..W..
B......B
.BWBBWB.
BWB..BWB
WBW..WBW
.WBWWBW.
W......W
..B..B..
*8
.B...W..
...W...B
WBW.BWB.
.WBW.BWB
.BWB.WBW
BWB.WBW.
...B...W
.W...B..
*4
.B....B.
...WW...
WBW..WBW
.WBWWBW.
.BWBBWB.
BWB..BWB
...BB...
.W....W.
*8
.W.W....
.B.B.B..
B.BWWW.W
.WWB.BB.
.WWB.BB.
B.BWWW.W
.B.B.B..
.W.W....
*8
....BB..
..WW..W.
BB..WWW.
..WBBBBB
WWWWWB..
.BBB..WW
.B..BB..
..WW....
#Done 94.76s main
Solution repositories Added Queried Synchro
'feasible solutions': 52 0 52
"""
Raw
nightriders.py
#!/usr/bin/env python3
from ortools.sat.python import cp_model
from itertools import combinations
# https://puzzling.stackexchange.com/q/130763/75318
class CB(cp_model.CpSolverSolutionCallback):
def __init__(self, litmap):
cp_model.CpSolverSolutionCallback.__init__(self)
self.litmap = litmap
def on_solution_callback(self):
w = []
for i in range(8):
for j in range(8):
if self.value(self.litmap[(i,j)]):
w.append("N")
else:
w.append(".")
w.append("\n")
print("".join(w))
def place_nightriders(k):
board = [(i,j) for i in range(8) for j in range(8)]
model = cp_model.CpModel()
litmap = {}
for sq in board:
litmap[sq] = model.NewBoolVar(f"{sq}")
for (s1, s2) in combinations(board, 2):
dx, dy = abs(s1[0]-s2[0]), abs(s1[1]-s2[1])
if dx == 2*dy or dy == 2*dx:
model.AddBoolOr(litmap[s1].Not(), litmap[s2].Not())
model.add(sum(litmap[sq] for sq in board) >= k)
solver = cp_model.CpSolver()
solver.parameters.linearization_level = 2
solver.parameters.enumerate_all_solutions = True
solver.Solve(model, CB(litmap))
place_nightriders(20) # two solutions
print("***")
place_nightriders(21) # no solutions
"""
N.N..N.N
.N....N.
N.N..N.N
........
........
N.N..N.N
.N....N.
N.N..N.N
.N....N.
NNN..NNN
.N....N.
........
........
.N....N.
NNN..NNN
.N....N.
"""
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment