/*
Number Cross Puzzle in Picat.
"A programming challenge. Number Cross Puzzle"
http://codegolf.stackexchange.com/questions/8571/a-programming-challenge-number-cross-puzzle
"""
This is from a programming challenge website.
The cross problem states that you can place the numbers 1 through N inside the cross
such that no two adjacent cells in any direction (up, down, left or right, or diagonal)
contain adjacent numbers (+ or - 1).
Given the shape of an 8 sized cross below where the numbers represent the cell index:
1 4
0 2 5 7
3 6
there are only 4 solutions for an 8 sized cross. In the above structure, cell 2 is
adjacent to cells 0, 1, 3, 4, 5 and 6 while cell 1 is adjacent to cell 0, 2, 4 and 5.
Here is one of the 4 solutions:
5 3
2 8 1 7
6 4
How many solutions are there on a 12 sized cross given the indexes below?
2 6
0 3 7 10
1 4 8 11
5 9
I solved it via simple brute force where I used recursion to fill the cross. It took
me around 5-10 mins though. I wonder whether there is an efficient algorithm for it,
or maybe a mathematical way. I really liked this challenge and that is why I am wondering
about an efficient solution.
"""
Compare with another approach (for problem #1):
http://hakank.org/picat/place_number_puzzle.pi
This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
See also my Picat page: http://www.hakank.org/picat/
*/
import cp.
main => go.
%
% 12 sized instance
% There are 262288 different solutions (1.3s, 0 backtracks)
%
go =>
problem(2,Rows,Cols,Mat),
Count = count_all(puzzle(Rows,Cols,Mat, _X)),
println(count=Count),
nl.
% Find just one solution
go2 =>
problem(2,Rows,Cols,Mat), % 12 sized
puzzle(Rows,Cols,Mat, X),
println(X),
nl.
% Problem 1 (8 sized)
% 4 solutions
go3 =>
problem(1,Rows,Cols,Mat), % 8 sized
All = find_all(X,puzzle(Rows,Cols,Mat, X)),
println(All),
println(len=All.len),
nl.
puzzle(Rows,Cols,Mat, X) =>
N = sum([1 : I in 1..Rows, J in 1..Cols, Mat[I,J] > 0]),
% decision variables
X = new_array(N),
X :: 1..N,
all_different(X),
% constrain all the neighbours for each cell
V = {-1,0,1},
foreach(I in 1..Rows, J in 1..Cols, Mat[I,J] > 0)
foreach(A in V,B in V,
member(I+A,1..Rows), member(J+B,1..Cols),
not(A == 0, B == 0), Mat[I+A,J+B] > 0)
abs(X[Mat[I,J]] - X[Mat[I+A,J+B]]) #> 1
end
end,
solve([ffd,split],X).
% Problem 1: 8 sized
problem(1,Rows,Cols,Mat) =>
Rows = 3,
Cols = 4,
% 0 means empty cell
Mat =
[
[0, 2, 5, 0],
[1, 3, 6, 8],
[0, 4, 7, 0]
].
% Problem 2: 12 sized
problem(2,Rows,Cols,Mat) =>
Rows = 4,
Cols = 4,
% 0 means empty cell
Mat =
[
[0, 3, 7, 0],
[1, 4, 8, 11],
[2, 5, 9, 12],
[0, 6, 10, 0]
].