解决数独谜题
这个例子演示了如何使用混合整数线性规划（MILP）和约束规划（CP）的方法找到数独谜题的解决方案。
我们将使用[面向问题的优化]工作流程解决此问题（https://engee.com/community/catalogs/projects/algoritm-resheniia-zadach-optimizatsii )。
在这个例子中，我们将使用[跳转的函数。jl]图书馆(https://engee.com/helpcenter/stable/ru/julia/JuMP/index.html ）使用线性优化库[HiGHS.jl]来制定优化问题（https://github.com/jump-dev/HiGHS.jl ），随机数生成库[Random.jl]（https://engee.com/helpcenter/stable/ru/julia/stdlib/Random.html ）和[情节。jl]图书馆(https://engee.com/helpcenter/stable/ru/julia/juliaplots/index.html ）来可视化结果。
安装库
如果您的环境中未安装最新版本的软件包 JuMP，取消注释并运行下面的单元格:
Pkg.add(["JuMP", "HiGHS"])
任务说明
数独是一个逻辑组合数字放置难题. 目标是用数字填充9x9网格，以便每列，每行和九个3x3子网格中的每一个都包含从1到9的所有数字。
规则:
- 每行必须包含从1到9的数字，不重复。
- 每列必须包含从1到9的数字，不重复。
- 每个3x3子网必须包含从1到9的数字，而不重复。
为了解决难题，提供了最初的提示。:
.png)
一个解决的数独的例子:
.png)
数独谜题的范围从简单到非常困难，难度通常取决于提供的初始线索的数量以及解决它们所需的策略的复杂性。 一个精心设计的数独谜题应该只有一个解决方案。
连接图书馆
连接库 JuMP:
using JuMP;
连接求解器库 HiGHS:
using HiGHS;
连接图表库 Plots:
using Plots;
连接随机数生成库 Random:
using Random;
创建数独可视化功能
创建函数 plot_sudoku()，可视化数独:
function plot_sudoku(grid)
p = plot(aspect_ratio=:equal, legend=false, axis=false, ticks=false)
for i in 0:9
plot!(p, [i, i], [0, 9], color=:black, linewidth=(i % 3 == 0 ? 2 : 1))
plot!(p, [0, 9], [i, i], color=:black, linewidth=(i % 3 == 0 ? 2 : 1))
end
for i in 1:9, j in 1:9
if grid[i,j] != 0
annotate!(p, j-0.5, 9.5-i, text(string(grid[i,j]), 14))
end
end
return p
end
在这个例子中，我们将使用这个函数来可视化数独。
数独益智一代
在本节中，我们将编写一个程序，将生成数独谜题来解决。
创建函数 generate_full_grid() 负责构建数独网格:
function generate_full_grid()
grid = zeros(Int, 9, 9)
fill_grid!(grid, 1)
return grid
end
创建递归函数 fill_grid!() 用数字填充数独网格:
function fill_grid!(grid, pos)
if pos > 81
return true
end
row, col = divrem(pos - 1, 9) .+ 1
nums = shuffle(1:9)
for num in nums
if is_valid(grid, row, col, num)
grid[row, col] = num
if fill_grid!(grid, pos + 1)
return true
end
grid[row, col] = 0
end
end
return false
end
这个函数实现了一个回溯算法，用有效的数字填充数独网格。
创建函数 is_valid()，检查给定数字的放置是否可接受（num）在数独网格的特定单元格（行，列）中:
function is_valid(grid, row, col, num)
for i in 1:9
if grid[row, i] == num || grid[i, col] == num
return false
end
end
box_row, box_col = 3 * ((row - 1) ÷ 3) + 1, 3 * ((col - 1) ÷ 3) + 1
for i in 0:2, j in 0:2
if grid[box_row + i, box_col + j] == num
return false
end
end
return true
end
此功能对于在完成数独网格的过程中遵循所有三个规则至关重要。
创建函数 remove_numbers!() 负责从填充的数独网格中删除数字以创建一个谜题:
function remove_numbers!(grid, num_to_remove)
positions = [(i, j) for i in 1:9 for j in 1:9]
shuffle!(positions)
for _ in 1:num_to_remove
for (row, col) in positions
if grid[row, col] != 0
temp = grid[row, col]
grid[row, col] = 0
solution_count = count_solutions(grid)
if solution_count != 1
grid[row, col] = temp
else
break
end
end
end
end
end
这是创建不同难度级别的数独谜题的关键部分，因为移除的单元格数量会影响谜题的难度。
创建递归函数 count_solutions()，它计算给定数独网格的有效解的数量:
function count_solutions(grid, limit=2)
empty_cell = findfirst(iszero, grid)
if empty_cell === nothing
return 1
end
row, col = Tuple(empty_cell)
count = 0
for num in 1:9
if is_valid(grid, row, col, num)
grid[row, col] = num
count += count_solutions(grid, limit - count)
grid[row, col] = 0
if count >= limit
return count
end
end
end
return count
end
此函数对于确保从网格中删除数字至关重要（在函数中 remove_numbers!）没有导致多个解决方案。
创建函数 generate_sudoku_puzzle()，它生成一个具有一定数量提示的数独:
function generate_sudoku_puzzle(num_clues)
full_grid = generate_full_grid()
num_to_remove = 81 - num_clues
remove_numbers!(full_grid, num_to_remove)
return full_grid
end
单解数独谜题的理论最小提示数为17。
我们编写的程序可以用一个解决方案稳定地生成数独，其中提示的最小数量在20到30之间，这对于这个例子来说已经足够了。
用25个提示生成数独:
sudoku_puzzle = generate_sudoku_puzzle(25);
用提示可视化数独:
plot_sudoku(sudoku_puzzle)
混合整数线性规划问题的公式化
让我们使用混合整数线性规划来解决这个问题。 目标是将难题建模为可行性问题，其中每个单元必须满足某些约束。
使用函数创建优化任务 Model() 并在括号中指定求解器的名称。:
sudoku_milp = Model(HiGHS.Optimizer)
创建变量 x，这是一个三维数组 ，在哪里 i, j 和 k 在1到9的范围内。 论点 Bin 表示变量 x 它是二进制的。
@variable(sudoku_milp, x[i = 1:9, j = 1:9, k = 1:9], Bin);
阵列 x 由:
i（行索引）：表示数独网格中从1到9范围内的行号j（列索引）：表示数独网格中的列号，也在1到9的范围内k（数字索引）：表示可以放置在单元格中的潜在数字（从1到9）（i,j)
所以二进制表示是 x 意思是:
-
-数字8放置在位于第3行第3列的单元格中
-
=0-数字8不放在此单元格中。
使用循环 for 遍历各行 i 和列 j 为优化问题创建以下条件:
此条件可确保数独网格中的每个单元格都包含从1到9的一个数字。
for i in 1:9
for j in 1:9
@constraint(sudoku_milp, sum(x[i, j, k] for k in 1:9) == 1)
end
end
使用循环 for 遍历各行 i 和列 j，为优化任务创建以下条件:
此约束确保每个数字 k 在每行中出现一次 ind.
此约束确保每个数字 k 在每列中只显示一次 ind.
for ind in 1:9
for k in 1:9
@constraint(sudoku_milp, sum(x[ind, j, k] for j in 1:9) == 1)
@constraint(sudoku_milp, sum(x[i, ind, k] for i in 1:9) == 1)
end
end
上游单元中的代码将约束添加到模型162:
*81行限制(9行×9位)
*81列限制(9列×9位数)
有了这两个条件，我们就满足了数独的前两条规则。:
*每行必须包含从1到9的数字，不重复。
*每列必须包含从1到9的数字，不重复。
使用循环 for 为优化问题创建以下条件:
最外层的循环 i 在1:3:7，它遍历行1、4和7，它们是每个3x3子网的起始行。
平均周期为 j 在1:3:7，它遍历列1、4和7，它们是每个3x3子网的起始列。
最里面的循环 k 在1:9，他通过所有可能的数字（从1到9）。
变量 r 和 c 允许您为数独中的每个3x3子网定义约束。
r-表示3x3子网中的行索引，并从i以前i+2c-表示3x3子网中的列索引，并从j以前j+2
for i in 1:3:7
for j in 1:3:7
for k in 1:9
@constraint(sudoku_milp, sum(x[r, c, k] for r in i:(i+2), c in j:(j+2)) == 1)
end
end
end
上游单元中的代码为模型添加了81个约束（9个子网中的每个为9位），确保每个3x3子网包含从1到9的所有位，而不会重复。 这就是我们如何实现数独谜题的第三条规则。
使用循环 for 要遍历单元格，请将值设置为1（true）在一个二进制变量 x 在初始提示所在的单元格中（sudoku_puzzle），使用函数 fix():
for i in 1:9
for j in 1:9
if sudoku_puzzle[i, j] != 0
fix(x[i, j, sudoku_puzzle[i, j]], 1; force = true)
end
end
end
您已经为完成所有三个解决难题的规则创造了条件，并为变量添加了提示 x. 现在您可以解决优化问题。:
optimize!(sudoku_milp)
显示求解器结果的状态:
game_status = termination_status(sudoku_milp)
println("Статус: ", game_status)
if game_status == MOI.OPTIMAL || game_status == MOI.FEASIBLE_POINT
println("Оптимальное решение найдено")
else
println("Оптимальное решение не найдено")
end
OPTIMAL状态表示求解器已找到问题的全局最优解。
保存二进制变量的值 x 在变量中 x_val:
x_val = value.(x)
您可以确保每个值 k 从解中，网格中的一个位置被分配给一个变量 x_val.
创建一个新的9x9矩阵填充零，这将用于将结果从二进制格式转换为标准的数独网格格式。 论点 Int 表示矩阵的值为整数。
sol_milp = zeros(Int, 9, 9);
使用循环 for 要遍历数独网格中的所有单元格和可能的数字，请转换三维数组的值 x_val 成一个二维整数数组 sol_milp.
sol_milp = zeros(Int, 9, 9)
for i in 1:9
for j in 1:9
for k in 1:9
if round(Int, x_val[i, j, k]) == 1
sol_milp[i, j] = k
end
end
end
end
现在变量 sol_milp 它以二维整数数组的格式包含拼图的实际解决方案。
可视化结果:
plot_sudoku(sol_milp)
我们已经演示了使用混合整数线性规划问题的解决方案。 求解器查找符合制定为行、列和子网约束的数独求解规则的可能数字配置。
约束中的规划问题的制定
您还可以使用约束编程来模拟此任务。 让我们应用条件 AllDifferent()（"都是不同的"），它指出矢量的任何两个元素都不能取相同的值。
使用函数创建优化任务 Model() 并在括号中指定求解器的名称。:
sudoku_cp = Model(HiGHS.Optimizer)
创建变量 sudoku_cp，包含二维数组 . 每个变量的范围从1到9。 论点是 Int 指定变量的值为整数。
@variable(sudoku_cp , 1 <= x[1:9, 1:9] <= 9, Int);
指定适用于每行的条件 i 数独网格。 MOI.AllDifferent(9) 确保行中的所有元素都是 i 他们是不同的。
这意味着从1到9的每个数字在每行中恰好出现一次。
@constraint(sudoku_cp , [i = 1:9], x[i, :] in MOI.AllDifferent(9));
指定适用于每列的条件 j 数独网格。 MOI.AllDifferent(9) 确保列中的所有项 j 他们是不同的。
这意味着从1到9的每个数字在每列中恰好出现一次。
@constraint(sudoku_cp, [j = 1:9], x[:, j] in MOI.AllDifferent(9));
设置适用于数独中每个3x3子网的条件。 MOI.AllDifferent(9) 确保每个子网中的所有元素都不同。 这意味着从1到9的每个数字在每个3x3子网中恰好出现一次。
for i in 1:3:7, j in 1:3:7
@constraint(sudoku_cp, vec(x[i:i+2, j:j+2]) in MOI.AllDifferent(9))
end
对于每个细胞 [i, j] 将原始提示从 sudoku_puzzle 到一个变量 x 使用函数 fix:
for i in 1:9, j in 1:9
if sudoku_puzzle[i, j] != 0
fix(x[i, j], sudoku_puzzle[i, j]; force = true)
end
end
您已经为完成所有三个解决难题的规则创造了条件，并为变量添加了提示 x. 现在你可以解决优化问题。:
optimize!(sudoku_cp)
显示求解器结果的状态:
game_status = termination_status(sudoku_cp)
println("Статус: ", game_status)
if game_status == MOI.OPTIMAL || game_status == MOI.FEASIBLE_POINT
println("Оптимальное решение найдено")
else
println("Оптимальное решение не найдено")
end
OPTIMAL状态表示求解器已找到问题的全局最优解。
将结果保存在变量中。 收到的值的类型 Float64. 您可以使用该功能 round 随着争论 Int 将值转换为整数。
sol_cp = round.(Int, value.(x));
可视化生成的数独解决方案:
plot_sudoku(sol_cp)
您可以比较通过使用混合整数线性规划和通过在约束中编程获得的解决方案。:
sol_milp == sol_cp
这两种解决难题的方法的结果是相同的。
结论
在这个例子中，我们使用两种不同的方法解决了数独难题—混合整数线性规划（MILP）和约束规划（CP）。 这两种方法都可以解决难题，但它们以根本不同的方式制定和解决问题，在建模和解决问题方面表现出不同的特征。 作为本示例中演示的问题解决方案的一部分，我们可以确定这些方法之间的一些差异。
混合整数线性规划:
*使用二进制变量
@变量（sudoku_milp，x[i=1：9，j=1：9，k=1：9]，Bin）
*使用线性约束来强制执行数独规则
@constraint(sudoku_milp,sum(x[i,j,k]for k in1:9)==1)
一个更大的模型，具有更多的变量，但具有更简单的约束
*它通常对小型模型更改更具弹性，并且随着任务大小的增加而更好地扩展
约束编程:
*使用整数变量
@变量(sudoku_cp,1<=x[1:9, 1:9] <= 9, Int）
*使用全局约束，例如 AllDifferent，执行数独规则
@constraint(sudoku_cp,[i=1:9],X[i,:]in MOI.所有不同(9))
*一个较小的模型，具有较少的变量，但具有更复杂的约束
*可能对任务的大小和结构更敏感。
在实践中，混合整数线性规划和约束规划之间的选择通常取决于任务的特定特性，并且对于某些任务，一种方法比另一种方法更适合。 在某些情况下，结合两种方法的混合方法可能是有效的。