Re:Brute-forcing a seemingly simple number puzzle
by triska on Wednesday December 05, 2018 @11:03AM
(#18609448)
That's a very nice challenge!
Here is a Prolog formulation of the task:
:- use_module(library(clpfd)).
n_tour(N, Vs) :-
L #= N*N,
length(Vs0, L),
successors(Vs0, N, 1),
append(Vs0, [_], Vs), % last element is for open tours
circuit(Vs).
successors([], _, _).
successors([V|Vs], N, K0) :-
findall(Num, n_k_next(N, K0, Num), [Next|Nexts]),
foldl(num_to_dom, Nexts, Next, Dom),
Dummy #= N*N + 1, % last element is for open tours
V in Dom \/ Dummy,
K1 #= K0 + 1,
successors(Vs, N, K1).
num_to_dom(N, D0, D0\/N).
n_x_y_k(N, X, Y, K) :- [X,Y] ins 1..N, K #= N*(Y-1) + X.
n_k_next(N, K, Next) :-
n_x_y_k(N, X0, Y0, K),
( [DX,DY] ins -2 \/ 2 % 2 diagonally
; [DX,DY] ins -3 \/ 0 \/ 3, % 3 vertically or horizontally
abs(DX) + abs(DY) #= 3
),
[X,Y] ins 1..N,
X #= X0 + DX,
Y #= Y0 + DY,
n_x_y_k(N, X, Y, Next),
label([DX,DY]).
The key element of this solution is the CPL(FD) constraint circuit/1, which describes a Hamiltonian circuit. It uses a list of finite domain variables to represent solutions: Each element of the list is an integer, denoting the position of the successor in the list. For example, a list with 3 elements admits precisely 2 Hamiltonian circuits, which we can find via search:
?- Vs = [_,_,_], circuit(Vs), label(Vs).
Vs = [2, 3, 1] ;
Vs = [3, 1, 2].
The rest of the code sets up the domains of the involved variables to constrain them to admissible moves. A dummy element is used to allow open tours. The predicate n_x_y_k/4 relates X/Y coordinates to list indices. You can easily adapt this to other variants of the puzzle (e.g., knight's tour) by changing n_k_next/3.
A major attraction of a declarative solution is that it can be used in all directions: We can use the exact same code to test, generate, and to complete solutions. For example, we can use the Prolog program to show that the 5×5 solution that is shown in the article is uniquely defined if we fix just 4 elements in the first row:
Since the search for solutions is decoupled from the problem description, we can easily try different search strategies. For example, using the strategy "ff" (first fail) measurably reduces the running time in this case:
Using CLP(FD) constraints typically yields much faster solutions than using brute-force search, since constraints propagate information before and also during the search to prune the search tree. Especially for more complex tasks, the computational cost of constraint propagation is typically negligible in comparison to traversing the entire search tree.
However, if you want, you can also easily obtain a brute-force variation from this program, by posting the constraints after the search. This turns the whole program into a "generate and test" approach, which is typically much slower than constraint-based search.
Here is a Prolog formulation of the task:
The key element of this solution is the CPL(FD) constraint circuit/1, which describes a Hamiltonian circuit. It uses a list of finite domain variables to represent solutions: Each element of the list is an integer, denoting the position of the successor in the list. For example, a list with 3 elements admits precisely 2 Hamiltonian circuits, which we can find via search: The rest of the code sets up the domains of the involved variables to constrain them to admissible moves. A dummy element is used to allow open tours. The predicate n_x_y_k/4 relates X/Y coordinates to list indices. You can easily adapt this to other variants of the puzzle (e.g., knight's tour) by changing n_k_next/3.A major attraction of a declarative solution is that it can be used in all directions: We can use the exact same code to test, generate, and to complete solutions. For example, we can use the Prolog program to show that the 5×5 solution that is shown in the article is uniquely defined if we fix just 4 elements in the first row:
A few additional definitions let us print solutions in a more readable form: For example, here is the 5×5 solution from the article again: And here is a query that solves the 10×10 instance: Yielding: Since the search for solutions is decoupled from the problem description, we can easily try different search strategies. For example, using the strategy "ff" (first fail) measurably reduces the running time in this case: Using CLP(FD) constraints typically yields much faster solutions than using brute-force search, since constraints propagate information before and also during the search to prune the search tree. Especially for more complex tasks, the computational cost of constraint propagation is typically negligible in comparison to traversing the entire search tree.However, if you want, you can also easily obtain a brute-force variation from this program, by posting the constraints after the search. This turns the whole program into a "generate and test" approach, which is typically much slower than constraint-based search.