超高層ビルとフェンスのパズルを解くための小さなプロローグ アプリケーションに取り組んでいます。
未解決のパズル:
解かれたパズル:
すでに解決済みのパズルをプログラムに渡すと、それを検証するのはほとんど瞬時に行われます。プログラムに非常に小さなパズル (たとえば、2x2、もちろん変更されたルール) を渡すと、解決策を見つけるのも非常に高速です。
問題は、「ネイティブ」サイズの 6x6 のパズルを計算することです。中止する前に、5時間ほど実行したままにしました。時間がかかりすぎます。
最も時間がかかるのは「高層ビル」ではなく「フェンス」であることがわかりました。"skyscrapers" を個別に実行すると、高速なソリューションが得られます。
フェンスのアルゴリズムは次のとおりです。
- 頂点は数字で表され、0 はパスがその特定の頂点を通過しないことを意味し、> 1 はパス内のその頂点の順序を表します。
- 各セルが適切な量の線で囲まれるように制約します。
- つまり、2 つの頂点が連番を持つ場合、それらが接続されていることを意味します。たとえば、1 -> 2、2 -> 1、1 ->
Max、Max-> 1 (Maxは、パス内の最後の頂点の番号です。 を介して計算されますmaximum/2) 。
- つまり、2 つの頂点が連番を持つ場合、それらが接続されていることを意味します。たとえば、1 -> 2、2 -> 1、1 ->
- ゼロ以外の各頂点に、連番を持つ隣接する頂点が少なくとも 2 つあることを確認します。
- (はエッジに沿った頂点の数で、で計算されます)
Maxと等しくなるように制約します。(BoardWidth + 1)^2 - NumberOfZerosBoardWidth+1NumberOfZeroscount/4 nvalue(Vertices, Max + 1)の個別の値の数VerticesがMax(つまり、パス内の頂点の数) プラス1(ゼロ値)であることを確認するために使用します。- a を含む最初のセルを見つけて、
3効率を高めるためにパスを強制的にそこから開始および終了させます。
効率を上げるにはどうすればよいですか？参照用にコードを以下に示します。
skyscrapersinfences.pro
:-use_module(library(clpfd)).
:-use_module(library(lists)).
:-ensure_loaded('utils.pro').
:-ensure_loaded('s1.pro').
print_row([]).
print_row([Head|Tail]) :-
write(Head), write(' '),
print_row(Tail).
print_board(Board, BoardWidth) :-
print_board(Board, BoardWidth, 0).
print_board(_, BoardWidth, BoardWidth).
print_board(Board, BoardWidth, Index) :-
make_segment(Board, BoardWidth, Index, row, Row),
print_row(Row), nl,
NewIndex is Index + 1,
print_board(Board, BoardWidth, NewIndex).
print_boards([], _).
print_boards([Head|Tail], BoardWidth) :-
print_board(Head, BoardWidth), nl,
print_boards(Tail, BoardWidth).
get_board_element(Board, BoardWidth, X, Y, Element) :-
Index is BoardWidth*Y + X,
get_element_at(Board, Index, Element).
make_column([], _, _, []).
make_column(Board, BoardWidth, Index, Segment) :-
get_element_at(Board, Index, Element),
munch(Board, BoardWidth, MunchedBoard),
make_column(MunchedBoard, BoardWidth, Index, ColumnTail),
append([Element], ColumnTail, Segment).
make_segment(Board, BoardWidth, Index, row, Segment) :-
NIrrelevantElements is BoardWidth*Index,
munch(Board, NIrrelevantElements, MunchedBoard),
select_n_elements(MunchedBoard, BoardWidth, Segment).
make_segment(Board, BoardWidth, Index, column, Segment) :-
make_column(Board, BoardWidth, Index, Segment).
verify_segment(_, 0).
verify_segment(Segment, Value) :-
verify_segment(Segment, Value, 0).
verify_segment([], 0, _).
verify_segment([Head|Tail], Value, Max) :-
Head #> Max #<=> B,
Value #= M+B,
maximum(NewMax, [Head, Max]),
verify_segment(Tail, M, NewMax).
exactly(_, [], 0).
exactly(X, [Y|L], N) :-
X #= Y #<=> B,
N #= M +B,
exactly(X, L, M).
constrain_numbers(Vars) :-
exactly(3, Vars, 1),
exactly(2, Vars, 1),
exactly(1, Vars, 1).
iteration_values(BoardWidth, Index, row, 0, column) :-
Index is BoardWidth - 1.
iteration_values(BoardWidth, Index, Type, NewIndex, Type) :-
\+((Type = row, Index is BoardWidth - 1)),
NewIndex is Index + 1.
solve_skyscrapers(Board, BoardWidth) :-
solve_skyscrapers(Board, BoardWidth, 0, row).
solve_skyscrapers(_, BoardWidth, BoardWidth, column).
solve_skyscrapers(Board, BoardWidth, Index, Type) :-
make_segment(Board, BoardWidth, Index, Type, Segment),
domain(Segment, 0, 3),
constrain_numbers(Segment),
observer(Type, Index, forward, ForwardObserver),
verify_segment(Segment, ForwardObserver),
observer(Type, Index, reverse, ReverseObserver),
reverse(Segment, ReversedSegment),
verify_segment(ReversedSegment, ReverseObserver),
iteration_values(BoardWidth, Index, Type, NewIndex, NewType),
solve_skyscrapers(Board, BoardWidth, NewIndex, NewType).
build_vertex_list(_, Vertices, BoardWidth, X, Y, List) :-
V1X is X, V1Y is Y, V1Index is V1X + V1Y*(BoardWidth+1),
V2X is X+1, V2Y is Y, V2Index is V2X + V2Y*(BoardWidth+1),
V3X is X+1, V3Y is Y+1, V3Index is V3X + V3Y*(BoardWidth+1),
V4X is X, V4Y is Y+1, V4Index is V4X + V4Y*(BoardWidth+1),
get_element_at(Vertices, V1Index, V1),
get_element_at(Vertices, V2Index, V2),
get_element_at(Vertices, V3Index, V3),
get_element_at(Vertices, V4Index, V4),
List = [V1, V2, V3, V4].
build_neighbors_list(Vertices, VertexWidth, X, Y, [NorthMask, EastMask, SouthMask, WestMask], [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor]) :-
NorthY is Y - 1,
EastX is X + 1,
SouthY is Y + 1,
WestX is X - 1,
NorthNeighborIndex is (NorthY)*VertexWidth + X,
EastNeighborIndex is Y*VertexWidth + EastX,
SouthNeighborIndex is (SouthY)*VertexWidth + X,
WestNeighborIndex is Y*VertexWidth + WestX,
(NorthY >= 0, get_element_at(Vertices, NorthNeighborIndex, NorthNeighbor) -> NorthMask = 1 ; NorthMask = 0),
(EastX < VertexWidth, get_element_at(Vertices, EastNeighborIndex, EastNeighbor) -> EastMask = 1 ; EastMask = 0),
(SouthY < VertexWidth, get_element_at(Vertices, SouthNeighborIndex, SouthNeighbor) -> SouthMask = 1 ; SouthMask = 0),
(WestX >= 0, get_element_at(Vertices, WestNeighborIndex, WestNeighbor) -> WestMask = 1 ; WestMask = 0).
solve_path(_, VertexWidth, 0, VertexWidth) :-
write('end'),nl.
solve_path(Vertices, VertexWidth, VertexWidth, Y) :-
write('switch row'),nl,
Y \= VertexWidth,
NewY is Y + 1,
solve_path(Vertices, VertexWidth, 0, NewY).
solve_path(Vertices, VertexWidth, X, Y) :-
X >= 0, X < VertexWidth, Y >= 0, Y < VertexWidth,
write('Path: '), nl,
write('Vertex width: '), write(VertexWidth), nl,
write('X: '), write(X), write(' Y: '), write(Y), nl,
VertexIndex is X + Y*VertexWidth,
write('1'),nl,
get_element_at(Vertices, VertexIndex, Vertex),
write('2'),nl,
build_neighbors_list(Vertices, VertexWidth, X, Y, [NorthMask, EastMask, SouthMask, WestMask], [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor]),
L1 = [NorthMask, EastMask, SouthMask, WestMask],
L2 = [NorthNeighbor, EastNeighbor, SouthNeighbor, WestNeighbor],
write(L1),nl,
write(L2),nl,
write('3'),nl,
maximum(Max, Vertices),
write('4'),nl,
write('Max: '), write(Max),nl,
write('Vertex: '), write(Vertex),nl,
(Vertex #> 1 #/\ Vertex #\= Max) #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Vertex - 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Vertex - 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Vertex - 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Vertex - 1))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Vertex + 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Vertex + 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Vertex + 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Vertex + 1))
),
write('5'),nl,
Vertex #= 1 #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Max)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Max)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Max)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Max))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= 2)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= 2)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= 2)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= 2))
),
write('6'),nl,
Vertex #= Max #=> (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= 1))
) #/\ (
((NorthMask #> 0 #/\ NorthNeighbor #> 0) #/\ (NorthNeighbor #= Max - 1)) #\
((EastMask #> 0 #/\ EastNeighbor #> 0) #/\ (EastNeighbor #= Max - 1)) #\
((SouthMask #> 0 #/\ SouthNeighbor #> 0) #/\ (SouthNeighbor #= Max - 1)) #\
((WestMask #> 0 #/\ WestNeighbor #> 0) #/\ (WestNeighbor #= Max - 1))
),
write('7'),nl,
NewX is X + 1,
solve_path(Vertices, VertexWidth, NewX, Y).
solve_fences(Board, Vertices, BoardWidth) :-
VertexWidth is BoardWidth + 1,
write('- Solving vertices'),nl,
solve_vertices(Board, Vertices, BoardWidth, 0, 0),
write('- Solving path'),nl,
solve_path(Vertices, VertexWidth, 0, 0).
solve_vertices(_, _, BoardWidth, 0, BoardWidth).
solve_vertices(Board, Vertices, BoardWidth, BoardWidth, Y) :-
Y \= BoardWidth,
NewY is Y + 1,
solve_vertices(Board, Vertices, BoardWidth, 0, NewY).
solve_vertices(Board, Vertices, BoardWidth, X, Y) :-
X >= 0, X < BoardWidth, Y >= 0, Y < BoardWidth,
write('process'),nl,
write('X: '), write(X), write(' Y: '), write(Y), nl,
build_vertex_list(Board, Vertices, BoardWidth, X, Y, [V1, V2, V3, V4]),
write('1'),nl,
get_board_element(Board, BoardWidth, X, Y, Element),
write('2'),nl,
maximum(Max, Vertices),
(V1 #> 0 #/\ V2 #> 0 #/\
(
(V1 + 1 #= V2) #\
(V1 - 1 #= V2) #\
(V1 #= Max #/\ V2 #= 1) #\
(V1 #= 1 #/\ V2 #= Max)
)
) #<=> B1,
(V2 #> 0 #/\ V3 #> 0 #/\
(
(V2 + 1 #= V3) #\
(V2 - 1 #= V3) #\
(V2 #= Max #/\ V3 #= 1) #\
(V2 #= 1 #/\ V3 #= Max)
)
) #<=> B2,
(V3 #> 0 #/\ V4 #> 0 #/\
(
(V3 + 1 #= V4) #\
(V3 - 1 #= V4) #\
(V3 #= Max #/\ V4 #= 1) #\
(V3 #= 1 #/\ V4 #= Max)
)
) #<=> B3,
(V4 #> 0 #/\ V1 #> 0 #/\
(
(V4 + 1 #= V1) #\
(V4 - 1 #= V1) #\
(V4 #= Max #/\ V1 #= 1) #\
(V4 #= 1 #/\ V1 #= Max)
)
) #<=> B4,
write('3'),nl,
sum([B1, B2, B3, B4], #= , C),
write('4'),nl,
Element #> 0 #=> C #= Element,
write('5'),nl,
NewX is X + 1,
solve_vertices(Board, Vertices, BoardWidth, NewX, Y).
sel_next_variable_for_path(Vars,Sel,Rest) :-
% write(Vars), nl,
findall(Idx-Cost, (nth1(Idx, Vars,V), fd_set(V,S), fdset_size(S,Size), fdset_min(S,Min), var_cost(Min,Size, Cost)), L),
min_member(comp, BestIdx-_MinCost, L),
nth1(BestIdx, Vars, Sel, Rest),!.
var_cost(0, _, 1000000) :- !.
var_cost(_, 1, 1000000) :- !.
var_cost(X, _, X).
%build_vertex_list(_, Vertices, BoardWidth, X, Y, List)
constrain_starting_and_ending_vertices(Vertices, [V1,V2,V3,V4]) :-
maximum(Max, Vertices),
(V1 #= 1 #/\ V2 #= Max #/\ V3 #= Max - 1 #/\ V4 #= 2 ) #\
(V1 #= Max #/\ V2 #= 1 #/\ V3 #= 2 #/\ V4 #= Max - 1 ) #\
(V1 #= Max - 1 #/\ V2 #= Max #/\ V3 #= 1 #/\ V4 #= 2 ) #\
(V1 #= 2 #/\ V2 #= 1 #/\ V3 #= Max #/\ V4 #= Max - 1 ) #\
(V1 #= 1 #/\ V2 #= 2 #/\ V3 #= Max - 1 #/\ V4 #= Max ) #\
(V1 #= Max #/\ V2 #= Max - 1 #/\ V3 #= 2 #/\ V4 #= 1 ) #\
(V1 #= Max - 1 #/\ V2 #= 2 #/\ V3 #= 1 #/\ V4 #= Max ) #\
(V1 #= 2 #/\ V2 #= Max - 1 #/\ V3 #= Max #/\ V4 #= 1 ).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth) :-
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, 0, 0).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, BoardWidth, Y) :-
Y \= BoardWidth,
NewY is Y + 1,
solve_path(Board, Vertices, BoardWidth, 0, NewY).
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, X, Y) :-
X >= 0, X < BoardWidth, Y >= 0, Y < BoardWidth,
build_vertex_list(_, Vertices, BoardWidth, X, Y, List),
get_board_element(Board, BoardWidth, X, Y, Element),
(Element = 3 ->
constrain_starting_and_ending_vertices(Vertices, List)
;
NewX is X + 1,
set_starting_and_ending_vertices(Board, Vertices, BoardWidth, NewX, Y)).
solve(Board, Vertices, BoardWidth) :-
write('Skyscrapers'), nl,
solve_skyscrapers(Board, BoardWidth),
write('Labeling'), nl,
labeling([ff], Board), !,
write('Setting domain'), nl,
NVertices is (BoardWidth+1)*(BoardWidth+1),
domain(Vertices, 0, NVertices),
write('Starting and ending vertices'), nl,
set_starting_and_ending_vertices(Board, Vertices, BoardWidth),
write('Setting maximum'), nl,
maximum(Max, Vertices),
write('1'),nl,
Max #> BoardWidth + 1,
write('2'),nl,
Max #< NVertices,
count(0, Vertices, #=, NZeros),
Max #= NVertices - NZeros,
write('3'),nl,
write('Calling nvalue'), nl,
ValueCount #= Max + 1,
nvalue(ValueCount, Vertices),
write('Solving fences'), nl,
solve_fences(Board, Vertices, BoardWidth),
write('Labeling'), nl,
labeling([ff], Vertices).
main :-
board(Board),
board_width(BoardWidth),
vertices(Vertices),
solve(Board, Vertices, BoardWidth),
%findall(Board,
% labeling([ff], Board),
% Boards
%),
%append(Board, Vertices, Final),
write('done.'),nl,
print_board(Board, 6), nl,
print_board(Vertices, 7).
utils.pro
get_element_at([Head|_], 0, Head).
get_element_at([_|Tail], Index, Element) :-
Index \= 0,
NewIndex is Index - 1,
get_element_at(Tail, NewIndex, Element).
reverse([], []).
reverse([Head|Tail], Inv) :-
reverse(Tail, Aux),
append(Aux, [Head], Inv).
munch(List, 0, List).
munch([_|Tail], Count, FinalList) :-
Count > 0,
NewCount is Count - 1,
munch(Tail, NewCount, FinalList).
select_n_elements(_, 0, []).
select_n_elements([Head|Tail], Count, FinalList) :-
Count > 0,
NewCount is Count - 1,
select_n_elements(Tail, NewCount, Result),
append([Head], Result, FinalList).
generate_list(Element, NElements, [Element|Result]) :-
NElements > 0,
NewNElements is NElements - 1,
generate_list(Element, NewNElements, Result).
generate_list(_, 0, []).
s1.pro
% Skyscrapers and Fences puzzle S1
board_width(6).
%observer(Type, Index, Orientation, Observer),
observer(row, 0, forward, 2).
observer(row, 1, forward, 2).
observer(row, 2, forward, 2).
observer(row, 3, forward, 1).
observer(row, 4, forward, 2).
observer(row, 5, forward, 1).
observer(row, 0, reverse, 1).
observer(row, 1, reverse, 1).
observer(row, 2, reverse, 2).
observer(row, 3, reverse, 3).
observer(row, 4, reverse, 2).
observer(row, 5, reverse, 2).
observer(column, 0, forward, 2).
observer(column, 1, forward, 3).
observer(column, 2, forward, 0).
observer(column, 3, forward, 2).
observer(column, 4, forward, 2).
observer(column, 5, forward, 1).
observer(column, 0, reverse, 1).
observer(column, 1, reverse, 1).
observer(column, 2, reverse, 2).
observer(column, 3, reverse, 2).
observer(column, 4, reverse, 2).
observer(column, 5, reverse, 2).
board(
[
_, _, 2, _, _, _,
_, _, _, _, _, _,
_, 2, _, _, _, _,
_, _, _, 2, _, _,
_, _, _, _, _, _,
_, _, _, _, _, _
]
).
vertices(
[
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _
]
).