I am working on a small prolog application to solve the Skyscrapers and Fences puzzle.
An unsolved puzzle:
A solved puzzle:
When I pass the program already solved puzzles it is quick, almost instantaneous, to validate it for me. When I pass the program really small puzzles (2x2, for example, with modified rules, of course), it is also quite fast to find a solution.
The problem is on computing puzzles with the "native" size of 6x6. I've left it running for 5 or so hours before aborting it. Way too much time.
I've found that the part that takes the longest is the "fences" one, not the "skyscrapers". Running "skyscrapers" separately results in a fast solution.
Here's my algorithm for fences:
- Vertices are represented by numbers, 0 means the path doesn't pass through that particular vertex, > 1 represents that vertex's order in the path.
- Constrain each cell to have the appropriate amount of lines surrounding it.
- That means that two vertexes are connected if they have sequential numbers, e.g., 1 -> 2, 2 -> 1, 1 ->
Max,Max-> 1 (Maxis the number for the last vertex in the path. computed viamaximum/2)
- That means that two vertexes are connected if they have sequential numbers, e.g., 1 -> 2, 2 -> 1, 1 ->
- Make sure each non-zero vertex has at least two neighboring vertices with sequential numbers
- Constrain
Maxto be equal to(BoardWidth + 1)^2 - NumberOfZeros(BoardWidth+1is the number of vertices along the edge andNumberOfZerosis computed viacount/4). - Use
nvalue(Vertices, Max + 1)to make sure the number of distinct values inVerticesisMax(i.e. the number of vertices in the path) plus1(zero values) - Find the first cell containing a
3and force the path to begin and end there, for efficiency purposes
What can I do to increase efficiency? Code is included below for reference.
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(
[
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _,
_, _, _, _, _, _, _
]
).