Оптимизация поиска пути в логическом программировании с ограничениями с помощью Prolog

Я работаю над небольшим приложением prolog для решения головоломки Небоскребы и заборы.

Не решенная головоломка:

Решенная головоломка:

Когда я передаю программе уже решенные головоломки, она быстро, почти мгновенно, подтверждает их для меня. Когда я передаю программе действительно маленькие головоломки (2x2, например, с измененными правилами, конечно), она также довольно быстро находит решение.

Проблема заключается в вычислении головоломок с "родным" размером 6x6. Я оставил ее запущенной на 5 или около того часов, прежде чем прервать ее. Слишком много времени.

Я обнаружил, что больше всего времени занимает часть "заборы", а не "небоскребы". Запуск "небоскребов" отдельно приводит к быстрому решению.

Вот мой алгоритм для заборов:

• Вершины представлены числами, 0 означает, что путь не проходит через данную вершину, > 1 означает порядок этой вершины в пути.
• Ограничьте каждую клетку, чтобы вокруг нее было соответствующее количество линий.
  • Это означает, что две вершины соединены, если они имеют последовательные номера, например, 1 -> 2, 2 -> 1, 1 -> Max, Max -> 1 (Max - номер последней вершины на пути. вычисляется через maximum/2)
• Убедитесь, что каждая ненулевая вершина имеет как минимум две соседние вершины с последовательными номерами
• Ограничьте Max, чтобы он был равен (BoardWidth + 1)^2 - NumberOfZeros (BoardWidth+1 - количество вершин вдоль ребра, а NumberOfZeros вычисляется через count/4).
• Используйте nvalue(Vertices, Max + 1), чтобы убедиться, что число отдельных значений в Vertices равно Max (т.е. количество вершин в пути) плюс 1 (нулевые значения)
• Найдите первую ячейку, содержащую 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(
    [
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _,
        _, _, _, _, _, _, _
    ]
).