約束規劃3-字元謎題和N皇后問題
3.3.約束規劃3-字元謎題和N皇后問題
- 1. 字元謎題
- 2. N皇后問題
- 3. 後話
- 4. 參考
1. 字元謎題
這個問題官網的原意是Cryptarithmetic Puzzles，有點像猜謎語的意思.舉個例子，下面的這個等式中，每個字母表示一個0-9的數字，那麼SP就是10-99之間的某個數，IS也是，FUN是100-999的某個數，TRUE是1000-9999之間的某個數，其中，FUN和TRUE的十位數相同；
CP
+ IS
+ FUN
--------
= TRUE
滿足這一等式的其中一個例子是：
23
+ 74
+ 968
--------
= 1065
整理下思路如下：
- 方差滿足：CP + IS + FUN = TRUE
- 所有的字母表示不同的數字
- C, I, F, T 不能是0，因為數字的首位不能是0.
接下來我們使用original-CP求解器來做這一道題。還記得步驟是什麼嗎，先定義變數，然後定義約束，之後添加目標函數，最後是求解列印結果。
# original-cp
from ortools.constraint_solver import pywrapcp
from os import abort
def CPIsFun():
# 定義求解器
solver = pywrapcp.Solver(cp-example)
kBase = 10
# 定義整數變數
digits = list(range(0, kBase))
digits_without_zero = list(range(1, kBase))
c = solver.IntVar(digits_without_zero, C)
p = solver.IntVar(digits, P)
i = solver.IntVar(digits_without_zero, I)
s = solver.IntVar(digits, S)
f = solver.IntVar(digits_without_zero, F)
u = solver.IntVar(digits, U)
n = solver.IntVar(digits, N)
t = solver.IntVar(digits_without_zero, T)
r = solver.IntVar(digits, R)
e = solver.IntVar(digits, E)
# We need to group variables in a list to use the constraint AllDifferent.
# 將所有變數放到一個list中，這其實是original-cp的要求
letters = [c, p, i, s, f, u, n, t, r, e]
# 添加約束，每個字母表示不同的數字
solver.Add(solver.AllDifferent(letters))
# 添加約束：CP + IS + FUN = TRUE
solver.Add(p + s + n + kBase * (c + i + u) + kBase * kBase * f ==
e + kBase * u + kBase * kBase * r + kBase * kBase * kBase * t)
# 創建Phase方法
# 並求解
db = solver.Phase(letters, solver.INT_VAR_DEFAULT,
solver.INT_VALUE_DEFAULT)
solver.NewSearch(db)
# 查看有多少組合是滿足要求的
while solver.NextSolution():
print(letters)
# Is CP + IS + FUN = TRUE?
assert (kBase * c.Value() + p.Value() + kBase * i.Value() + s.Value() +
kBase * kBase * f.Value() + kBase * u.Value() + n.Value() ==
kBase * kBase * kBase * t.Value() + kBase * kBase * r.Value() +
kBase * u.Value() + e.Value())
solver.EndSearch()
return
if __name__ == __main__:
CPIsFun()
# 結果如下：
[C(2), P(3), I(7), S(4), F(9), U(6), N(8), T(1), R(0), E(5)]
[C(2), P(3), I(7), S(5), F(9), U(4), N(8), T(1), R(0), E(6)]
[C(2), P(3), I(7), S(5), F(9), U(8), N(6), T(1), R(0), E(4)]
[C(2), P(3), I(7), S(6), F(9), U(8), N(5), T(1), R(0), E(4)]
……
……
2. N皇后問題
N皇后問題理解起來很簡單，在一個棋盤上，一個皇后在某個格子上，那麼這個格子的橫線、豎線、對角線上都不能有其他皇后。N皇后問題是一個很經典的編程題目，相關思路到網上搜索下。
這次我們使用CP-SAT求解器來。
import sys
from ortools.sat.python import cp_model
def main(board_size):
model = cp_model.CpModel()
# Creates the variables.
# The array index is the column, and the value is the row.
# 第一步，當然是創建變數
# queens 數組的 下標表示棋盤的列，值表示行
# 即 queens_i=j 表示第j行第i列 上有一個皇后
queens = [model.NewIntVar(0, board_size - 1, x%i % i)
for i in range(board_size)]
# Creates the constraints.
# The following sets the constraint that all queens are in different rows.
# 下面的約束表示所有的皇后在不同的行上面，即queens的值都不相同
model.AddAllDifferent(queens)
# Note: all queens must be in different columns because the indices of queens are all different.
# The following sets the constraint that no two queens can be on the same diagonal.
# 下面的約束是 對角線上不能有2個皇后
# 邏輯有點繞
for i in range(board_size):
# Note: is not used in the inner loop.
diag1 = []
diag2 = []
for j in range(board_size):
# Create variable array for queens(j) + j.
q1 = model.NewIntVar(0, 2 * board_size, diag1_%i % i)
diag1.append(q1)
model.Add(q1 == queens[j] + j)
# Create variable array for queens(j) - j.
q2 = model.NewIntVar(-board_size, board_size, diag2_%i % i)
diag2.append(q2)
model.Add(q2 == queens[j] - j)
model.AddAllDifferent(diag1)
model.AddAllDifferent(diag2)
### Solve model.
# 最後就是求解約束方程
solver = cp_model.CpSolver()
solution_printer = SolutionPrinter(queens)
status = solver.SearchForAllSolutions(model, solution_printer)
print()
print(Solutions found : %i % solution_printer.SolutionCount())
class SolutionPrinter(cp_model.CpSolverSolutionCallback):
"""列印中間結果"""
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
print(%s = %i % (v, self.Value(v)), end= )
print()
def SolutionCount(self):
return self.__solution_count
class DiagramPrinter(cp_model.CpSolverSolutionCallback):
def __init__(self, variables):
cp_model.CpSolverSolutionCallback.__init__(self)
self.__variables = variables
self.__solution_count = 0
def OnSolutionCallback(self):
self.__solution_count += 1
for v in self.__variables:
queen_col = int(self.Value(v))
board_size = len(self.__variables)
# Print row with queen.
for j in range(board_size):
if j == queen_col:
# There is a queen in column j, row i.
print("Q", end=" ")
else:
print("_", end=" ")
print()
print()
def SolutionCount(self):
return self.__solution_count
if __name__ == __main__:
# By default, solve the 8x8 problem.
board_size = 8
if len(sys.argv) > 1:
board_size = int(sys.argv[1])
main(board_size)
# 結果如下：
x0 = 0 x1 = 6 x2 = 4 x3 = 7 x4 = 1 x5 = 3 x6 = 5 x7 = 2
x0 = 0 x1 = 6 x2 = 3 x3 = 5 x4 = 7 x5 = 1 x6 = 4 x7 = 2
x0 = 0 x1 = 4 x2 = 7 x3 = 5 x4 = 2 x5 = 6 x6 = 1 x7 = 3
x0 = 0 x1 = 5 x2 = 7 x3 = 2 x4 = 6 x5 = 3 x6 = 1 x7 = 4
……
……
# 其中的一個棋盤入局如下：
Q _ _ _ _ _ _ _
_ _ _ _ _ _ Q _
_ _ _ _ Q _ _ _
_ _ _ _ _ _ _ Q
_ Q _ _ _ _ _ _
_ _ _ Q _ _ _ _
_ _ _ _ _ Q _ _
_ _ Q _ _ _ _ _
3. 後話
ortools的約束規劃就到這裡了，官方給的例子也比較簡單，在實際業務中肯定是比較複雜的，比如電力調度，可能涉及到幾千幾萬的變數和約束，此時看來ortools就不是那麼好用了，可能商業求解器比如gurobi或者cplex等會好用些。
更多問題，還需要大家多實驗實驗才知道。下一篇文章我們將開始整數規劃問題，整數規劃是在約束規劃的基礎上，增加全部或者部分變數是整數的情況，增加了約束情況就比較複雜了。
4. 參考
- 八皇后問題
- ortools-Original-CP-Solver
大家看完記得關注點贊.
推薦閱讀：
