如何使用 Google OR 工具解决流程游戏？
How to solve flow game using Google OR tools?
我尝试使用 google-OR 工具为流程游戏制作求解器。
我为角落制定了一些规则，只包含角落管道，但除此之外，我不知道如何让管道相互连接，也不知道如何告诉模型制作一个管道相互连接。
一些片段
pipe_types = {
0: " ",
1: "-",
2: "|",
3: "┗" ,
4: "┛" ,
5: "┓",
6: "┏",
7: "●"
}
model = cp_model.CpModel()
filled_map = [[0,0,0,0],
[0,0,7,0],
[0,0,0,0],
[0,7,0,0]]
mesh_size = int(np.sqrt(len(np.array(filled_map).flatten())))
target_map = [[model.NewIntVar(1, 6, 'column: %i' % i) for i in range(mesh_size)] for j in range(mesh_size)]
flow_map = init_map(model, target_map, filled_map)
for i in range(len(flow_map)):
for j in range(len(flow_map[0])):
# check if top or bottom side
if (i == 0) or (i == len(flow_map)-1):
model.Add(flow_map[i][j] != 2)
# check if left or right side
if (j == 0) or (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 1)
# left up corner
if (i == 0) & (j == 0):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 5)
# right up corner
if (i == 0) & (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 6)
# left bottom corner
if (i == len(flow_map)-1) & (j == 0):
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 5)
model.Add(flow_map[i][j] != 6)
# right bottom corner
if (i == len(flow_map)-1) & (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 5)
model.Add(flow_map[i][j] != 6)
# Solving
status = solver.Solve(model)
res = []
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
for i in range(len(flow_map)):
for j in range(len(flow_map[0])):
res.append(solver.Value(flow_map[i][j]))
print(solver.Value(flow_map[i][j]), end=" ")
print()
这会导致网格中心出现水平管道。稍后，我还得弄清楚如何在上面添加颜色等等。
是否有关于如何在 OR 工具上进行此操作的指示？
编辑 1：
根据 David Eisenstat 的回答，我可以找到解决方案。根据 JohanC 的回答可视化这个解决方案，我得到了这个结果。
我可以从 google-OR 工具中获取路径吗？
编辑 2：
使用来自 的汉密尔顿路径
我可以生成一些正确的路径。
但感觉很奇怪，因为OR工具已经计算出路径了，我必须重新计算路径。从 生成的路径并未显示所有可能的组合。如果我可以从 OR 工具走上这条路，我认为那将是我最大的兴趣。
最好的方法可能是 AddCircuit。此约束采用有向图，其中每条弧都标有文字，并要求标记为 true 的弧形成一个子图，其中每个节点的入度和出度均为 1，并且最多有一个循环不是自身-环形。通过强制从尾到头的弧，我们可以使用这种约束类型来要求从头到尾只有一条路径。
文档有点少，所以这里有一个工作代码示例。画图的部分就交给你了
import collections
from ortools.sat.python import cp_model
def validate_board_and_count_colors(board):
assert isinstance(board, list)
assert all(isinstance(row, list) for row in board)
assert len(set(map(len, board))) == 1
colors = collections.Counter(square for row in board for square in row)
del colors[0]
assert all(count == 2 for count in colors.values())
num_colors = len(colors)
assert set(colors.keys()) == set(range(1, num_colors + 1))
return num_colors
def main(board):
num_colors = validate_board_and_count_colors(board)
model = cp_model.CpModel()
solution = [
[square or model.NewIntVar(1, num_colors, "") for (j, square) in enumerate(row)]
for (i, row) in enumerate(board)
]
true = model.NewBoolVar("")
model.AddBoolOr([true])
for color in range(1, num_colors + 1):
endpoints = []
arcs = []
for i, row in enumerate(board):
for j, square in enumerate(row):
if square == color:
endpoints.append((i, j))
else:
arcs.append(((i, j), (i, j)))
if i < len(board) - 1:
arcs.append(((i, j), (i + 1, j)))
if j < len(row) - 1:
arcs.append(((i, j), (i, j + 1)))
(i1, j1), (i2, j2) = endpoints
k1 = i1 * len(row) + j1
k2 = i2 * len(row) + j2
arc_variables = [(k2, k1, true)]
for (i1, j1), (i2, j2) in arcs:
k1 = i1 * len(row) + j1
k2 = i2 * len(row) + j2
edge = model.NewBoolVar("")
if k1 == k2:
model.Add(solution[i1][j1] != color).OnlyEnforceIf(edge)
arc_variables.append((k1, k1, edge))
else:
model.Add(solution[i1][j1] == color).OnlyEnforceIf(edge)
model.Add(solution[i2][j2] == color).OnlyEnforceIf(edge)
forward = model.NewBoolVar("")
backward = model.NewBoolVar("")
model.AddBoolOr([edge, forward.Not()])
model.AddBoolOr([edge, backward.Not()])
model.AddBoolOr([edge.Not(), forward, backward])
model.AddBoolOr([forward.Not(), backward.Not()])
arc_variables.append((k1, k2, forward))
arc_variables.append((k2, k1, backward))
model.AddCircuit(arc_variables)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
for row in solution:
print("".join(str(solver.Value(x)) for x in row))
if __name__ == "__main__":
main(
[
[1, 0, 0, 2, 3],
[0, 0, 0, 4, 0],
[0, 0, 4, 0, 0],
[0, 2, 3, 0, 5],
[0, 1, 5, 0, 0],
]
)
由于我没有使用 OR 工具的经验，这里有一个 Z3 的方法。
- 初始棋盘由端点数字表示，每种颜色一个数字。思路有点类似于how Sudoku is represented.
- 棋盘上的每个其他单元格将获得一个零值或一个数字。这个数字应该恰好等于它的两个邻居。
- 初始端点应恰好有一个具有其颜色的邻居。
from z3 import Solver, Sum, Int, If, And, Or, sat
def plot_solution(S):
import matplotlib.pyplot as plt
ax = plt.gca()
colors = plt.cm.tab10.colors
for i in range(M):
for j in range(N):
if board[i][j] != 0:
ax.scatter(j, i, s=500, color=colors[board[i][j]])
if S[i][j] != 0:
for k in range(M):
for l in range(N):
if abs(k - i) + abs(l - j) == 1 and S[i][j] == S[k][l]:
ax.plot([j, l], [i, k], color=colors[S[i][j]], lw=15)
ax.set_ylim(M - 0.5, -0.5)
ax.set_xlim(-0.5, N - 0.5)
ax.set_aspect('equal')
ax.set_facecolor('black')
ax.set_yticks([i + 0.5 for i in range(M - 1)], minor=True)
ax.set_xticks([j + 0.5 for j in range(N - 1)], minor=True)
ax.grid(b=True, which='minor', color='white')
ax.set_xticks([])
ax.set_yticks([])
ax.tick_params(axis='both', which='both', length=0)
plt.show()
board = [[1, 0, 0, 2, 3],
[0, 0, 0, 4, 0],
[0, 0, 4, 0, 0],
[0, 2, 3, 0, 5],
[0, 1, 5, 0, 0]]
M = len(board)
N = len(board[0])
B = [[Int(f'B_{i}_{j}') for j in range(N)] for i in range(M)]
s = Solver()
s.add(([If(board[i][j] != 0, B[i][j] == board[i][j], And(B[i][j] >= 0, B[i][j] < 10))
for j in range(N) for i in range(M)]))
for i in range(M):
for j in range(N):
same_neighs_ij = Sum([If(B[i][j] == B[k][l], 1, 0)
for k in range(M) for l in range(N) if abs(k - i) + abs(l - j) == 1])
if board[i][j] != 0:
s.add(same_neighs_ij == 1)
else:
s.add(Or(same_neighs_ij == 2, B[i][j] == 0))
if s.check() == sat:
m = s.model()
S = [[m[B[i][j]].as_long() for j in range(N)] for i in range(M)]
print(S)
plot_solution(S)
解决方案：
[[1, 2, 2, 2, 3],
[1, 2, 4, 4, 3],
[1, 2, 4, 3, 3],
[1, 2, 3, 3, 5],
[1, 1, 5, 5, 5]]
如评论中所述，可能的要求是所有单元格都需要着色。这将需要更复杂的方法。这是此类配置的示例，上面的代码可以创建一个连接所有端点而不接触所有单元格的解决方案：
board = [[0, 1, 2, 0, 0, 0, 0],
[1, 3, 4, 0, 3, 5, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 2, 0, 4, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 5, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]]
我尝试使用 google-OR 工具为流程游戏制作求解器。
我为角落制定了一些规则，只包含角落管道，但除此之外，我不知道如何让管道相互连接，也不知道如何告诉模型制作一个管道相互连接。
一些片段
pipe_types = {
0: " ",
1: "-",
2: "|",
3: "┗" ,
4: "┛" ,
5: "┓",
6: "┏",
7: "●"
}
model = cp_model.CpModel()
filled_map = [[0,0,0,0],
[0,0,7,0],
[0,0,0,0],
[0,7,0,0]]
mesh_size = int(np.sqrt(len(np.array(filled_map).flatten())))
target_map = [[model.NewIntVar(1, 6, 'column: %i' % i) for i in range(mesh_size)] for j in range(mesh_size)]
flow_map = init_map(model, target_map, filled_map)
for i in range(len(flow_map)):
for j in range(len(flow_map[0])):
# check if top or bottom side
if (i == 0) or (i == len(flow_map)-1):
model.Add(flow_map[i][j] != 2)
# check if left or right side
if (j == 0) or (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 1)
# left up corner
if (i == 0) & (j == 0):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 5)
# right up corner
if (i == 0) & (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 6)
# left bottom corner
if (i == len(flow_map)-1) & (j == 0):
model.Add(flow_map[i][j] != 4)
model.Add(flow_map[i][j] != 5)
model.Add(flow_map[i][j] != 6)
# right bottom corner
if (i == len(flow_map)-1) & (j == len(flow_map[0])-1):
model.Add(flow_map[i][j] != 3)
model.Add(flow_map[i][j] != 5)
model.Add(flow_map[i][j] != 6)
# Solving
status = solver.Solve(model)
res = []
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
for i in range(len(flow_map)):
for j in range(len(flow_map[0])):
res.append(solver.Value(flow_map[i][j]))
print(solver.Value(flow_map[i][j]), end=" ")
print()
这会导致网格中心出现水平管道。稍后，我还得弄清楚如何在上面添加颜色等等。
是否有关于如何在 OR 工具上进行此操作的指示？
编辑 1：
根据 David Eisenstat 的回答，我可以找到解决方案。根据 JohanC 的回答可视化这个解决方案，我得到了这个结果。
我可以从 google-OR 工具中获取路径吗？
编辑 2：
使用来自
但感觉很奇怪，因为OR工具已经计算出路径了，我必须重新计算路径。从
最好的方法可能是 AddCircuit。此约束采用有向图，其中每条弧都标有文字，并要求标记为 true 的弧形成一个子图，其中每个节点的入度和出度均为 1，并且最多有一个循环不是自身-环形。通过强制从尾到头的弧，我们可以使用这种约束类型来要求从头到尾只有一条路径。
文档有点少，所以这里有一个工作代码示例。画图的部分就交给你了
import collections
from ortools.sat.python import cp_model
def validate_board_and_count_colors(board):
assert isinstance(board, list)
assert all(isinstance(row, list) for row in board)
assert len(set(map(len, board))) == 1
colors = collections.Counter(square for row in board for square in row)
del colors[0]
assert all(count == 2 for count in colors.values())
num_colors = len(colors)
assert set(colors.keys()) == set(range(1, num_colors + 1))
return num_colors
def main(board):
num_colors = validate_board_and_count_colors(board)
model = cp_model.CpModel()
solution = [
[square or model.NewIntVar(1, num_colors, "") for (j, square) in enumerate(row)]
for (i, row) in enumerate(board)
]
true = model.NewBoolVar("")
model.AddBoolOr([true])
for color in range(1, num_colors + 1):
endpoints = []
arcs = []
for i, row in enumerate(board):
for j, square in enumerate(row):
if square == color:
endpoints.append((i, j))
else:
arcs.append(((i, j), (i, j)))
if i < len(board) - 1:
arcs.append(((i, j), (i + 1, j)))
if j < len(row) - 1:
arcs.append(((i, j), (i, j + 1)))
(i1, j1), (i2, j2) = endpoints
k1 = i1 * len(row) + j1
k2 = i2 * len(row) + j2
arc_variables = [(k2, k1, true)]
for (i1, j1), (i2, j2) in arcs:
k1 = i1 * len(row) + j1
k2 = i2 * len(row) + j2
edge = model.NewBoolVar("")
if k1 == k2:
model.Add(solution[i1][j1] != color).OnlyEnforceIf(edge)
arc_variables.append((k1, k1, edge))
else:
model.Add(solution[i1][j1] == color).OnlyEnforceIf(edge)
model.Add(solution[i2][j2] == color).OnlyEnforceIf(edge)
forward = model.NewBoolVar("")
backward = model.NewBoolVar("")
model.AddBoolOr([edge, forward.Not()])
model.AddBoolOr([edge, backward.Not()])
model.AddBoolOr([edge.Not(), forward, backward])
model.AddBoolOr([forward.Not(), backward.Not()])
arc_variables.append((k1, k2, forward))
arc_variables.append((k2, k1, backward))
model.AddCircuit(arc_variables)
solver = cp_model.CpSolver()
status = solver.Solve(model)
if status == cp_model.OPTIMAL:
for row in solution:
print("".join(str(solver.Value(x)) for x in row))
if __name__ == "__main__":
main(
[
[1, 0, 0, 2, 3],
[0, 0, 0, 4, 0],
[0, 0, 4, 0, 0],
[0, 2, 3, 0, 5],
[0, 1, 5, 0, 0],
]
)
由于我没有使用 OR 工具的经验，这里有一个 Z3 的方法。
- 初始棋盘由端点数字表示，每种颜色一个数字。思路有点类似于how Sudoku is represented.
- 棋盘上的每个其他单元格将获得一个零值或一个数字。这个数字应该恰好等于它的两个邻居。
- 初始端点应恰好有一个具有其颜色的邻居。
from z3 import Solver, Sum, Int, If, And, Or, sat
def plot_solution(S):
import matplotlib.pyplot as plt
ax = plt.gca()
colors = plt.cm.tab10.colors
for i in range(M):
for j in range(N):
if board[i][j] != 0:
ax.scatter(j, i, s=500, color=colors[board[i][j]])
if S[i][j] != 0:
for k in range(M):
for l in range(N):
if abs(k - i) + abs(l - j) == 1 and S[i][j] == S[k][l]:
ax.plot([j, l], [i, k], color=colors[S[i][j]], lw=15)
ax.set_ylim(M - 0.5, -0.5)
ax.set_xlim(-0.5, N - 0.5)
ax.set_aspect('equal')
ax.set_facecolor('black')
ax.set_yticks([i + 0.5 for i in range(M - 1)], minor=True)
ax.set_xticks([j + 0.5 for j in range(N - 1)], minor=True)
ax.grid(b=True, which='minor', color='white')
ax.set_xticks([])
ax.set_yticks([])
ax.tick_params(axis='both', which='both', length=0)
plt.show()
board = [[1, 0, 0, 2, 3],
[0, 0, 0, 4, 0],
[0, 0, 4, 0, 0],
[0, 2, 3, 0, 5],
[0, 1, 5, 0, 0]]
M = len(board)
N = len(board[0])
B = [[Int(f'B_{i}_{j}') for j in range(N)] for i in range(M)]
s = Solver()
s.add(([If(board[i][j] != 0, B[i][j] == board[i][j], And(B[i][j] >= 0, B[i][j] < 10))
for j in range(N) for i in range(M)]))
for i in range(M):
for j in range(N):
same_neighs_ij = Sum([If(B[i][j] == B[k][l], 1, 0)
for k in range(M) for l in range(N) if abs(k - i) + abs(l - j) == 1])
if board[i][j] != 0:
s.add(same_neighs_ij == 1)
else:
s.add(Or(same_neighs_ij == 2, B[i][j] == 0))
if s.check() == sat:
m = s.model()
S = [[m[B[i][j]].as_long() for j in range(N)] for i in range(M)]
print(S)
plot_solution(S)
解决方案：
[[1, 2, 2, 2, 3],
[1, 2, 4, 4, 3],
[1, 2, 4, 3, 3],
[1, 2, 3, 3, 5],
[1, 1, 5, 5, 5]]
如评论中所述，可能的要求是所有单元格都需要着色。这将需要更复杂的方法。这是此类配置的示例，上面的代码可以创建一个连接所有端点而不接触所有单元格的解决方案：
board = [[0, 1, 2, 0, 0, 0, 0],
[1, 3, 4, 0, 3, 5, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 2, 0, 4, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 5, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0]]