- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我是 Prolog 的新手(例如:我在 7 周内只用 7 种语言完成了 Prolog 章节),因此非常欢迎对以下任何代码提出一般性评论。
首先:什么是 hell ?这就像一个数独游戏,除了你得到一个空的网格,并且在每个 3x3 block 内,给出相邻插槽之间的不等式。此处示例:http://krazydad.com/jigoku/books/KD_Jigoku_CH_8_v18.pdf .您仍然需要填充网格,使每一行、每一列和每一 block 都包含数字 1-9。
我尝试基于这个数独解算器实现一个解算器:http://programmablelife.blogspot.co.uk/2012/07/prolog-sudoku-solver-explained.html .出于调试原因,我从一个运行良好的 4x4 示例开始:
:- use_module(library(clpfd)).
small_jidoku(Rows, RowIneqs, ColIneqs) :-
Rows = [A,B,C,D],
append(Rows, Vs), Vs ins 1..4,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
blocks(A, B), blocks(C,D),
maplist(label, Rows),
fake_check_ineqs(Rows, RowIneqs),
fake_check_ineqs(Columns, ColIneqs),
pretty_print([A,B,C,D]).
blocks([], []).
blocks([A,B|Bs1], [D,E|Bs2]) :-
all_distinct([A,B,D,E]),
blocks(Bs1, Bs2).
fake_check_ineqs([],[]).
fake_check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :-
Head = [A,B,C,D],
atom_chars(Ineq1, [X1,X2]),
call(X1, A, B),
call(X2, C, D),
fake_check_ineqs(Tail, TailIneqs).
pretty_print([]).
pretty_print([Head | Tail]) :-
print(Head),
print('\n'),
pretty_print(Tail).
然后我解决了下面的例子:
time(small_jidoku([[A1,A2,A3,A4],[B1,B2,B3,B4],[C1,C2,C3,C4],[D1,D2,D3,D4]],[><,<>,<<,<<],[><,<<,<>,>>])).
这会在大约 0.5 秒内运行。但是,我也尝试用
解决它time(small_jidoku([A,B,C,D],[><,<>,<<,<<],[><,<<,<>,>>])).
这似乎需要很长时间。谁能解释为什么当我没有指定每行有 4 个元素时求解器需要更长的时间?对此我天真的回答是 Prolog,如果没有告诉我行的实际格式,将也尝试探索更小/更大的行,因此浪费时间在例如行长度为 5,但这真的是真的吗?
我的第二个问题是关于 9x9 版本,它与 4x4 非常相似,只是 block 当然更大,而且在检查不等式时需要进行更多测试。代码如下:
:- use_module(library(clpfd)).
jidoku(Rows, RowIneqs, ColIneqs) :-
Rows = [A,B,C,D,E,F,G,H,I],
append(Rows, Vs), Vs ins 1..9,
maplist(all_distinct, Rows),
transpose(Rows, Columns),
maplist(all_distinct, Columns),
blocks(A, B, C), blocks(D, E, F), blocks(G, H, I),
maplist(label, Rows),
check_ineqs(Rows, RowIneqs),
check_ineqs(Columns, ColIneqs),
pretty_print([A,B,C,D,E,F,G,H,I]).
blocks([], [], []).
blocks([A,B,C|Bs1], [D,E,F|Bs2], [G,H,I|Bs3]) :-
all_distinct([A,B,C,D,E,F,G,H,I]),
blocks(Bs1, Bs2, Bs3).
check_ineqs([],[]).
check_ineqs([Head|Tail], [Ineq1|TailIneqs]) :-
Head = [A,B,C,D,E,F,G,H,I],
atom_chars(Ineq1, [X1, X2, X3, X4, X5, X6]),
call(X1, A, B),
call(X2, B, C),
call(X3, D, E),
call(X4, E, F),
call(X5, G, H),
call(X6, H, I),
check_ineqs(Tail, TailIneqs).
测试示例:
time(jidoku([[A1,A2,A3,A4,A5,A6,A7,A8,A9],
[B1,B2,B3,B4,B5,B6,B7,B8,B9],
[C1,C2,C3,C4,C5,C6,C7,C8,C9],
[D1,D2,D3,D4,D5,D6,D7,D8,D9],
[E1,E2,E3,E4,E5,E6,E7,E8,E9],
[F1,F2,F3,F4,F5,F6,F7,F8,F9],
[G1,G2,G3,G4,G5,G6,G7,G8,G9],
[H1,H2,H3,H4,H5,H6,H7,H8,H9],
[I1,I2,I3,I4,I5,I6,I7,I8,I9]],
[<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>],
[<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])).
并且这个已经运行了一夜没有得出任何结论,在这一点上,我完全不知道出了什么问题。我预计会出现一些缩放问题,但不是这个比例!
如果真正知道自己在做什么的人能够对此有所启发,那就太好了!已经谢谢了!
最佳答案
这是我想到的您的代码版本(其他谓词保持不变):
ineqs(Cells, Ineq) :-
atom_chars(Ineq, Cs),
maplist(primitive_declarative, Cs, Ds),
ineqs_(Ds, Cells).
ineqs_([], _).
ineqs_([Op1,Op2|Ops], [A,B,C|Cells]) :-
call(Op1, A, B),
call(Op2, B, C),
ineqs_(Ops, Cells).
primitive_declarative(<, #<).
primitive_declarative(>, #>).
请注意,调用谓词“check_...
”并不符合代码的一般性,因为谓词说明了持有什么并且可以使用在几个方向:是的,它可以用来检查约束是否成立,但它可以也用来声明约束必须保持一些变量。因此,我避免命令式并使用更多声明性名称。
您在 jidoku/3
中使用 ineqs/2
与:maplist(ineqs, Rows, RowsIneqs)
等
您的示例和新版本的结果,使用 SWI 7.3.2:
?- length(Rows, 9), maplist(same_length(Rows), Rows),
time(jidoku(Rows,
[<>>><>,<<<>><,<<<><>,<><<><,>>><><,><>><>,<>>><>,<>><><,><<>>>],
[<<<><>,><<>>>,<><<><,><<<>>,><><<<,<><><>,<>>>><,><><><,<>><>>])),
maplist(writeln, Rows).
% 2,745,471 inferences, 0.426 CPU in 0.432 seconds (99% CPU, 6442046 Lips)
[1,5,4,8,7,2,6,9,3]
[2,3,9,1,6,5,7,4,8]
[6,7,8,3,9,4,2,5,1]
[3,4,1,2,5,6,8,7,9]
[9,6,5,7,1,8,3,2,4]
[8,2,7,9,4,3,1,6,5]
[4,9,3,6,2,1,5,8,7]
[7,8,2,5,3,9,4,1,6]
[5,1,6,4,8,7,9,3,2]
Rows = [[1, 5, 4, 8, 7, 2, 6, 9|...], ...].
事实上,请注意,在这种特殊情况下,根本不需要标记来计算唯一的解决方案,因为约束求解器足够强大,可以将所有域简化为单例集。
在您之前的版本中,所有的时间都被不必要地浪费在天真地生成最终被认为是不一致的排列上。在新版本中,约束求解器有机会更早地应用这些知识。
因此建议首先声明所有约束,然后才调用labeling/2
来搜索具体的解决方案,如CLP(FD) manual 中所述。 .
关于Prolog - jigoku 求解器 - 运行时,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31501347/
SQLite、Content provider 和 Shared Preference 之间的所有已知区别。 但我想知道什么时候需要根据情况使用 SQLite 或 Content Provider 或
警告:我正在使用一个我无法完全控制的后端,所以我正在努力解决 Backbone 中的一些注意事项,这些注意事项可能在其他地方更好地解决......不幸的是,我别无选择,只能在这里处理它们! 所以,我的
我一整天都在挣扎。我的预输入搜索表达式与远程 json 数据完美配合。但是当我尝试使用相同的 json 数据作为预取数据时,建议为空。点击第一个标志后,我收到预定义消息“无法找到任何内容...”,结果
我正在制作一个模拟 NHL 选秀彩票的程序,其中屏幕右侧应该有一个 JTextField,并且在左侧绘制弹跳的选秀球。我创建了一个名为 Ball 的类,它实现了 Runnable,并在我的主 Draf
这个问题已经有答案了: How can I calculate a time span in Java and format the output? (18 个回答) 已关闭 9 年前。 这是我的代码
我有一个 ASP.NET Web API 应用程序在我的本地 IIS 实例上运行。 Web 应用程序配置有 CORS。我调用的 Web API 方法类似于: [POST("/API/{foo}/{ba
我将用户输入的时间和日期作为: DatePicker dp = (DatePicker) findViewById(R.id.datePicker); TimePicker tp = (TimePic
放宽“邻居”的标准是否足够,或者是否有其他标准行动可以采取? 最佳答案 如果所有相邻解决方案都是 Tabu,则听起来您的 Tabu 列表的大小太长或您的释放策略太严格。一个好的 Tabu 列表长度是
我正在阅读来自 cppreference 的代码示例: #include #include #include #include template void print_queue(T& q)
我快疯了,我试图理解工具提示的行为,但没有成功。 1. 第一个问题是当我尝试通过插件(按钮 1)在点击事件中使用它时 -> 如果您转到 Fiddle,您会在“内容”内看到该函数' 每次点击都会调用该属
我在功能组件中有以下代码: const [ folder, setFolder ] = useState([]); const folderData = useContext(FolderContex
我在使用预签名网址和 AFNetworking 3.0 从 S3 获取图像时遇到问题。我可以使用 NSMutableURLRequest 和 NSURLSession 获取图像,但是当我使用 AFHT
我正在使用 Oracle ojdbc 12 和 Java 8 处理 Oracle UCP 管理器的问题。当 UCP 池启动失败时,我希望关闭它创建的连接。 当池初始化期间遇到 ORA-02391:超过
关闭。此题需要details or clarity 。目前不接受答案。 想要改进这个问题吗?通过 editing this post 添加详细信息并澄清问题. 已关闭 9 年前。 Improve
引用这个plunker: https://plnkr.co/edit/GWsbdDWVvBYNMqyxzlLY?p=preview 我在 styles.css 文件和 src/app.ts 文件中指定
为什么我的条形这么细?我尝试将宽度设置为 1,它们变得非常厚。我不知道还能尝试什么。默认厚度为 0.8,这是应该的样子吗? import matplotlib.pyplot as plt import
当我编写时,查询按预期执行: SELECT id, day2.count - day1.count AS diff FROM day1 NATURAL JOIN day2; 但我真正想要的是右连接。当
我有以下时间数据: 0 08/01/16 13:07:46,335437 1 18/02/16 08:40:40,565575 2 14/01/16 22:2
一些背景知识 -我的 NodeJS 服务器在端口 3001 上运行,我的 React 应用程序在端口 3000 上运行。我在 React 应用程序 package.json 中设置了一个代理来代理对端
我面临着一个愚蠢的问题。我试图在我的 Angular 应用程序中延迟加载我的图像,我已经尝试过这个2: 但是他们都设置了 src attr 而不是 data-src,我在这里遗漏了什么吗?保留 d
我是一名优秀的程序员,十分优秀!