当我在4个小时内撰写日语填字游戏时

我懒洋洋地浏览了Sirius同事最近列出的学童开设的课程清单 ...那么,这是什么? “使用SAT求解器搜索组合对象”? “我们制作了数独解算器,日语填字游戏等等?”

突然想到了穷举的NP问题可以相互简化,特别是对于布尔表达式的可行性搜索是可以简化的。哈勃(Habr)的一位作者在这里表达了这个想法,坦白说,对我而言,这就像魔术。

当然,作为一个完成离散数学和算法复杂性课程的人,我从理论上知道任务是可以简化的。但是通常很难做到这一点,我最好对教授和其他聪明的人信服。

但是,然后它被提供给... SCHOOLCHILDREN!在内部,锥子开始激发创造力,并说:“好吧,一旦提供学生,将它固定下来可能并不难。我不能弄清楚吗?看起来,他们保证将使用Python库,但是我一般都知道python ...”“

时间大约是晚上9点,这使我对问题复杂性的批判性眼光暗淡了……(实际上,这是4小时编程的进一步编年史)

21:02任务的第一阶段-我正在尝试在Python中安装该库。根据神经网络的经验,我已经知道,实际上,代码有时比配置数据包花费的时间更少。

使用经典的pip install pycosat不会安装,因此会产生错误,要求Microsoft Visual C ++ 14.0

我们一直在寻找问题的根源,然后转到Stackoverflow,在这里找到了所需的Visual C ++ 2015 Build Tools的小链接,显然包括C ++编译器。

下载,尝试安装...哇,它需要4 GB!我实际上只需要一个编译器,但是哦。

在下载并安装该程序时,我们将遵循Sirius发布的程序中的链接...是的,不是很多-Python项目的示例,但列出了本课程可能的任务。没有演示文稿,也没有视频,无法快速了解如何使用图书馆。

好的,让我们开始分析示例。我们转到queens_pycosat.py ...哇,一路走来,这是解决将皇后放在棋盘上这一常见问题的解决方案(任务是安排8个皇后,使他们彼此之间不打架)。

21:10-21:30我们了解并尝试开始。

一般逻辑开始被追踪:
SAT- () (1, 2, 3),(-1, 2 ..), (True/False).

, , .

( , ); , , 8x8 = 64 , .

(1 2 3… 8) — 1 . — [1,2,3...8]
— (9… 16) ..

— 1 !
[ 1 2] ( — ). [-1,-2],[-1,-3] .

, , . , .

( ) — (1 2… 8) ( 1 2) (...). , — .

是的,现在我想起来了,我不是那么聪明。

总的来说,我们将教学代码复制到自己身上。为了确保我们了解某些内容,请关闭对角线检查-然后该任务将变成有关车的任务。

我们开始,我们收到: 它有效!21:35稍微了解库文档之后,我们发现找到一个或所有解决方案都存在挑战。 告诉我,我亲爱的朋友,一个8x8的板上有多少辆车?你会找到一切吗? 机器思考了一段时间,然后我开始在Google析因表中搜索。 一分钟后,求解器回答-“找到了40320个解决方案。”检查-真的8 !,一切都正确。

| | | | | | | |x|
| | | | | | |x| |
| | | | | |x| | |
| | | | |x| | | |
| | | |x| | | | |
| | |x| | | | | |
| |x| | | | | | |
|x| | | | | | | |











我取消了新手不垂直碰撞的条件...但是现在多少钱了?必须为8 ^ 8 = 16777216。然后我想到他要花很长时间才能计数-我们中断了这个过程。

还找到了一种快速方法,可以在不计算所有内容的情况下从同一个库中的所有内容导出4个解决方案。完成了-找到解决方案,然后将其添加到布尔公式的异常中...

如何在python中推论几种解决方案
for cnter in range(4):
  sol = pycosat.solve(clauses)
  if isinstance(sol, list):
    print(sol)
    clauses.append([-x for x in sol]) #   -      
  else: #    - 
    return
#     ,    ,   .


总的来说,我们为“群发问题”提供了更多解决方案:21 : 45 我:总的来说,一切都清楚了,如果有的话,现在我可以将其固定。我要读一本书和水疗中心。 创意开始:嗯,您了解一切。让我们写一个简单的日语填字游戏的小填字游戏!以最简单的情况为例-在每一行和每一列上,最多只能有一位数字(因此,只有一个数字)。您只需搜索行/列的可能选项,即可在此处快速找到,然后将其加载到求解器中。我们去做吧? 我:( 没有埋伏)好吧...看来真相并不长久... 为了简单起见,我们只使用NxN个方形填字游戏-同时,您可以准备输出代码并考虑不需要水平和垂直的地方...

| | | | | | | |x|
| | | | | | |x| |
| | | | | |x| | |
| | | | |x| | | |
| | | |x| | | | |
| |x| | | | | | |
| | |x| | | | | |
|x| | | | | | | |











22:10它不起作用:(((
我们尝试使用1-0-1格式的3x3填字游戏(到目前为止,只有块是水平的,我们没有考虑垂直)。它给出了所有空单元格,感染,甚至都没有考虑填充的块...

好吧,详细我们深入研究了数据传输到求解器的格式,然后,稍微说一下,发现了意外的情况……

, «-» ?

/ /, — . , .

[1] 3 , :
[X__],[_X_],[__X]
, ,
[1,-2,-3],[-1,2,-3],[-1,-2,3]

, …
:
[1 -2 -3] [-1, 2...] [...]

, . , . — , !

伏击。实际上,有两种选择-提出KNF中填字游戏的条件,或者提出如何将DNF转换为KNF(嗯,有人应该考虑这一点,特别是因为这两个都是布尔公式!)

22:50我吃完了零食。我没有想到如何为KNF创造条件(我后来发现在文章中对它们进行了描述,但是对它们进行编程花了很长时间,而且坦率地说,它不是运动型的)。

因此,我们正在寻找DNF到CNF的转换器。对学术风格转变的形式描述散布在互联网上……为什么我需要它们?我现在绝对不会坚持下去,我会解决问题的。因此,我们看到了唯一(!)具有适当名称和功能的Python库。现在我们将连接...

23:10它的工作方式很有趣-它产生了其他变量,并通过它们将DNF带到CNF。显然,诚实地制作KNF相当困难……

因此,它也不起作用!怎么了?
我们提交DNF的测试输入:lstall = [[1,2,3]]。也就是说,我们期望只有[1,2,3](对应于整行[XXX])才是有效的解决方案,该

库给出了KNF:cnf = [[-1,-2,-3,4],[1 ,-4],[2,-4],[3,-4]]
不清楚,但很有趣。好吧,假设我相信您... ...

我们要求pycosat查找cnf的所有解决方案:
[1、2、3、4]
[1、2,-3,-4]
[1、2,-3,-4]
[1 ,-2,3,-4]
[-1,-2,-3,-4]
[-1,-2,3,-4]
[-1,2,-3,-4]
[-1, [2,3,-4]

而不是预期的一个,而是八个!该怎么办?

, , 4 True. ?

: cnf2 = [[-1, -2, -3, 4], [1, -4], [2, -4], [3, -4], [4]]
pycosat cnf2:
1: [1, 2, 3, 4]

, , ! , , .
— !

23:10她决定!这是垂直和水平方向的1-3-1填字游戏: 这是垂直和水平方向的1-0-1填字游戏的双重解决方案: 我:所以,一切对我都有效,我完成了。哇,已经是晚上11点了Spa ... 创意开始:您是否了解解决日语填字游戏的不足了?只需编写一个递归过程,该过程将产生不是针对一个块而是针对N的所有行选项。 我:嗯...应该很容易,是的... 00:00午夜时分,头部tupit烹饪得不太好,但是我继续调试递归。 日语填字游戏的用语-块之间必须至少有一个空格,但可能会有多个空格。

| |x| |
|x|x|x|
| |x| |




1
| | |x|
| | | |
|x| | |
2
|x| | |
| | | |
| | |x|












所以条件下[1,2,1] 6个单元,程序应该产生的唯一选择
[X_XX_X],
并为7个细胞已经有4个选项:
[X_XX_X_],
[X_XX__X],
[X__XX_X],
[_X_XX_X],

所有的时间我错误地计算了一个单元的位置,然后用它来计算-开始和修复比思考更容易...

00:30可以吗? 还有什么要检查的? 因此,在何处获得填字游戏的面向机器的描述...在此站点上,不,在此上-否...好的,到此为止,我都会打断笔。00:50因为它真的有效O_O 这里有一个螃蟹jcrosswords.ru/crossword/65

3x3
rows = [[1,1],[0],[1,1]]
cols = [[1,1],[0],[1,1]]

:
|X| |X|
| | | |
|X| |X|

4x4
rows = [[1,1],[0],[0],[1,1]]
cols = [[1],[1],[1],[1]]

:
1
| |X| |X|
| | | | |
| | | | |
|X| |X| |
2
|X| |X| |
| | | | |
| | | | |
| |X| |X|







由我的求解器决定。测试的最大尺寸为10x10,现在我很懒惰地在程序中插入更多填字游戏...- 我:哇,这是早上!等等,从我对SAT解算器一无所知的那一刻起,只花了4个小时?那么,到底怎么样? (关于发生了什么的简短说明...)

|x|_|x|_|_|_|_|x|_|x|
|x|x|x|_|_|_|_|x|x|x|
|_|x|_|_|_|_|_|_|x|_|
|_|x|_|x|_|_|x|_|x|_|
|_|x|x|x|x|x|x|x|x|_|
|_|_|x|x|x|x|x|x|_|_|
|x|x|x|x|x|x|x|x|x|x|
|_|_|x|x|x|x|x|x|_|_|
|x|x|_|x|x|x|x|_|x|x|
|x|_|_|_|_|_|_|_|_|x|








后记。

早晨。在Habr 上找到有关Rust的求解器文章。从填字游戏网站下载不起作用,但是转到文章中指定的Github文章后,我们在Webpbn填字游戏网站上发现了一个隐藏链接,可以以机器可读的格式导出填字游戏。选项“ Kyle Keen的Python解算器版本1的格式”适合我们,与我们的相同。

当您不需要用笔打扰填字游戏时,事情就会变得更快。很快就很清楚,求解器能够解决的最大值是30x30范围内的填字游戏。最主要的问题是各个行的变体的生成,在这些条件的堆堆的情况下,非常多,一切开始变慢:

1.首先,字符串选项需要很长时间才能生成。仅生成长度为60的字符串[2,1,3,1,4]的所有选项已经花费了大约半分钟的时间(如果有兴趣的话,只有2118760)
2.另外,DNF-> CNF转换会创建太多条件和其他变量...

但是如果没有几个块,那么即使是很大的填字游戏也可以在有意义的时间内解决。

猫-一切都很好
20x20
51511 clauses...
2851 last var number
--- 0.05186057090759277 seconds for clauses gen ---
1
| | |X|X| | | | | | | | | | | | | | | | |
| |X|X| | | | | | | | | | | | | | | | | |
| |X| | | | | | | | | | | | | | | | | | |
| |X| | | | | | | | | | | | | | | | | | |
| |X| | | | | |X|X|X| | | | | | | | | | |
|X|X| | | | |X|X|X|X|X| | | | | | | | | |
|X| | | | |X|X|X|X|X|X|X| | | |X| | | |X|
|X| | | | |X|X|X|X|X|X|X|X| | |X|X| |X|X|
|X| | | |X|X|X|X|X|X|X|X|X| | |X|X|X|X|X|
|X|X| | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
| |X| |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
| |X|X|X|X|X|X|X| |X|X|X|X|X|X|X|X|X|X|X|
| | |X|X|X|X|X| | | |X|X|X|X|X| |X|X|X| |
| | |X|X|X|X|X| | | |X|X|X|X| | | | | | |
| | | |X|X|X| | | | | |X|X|X| | | | | | |
| | | |X|X| | | | | | |X|X| | | | | | | |
| | |X|X| | | | | | | | |X| | | | | | | |
| | |X| | | | | | | | | |X| | | | | | | |
| | |X|X| | | | | | | | |X|X| | | | | | |
| | |X|X| | | | | | | | |X|X| | | | | | |
--- 0.02073383331298828 seconds for solve ---


为了测试更多的填字游戏,我迅速进行了对齐-当我们用零填充其余行时,任何填字游戏都会减少为一个正方形。是的,它不是最佳选择,但现在我不愿意重做代码...

马-30x38
22
13622799 clauses... -
350737 last var number
--- 14.18206787109375 seconds for clauses gen ---
1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | |X|X|X| | | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X| | | | |
| | | | | | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X| | | |
| | | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X|X| |X|X| | |
| | | | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X|X|X|X|X| |
| | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|
| | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X|X| |X|X|X|X|X|
| | | | | | | | | | | | | | | | | | | | | | | | |X|X|X|X|X|X|X| | | | | |X| |
| | | | | | | | | | |X|X|X|X| | | | | | | | | |X|X|X|X|X|X|X|X| | | | | | | |
| | | | | | | | |X|X|X|X|X|X|X|X|X| | | |X|X|X|X|X|X|X|X|X|X| | | | | | | | |
| | | | | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | | | |
| | | | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | | | | |
| | | | |X|X|X| |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | | | | |
| | | |X|X|X| | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | | | | | | |
| | |X|X|X| | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | | |
| |X|X|X| | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | |
|X|X|X|X| | | |X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X|X| | | |X|X| | | |
| |X|X| | | |X|X|X|X|X| | | | |X|X|X|X|X|X|X|X|X|X|X|X| | | | | | |X|X| | | |
| | |X| | | |X|X|X|X| |X| | | | | | |X|X|X|X|X|X| | | |X| | | | | |X|X| | | |
| | | | | |X|X|X|X| |X|X| | | | | | | | | | | | | |X|X|X| | | | | |X|X| | | |
| | | | |X|X|X|X| |X|X| | | | | | | | | | | | | | |X|X|X| | | | | |X|X| | | |
| | | | |X|X|X| | |X|X| | | | | | | | | | | | | | | |X|X| | | | | |X|X| | | |
| | | | |X|X| | | |X|X| | | | | | | | | | | | | | | |X|X| | | | |X|X|X| | | |
| | | |X|X|X| | | | |X|X| | | | | | | | | | | | | | |X|X| | | | |X|X| | | | |
| | | |X|X| | | | | |X|X| | | | | | | | | | | | | | |X|X| | | | |X| | | | | |
| | | |X|X| | | | | |X|X| | | | | | | | | | | | | | |X|X| | | | | | | | | | |
| | | |X|X| | | | | | |X|X| | | | | | | | | | | | | |X|X| | | | | | | | | | |
| | | |X|X| | | | | | |X|X| | | | | | | | | | | | | |X|X| | | | | | | | | | |
| | | | |X|X| | | | | | |X|X| | | | | | | | | | | | | |X|X| | | | | | | | | |
| | | | |X|X|X| | | | | |X|X|X| | | | | | | | | | | | |X|X|X| | | | | | | | |

--- 17.535892963409424 seconds for solve ---



SAT解算器原始出版物中,更诚实地生成了条件和变量-因此,解决方案速度更快,并且可能占用更少的内存。当决定一匹马时,它需要我大约2.7 GB的RAM,并且要花12个内存来安装所有复杂的东西,然后它们开始疯狂地交换到磁盘上……

更多结论得出的结论:

1.我想到为什么最快的Google搜索pycosat示例就是Sudoku解决方案。数独规则更容易放在求解器上,因为您无需描述块和单元之间的复杂关系,基本上只需描述条件“每行每一位”和“一行仅一位”。
但是我不太喜欢数独,所以我不后悔自己选择的决定。

2.我喜欢如何混合DNF和CNF。如果您不想编写正确的条件-无需;只需生成所有选项即可。当然,这不是最佳选择,但可以。

当然,我没有为解决填字游戏的速度创造任何记录,但是我度过了愉快的时光。最重要的是我能做到!:)我也希望你!

All Articles