0-1 计划和解决数独问题
最编程
2024-06-01 19:45:33
...
背景音乐:虚拟 - 陈粒
背景
本人一直以来比较喜欢数独,水平自认为还可以,
常用的app是Sodoku Joy,最难的Maelstrom模式也能在半小时内完成。
最近因工作需要,在看运筹优化方面的内容,
突然想到数独问题也可以用0-1规划求解,非常简单!
虽然变量和约束条件会变得很多,不过这都不是事儿。
Google一下,发现Python有个线性规划模块(Pulp)正好也提供了这方面的示例。
于是,简单地做个整理。
建模思路
- 每个单元格有9种可能取值,每种取值要么为1(被选中)要么为0(不被选中),标准的数独是9*9的网格结构,因此构造9*9*9=729个0-1变量。
- 目标函数:由于数独问题只要靠约束条件即可求解,因此目标函数可设为常数0。
- 约束条件:
1)每个单元格里,只能有一种取值被选中。
2)每行不能有重复数字;
3)每列不能有重复数字;
4)每个3*3小方格不能有重复数字;
案例
拿以前新闻里说的“最难数独”为例:
Python实现
- 首先创建一个记录了初始值的字典
# 有些单元格上已有指定的数值
init_choices = {
("1", "1"): "5",
("2", "1"): "6",
("4", "1"): "8",
("5", "1"): "4",
("6", "1"): "7",
("1", "2"): "3",
("3", "2"): "9",
("7", "2"): "6",
("3", "3"): "8",
("2", "4"): "1",
("5", "4"): "8",
("8", "4"): "4",
("1", "5"): "7",
("2", "5"): "9",
("4", "5"): "6",
("6", "5"): "2",
("8", "5"): "1",
("9", "5"): "8",
("2", "6"): "5",
("5", "6"): "3",
("8", "6"): "9",
("7", "7"): "2",
("3", "8"): "6",
("7", "8"): "8",
("9", "8"): "7",
("4", "9"): "3",
("5", "9"): "1",
("6", "9"): "6",
("8", "9"): "5",
}
- 然后创建数独所需的若干常量
# 创建一个列表,包含了所有出现的数值
Sequence = ["1", "2", "3", "4", "5", "6", "7", "8", "9"]
# 单元格的可能取值
Vals = Sequence
# 行列的索引
Rows = Sequence
Cols = Sequence
# 创建一个boxes列表,记录每个3*3小方格里的,各单元格的行列索引
Boxes =[]
for i in range(3):
for j in range(3):
Boxes += [[(Rows[3*i+k], Cols[3*j+l]) for k in range(3) for l in range(3)]]
- 建模
import pulp
# 创建0-1变量字典,表征指定单元格内的指定数值是否被选中
choices = pulp.LpVariable.dicts("Choice", (Vals, Rows, Cols), 0, 1, pulp.LpInteger)
# 创建模型
prob = pulp.LpProblem("Sudoku Problem", pulp.LpMinimize)
# 定义目标函数:由于数独问题只要满足所有约束条件即可求出解,所以目标函数随便指定为0
prob += 0, "Arbitrary Objective Function"
# 约束条件1:在一个单元格里,只能由一个数值被选中
for r in Rows:
for c in Cols:
prob += pulp.lpSum([choices[v][r][c] for v in Vals]) == 1, ""
# 约束条件2:对于一个数值,只能在一行/一列/一个box里,出现一次
for v in Vals:
for r in Rows:
prob += pulp.lpSum([choices[v][r][c] for c in Cols]) == 1, ""
for c in Cols:
prob += pulp.lpSum([choices[v][r][c] for r in Rows]) == 1, ""
for b in Boxes:
prob += pulp.lpSum([choices[v][r][c] for (r,c) in b]) == 1, ""
# 约束条件3:由于有些单元格上已有指定的数值,因此让它们的0-1变量取值恒为1
for (r, c), v in init_choices.items():
prob += choices[v][r][c] == 1,""
- 模型求解
这里需要说明的是,如果问题出的不好,数独就可能存在多解。
因此下面用while来循环求解:
1)每次求得一个新的解,会加上一个新的约束条件,从而保证相同的解不会再出现。
2)直到pulp.LpStatus[prob.status]不为Optimal,那么说明已经无解了,break。
这里用termcolor的colored函数,来print不同颜色,区分是否为初始值。
from termcolor import colored
while True:
# 模型循环求解
prob.solve()
# 打印当前的状态,并判断是否有解
print("Status:", pulp.LpStatus[prob.status])
if pulp.LpStatus[prob.status] == "Optimal":
# 逐行打印结果
for r in Rows:
# 若当前为第1、4、7行,先打印分隔符
if r == "1" or r == "4" or r == "7":
print("+-------+-------+-------+")
# 记录当前行的字符内容
s = ''
for c in Cols:
for v in Vals:
# 如果该单元格的数值被选中,则打印
if pulp.value(choices[v][r][c]) == 1:
# 若当前为第1、4、7列,先打印分隔符
if c == "1" or c == "4" or c =="7":
s += "| "
# 按照是否为初始值,打印不同的颜色
if init_choices.get((r, c)) == v:
s += (colored(v, 'white', 'on_magenta') + " ")
else:
s += (v + " ")
s += "|"
print(s)
print("+-------+-------+-------+")
# 添加新的约束,保证不会返回相同的解
prob += pulp.lpSum([choices[v][r][c] for v in Vals
for r in Rows
for c in Cols
if pulp.value(choices[v][r][c]) == 1]) <= 80
# 如果不能找到新的解,则结束程序
else:
break
-
结果
简书里设置颜色很麻烦,直接截图吧:
感兴趣的话,也可以试试注释掉一个初始解,就会返回多个可行解了。
速度测试
将上述内容封装到sudoku_problem函数中,运行
%timeit sudoku_problem(init_choices)
返回结果
655 ms ± 13.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
求解数独的时间在0.655秒左右,非常好~
后续可行的计划
- 找个随机生成数独游戏的方法,完成“发现问题-解决问题”的闭环。
- 简单地做个UX设计,用于交互。
- 基于Django或Flask做个web端的界面,可以方便地在上面玩数独。
- 加入图像识别模块,这样就可以识别截图的数独问题并求解了。
上一篇: 构建和验证 docker 私有镜像仓库
下一篇: 用 Python 实现数独解题程序代码
推荐阅读
-
Java 使用定时任务 - 前言:Java 开发过程中经常会遇到使用定时任务的情况,如在某个活动结束时自动生成获奖者名单、导出 excel 等。常见的有以下四种方式:Timer、ScheduledExecutorService、SpringTask、Quartz。 实现 Java 定时任务的四种方法 (1) JDK 自带定时器实现 (2) Spring Task @Scheduled 注解任务调度 (3) Quartz 定时器实现 (4) Elastic-job 分布式任务调度框架 JDK 自带 .NET Framework 2.0JDK 自带 Timer 和 JDK1.5 + 新 ScheduledExecutorService; Spring3.0自带的任务调度工具:它可以看做是一个轻量级的Quartz,而且使用起来比Quartz简单得多,一般可以直接用@Scheduled+corn表达式来注解实现; Quartz:简单但功能强大的 JAVA 作业调度框架; Elastic-job分布式作业调度框架:是当当网架构师基于Zookepper、Quartz开发并开源的一个Java分布式定时任务,解决了Quartz不支持分布式的缺点。 JDK自带的java.util. JDK 自带的 java.util.Import 是 JDK 的一部分。 java.util.import import java.util. import java.util. public class Test { /** * 第一个方法:设置在指定时间执行指定任务,只执行一次 * schedule(TimerTask task, Date time) */ public static void timer1 { Timer timer = new Timer; timer.schedule(new Timer) timer.schedule(new 定时任务) public void run { System.out.println(new Date + "\t "+"--specify the task to be run---"); } }, new Date(System.currentTimeMillis + 2000)); } } } /** * 第二个方法:设置指定任务在延迟后执行,只执行一次 * schedule(TimerTask task, long delay) * 延迟单位毫秒 */ public static void timer2{ Timer timer = new Timer; timer.schedule(new Timer) timer.schedule(new 定时任务) public void run { system.out.println(new Date + "\t "+"--specify the task to be run---"); } }, 2000); } /** * 第三个方法:设置指定的任务在指定的延迟时间后周期性执行,周期时间为 period * schedule(TimerTask task, long delay, long period) * scheduleAtFixedRate(TimerTask task, long delay, long period) * 延迟,周期以毫秒为单位 */ public static void timer3 { Timer timer = new Timer; timer.schedule(new Timer) timer.schedule(new 定时任务) public void run { system.out.println(new Date + "\t "+"--specify the task to be run---"); } }, 1000, 1000); } /** * 第四种方法:设置指定任务 task 在指定时间 firstTime 开始重复循环执行,循环时间为周期 * schedule(TimerTask task, Date firstTime, long period) * scheduleAtFixedRate(TimerTask task, Date firstTime, long period) * 以毫秒为单位的周期 */ public static void timer4 { Calendar calendar = Calendar.getInstance; calendar.set(Calendar.HOTIME) */ calendar.set(Calendar.HOUR_OF_DAY, 12); // 控制时间 calendar.set(Calendar.MINUTE, 0); // 控制分钟数 calendar.set(Calendar.SECOND, 0); // 控制秒数 Date time = calendar.getTime; // 推导出执行任务的时间,本例中为今天 12:00:00。 Timer timer = new Timer; timer.schedule(new Timer) timer.schedule(new 定时任务) public void run { System.out.println(new Date +"\t "+"--- 指定要执行的任务 ---"); } }, time, 1000); } /** * schedule 方法和 scheduleAtFixedRate 方法的区别: * (1) schedule 方法:如果第一次执行时间延迟,则根据上次实际执行完成时间点计算后续执行时间,即:下一次执行时间点 = 上次程序执行完成时间点 + 间隔时间 * (2) scheduleAtFixedRate 方法:如果第一次执行时间延迟,则根据上次开始时间点计算后续执行时间,即:下次执行时间点=上次程序执行时间点+间隔时间,*且前一个任务的执行时间延迟,则根据上次实际执行完成时间点计算后续执行时间,即:下次执行时间点=上次程序执行完成时间点+间隔时间。 *而上一个任务的执行时间大于间隔时间,就会与当前任务重叠,TimerTask 在执行时需要考虑线程同步的问题 */ } 计时器的缺陷:
-
Prolog Learning:数独和八皇后问题
-
解决数独问题的 Matlab 程序
-
0-1 计划和解决数独问题
-
Matlab_回溯法解决数独问题
-
回溯 + 约束编程 - LeetCode51(N 个皇后问题与解决数独问题的对比)
-
MATLAB 解决线性规划(含整数规划和 0-1 规划)问题 [简单易懂]
-
MATLAB 解决线性规划(包括整数规划和 0-1 规划)问题
-
MATLAB 解决线性规划(包括整数规划和 0-1 规划)问题
-
MATLAB 解决线性规划(包括整数规划和 0-1 规划)问题 [易于理解] - [x,fval,exitflag]= intlinprog(f,intcon,A,b,Aeq,beq,lb,ub)