-4

一般问题：我们有 8*8 的地图，我们必须用 1 到 6 的数字填充空方格。但是在每一列中，原始数字只能满足 1 次。每行和每列中的两个方格都留空。两边的数字，上下显示我们应该出现的第一个数字（但它可以出现在两个空方块之后）。

所以，现在我有了这个代码，它最终适用于 4*4 地图的 swi-prolog。

:- module(ab, [ab/0]).
:- [library(clpfd)].

gen_row(Ls):-length(Ls, 4), Ls ins 0..3.

transpose(Ms, Ts) :-
    %must_be(list(list), Ms),
    (   Ms = [] -> Ts = []
    ;   Ms = [F|_],
        transpose(F, Ms, Ts)
    ).

transpose([], _, []).
transpose([_|Rs], Ms, [Ts|Tss]) :-
    lists_firsts_rests(Ms, Ts, Ms1),
    transpose(Rs, Ms1, Tss).

lists_firsts_rests([], [], []).
lists_firsts_rests([[F|Os]|Rest], [F|Fs], [Os|Oss]) :-
    lists_firsts_rests(Rest, Fs, Oss).

ab :-
Rows = [R1,R2,R3,R4],
maplist(gen_row, Rows),
transpose(Rows, [C1,C2,C3,C4]),

maplist(all_distinct, [R1,R2,R3,R4]),
maplist(all_distinct, [C1,C2,C3,C4]),

start(R2, 3),
start(R3, 3),
finish(R3, 2),

start(C3, 1),
finish(C2, 2),

maplist(writeln, [R1,R2,R3,R4]).

finish(X, V) :-
reverse(X, Y),
start(Y, V).

start([0,Y|_], Y).
start([Y|_], Y).

但是，它不支持更大面积的 2 个空白位置的问题，例如 8*8 拼图。有什么提示吗？

4

1 回答 1

0

您必须从另一个问题中获取 transpose/2，并将 all_distinct/1 替换为 fd_all_distinct/2。

另外，获取 writeln 并在此处替换 writemaplist(write, [R1,R2,R3,R4]).

编辑一个简单的解决方案是扩展有限域的“编码”，将两位数保留为空白，而不仅仅是 0，并扩展在发布到另一个问题的答案中已经看到的逻辑。

为了类比，我将调用third_end_view，并且将是（在Gnu Prolog中）

/*  File:    third_end_view_puzzle.pl
    Author:  Carlo,,,
    Created: Oct  10 2012
    Purpose: help to solve extended Second End View puzzle
             https://stackoverflow.com/q/12797708/874024
*/

:- include(transpose) .

third_end_view_puzzle :-

    length(Rows, 8),
    maplist(gen_row(8), Rows),
    transpose(Rows, Cols),

    maplist(fd_all_different, Rows),
    maplist(fd_all_different, Cols),

    Rows = [R1,R2,R3,R4,R5,R6,R7,R8],
    Cols = [C1,C2,C3,C4,C5,C6,C7,C8],

    start(R1, 4),
    start(R2, 2),
    start(R3, 3),
    start(R4, 5),
    start(R5, 3),
    finish(R1, 6),
    finish(R2, 4),
    finish(R3, 2),
    finish(R5, 1),
    finish(R7, 2),


    start(C2, 3),
    start(C3, 4),
    start(C4, 3),
    start(C5, 5),
%   start(C6, 4),
    start(C7, 1),
%   finish(C1, 3),
%   finish(C2, 2),
    finish(C3, 5),
    finish(C4, 5),
    finish(C5, 6),
    finish(C6, 1),
    finish(C7, 4),

    maplist(fd_labeling, Rows),
    nl,
    maplist(out_row, Rows).

gen_row(N, Ls) :-
    length(Ls, N),
    fd_domain(Ls, 1, N).

out_row([]) :- nl.
out_row([H|T]) :-
    (H >= 7 -> write('-') ; write(H)),
    write(' '),
    out_row(T).

% constraint: Num is max third in that direction
start(Vars, Num) :-
    Vars = [A,B,C|_],
    A #= Num #\/ (A #>= 7 #/\ B #= Num) #\/ (A #>= 7 #/\ B #>= 7 #/\ C #= Num).

finish(Var, Num) :-
    reverse(Var, Rev), start(Rev, Num).

我使用了一个更简单的条件，没有具体化，来陈述“从方向看的第三个观点”。

如前所述，您会看到一些约束（那些被注释掉的）使这个谜题无法解决。

测试：

| ?- third_end_view_puzzle.  

4 3 - - 5 2 1 6 
2 1 - 3 - 5 6 4 
3 5 4 1 - 6 2 - 
5 4 6 2 1 3 - - 
- - 3 6 2 4 5 1 
1 6 2 4 3 - - 5 
6 - 1 5 4 - 3 2 
- 2 5 - 6 1 4 3 

true ?
于 2012-10-09T10:19:55.653 回答