Download
%
% Solitaire Battleships
% Sample ECLiPSe solution by Joachim Schimpf, 2016
% under Creative Commons Attribution 4.0 International License.
%
% This is problem 114 in CSPLIB (http://csplib.org/Problems/prob014)
% see also http://en.wikipedia.org/wiki/Battleship_(puzzle)
%
% Place a given number of ships of different sizes on the grid.
% A ship is a sequence of one (a submarine) to four (a battleship)
% consecutive 1s in the grid, arranged either horizontally or
% vertically. Ships do not touch each other, not even diagonally.
% For each row and each column, the number of 1s in that row/column
% is given. For some coordinates, a "hint" is given, which can be either:
% w(ater) field is 0
% c(ircle) field contains a submarine
% l(eft) field is the left end of a longer ship
% r(ight) field is the right end of a longer ship
% t(op) field is the top end of a longer ship
% b(ottom) field is the bottom end of a longer ship
% m(iddle) field is an inner part (not the end) of a ship
% Sample run:
%
% $ eclipse -f battleships.ecl -e 'battleships(example,_,_)'
%
% . . . . . . x . . .
% . . . x . . x . x .
% . . . . . . x . . .
% . x . . . . . . . .
% . x . x x x x . x .
% . . . . . . . . . .
% . . . . . . x x . .
% . x x x . . . . . .
% . . . . . x . . . .
% . . . . . . . . x x
%
:- lib(ic).
:- lib(ic_global).
% Include a file with problem instances:
%:- include(battleship_instances).
% Or specify your own problem instance here:
problem(example,
[4:1,3:2,2:3,1:4], % Fleet [ShipSize:Amount]
[1,3,1,1,6,0,2,3,1,2], % Row sums
[0,3,1,3,1,2,5,1,3,1], % Column sums
[c@[2,9],t@[4,2],m@[5,6],l@[8,2],r@[10,10]] % Hints
).
battleships(Name, Ships, Grid) :-
problem(Name, Fleet, RowSums, ColSums, Hints),
grid_constraints(RowSums, ColSums, Hints, Grid),
place_ships(Fleet, Grid, Ships),
print_grid(Grid).
% Deterministically set up grid constraints
grid_constraints(RowSums, ColSums, Hints, Grid) :-
length(RowSums, M),
length(ColSums, N),
dim(Grid, [M,N]),
Grid #:: 0..1,
( foreach(RowSum,RowSums), for(I,1,M), param(Grid,N) do
sum(Grid[I,1..N]) #= RowSum
),
( foreach(ColSum,ColSums), for(J,1,N), param(Grid,M) do
sum(Grid[1..M,J]) #= ColSum
),
( foreach(What@[I,J],Hints), param(Grid) do
hint(What, Pattern),
place_pattern(Pattern, I, J, Grid)
).
% Nondeterministically place the fleet
% To remove symmetry, we impose lex order on coordinates of same size ships
place_ships(Fleet, Grid, Ships) :-
sort(1, >=, Fleet, OrderedFleet),
(
foreach(Size:Num,OrderedFleet),
fromto(Ships,Ps1,Ps3,[]),
param(Grid)
do
(
for(_,1,Num), % place Num ships of Size
fromto(Ps1,[Ship|Ps2],Ps2,Ps3),
fromto([0,0],[I0,J0],[I,J],_), % ordered coordinates
param(Size,Grid)
do
Ship = ship(_,[I,J],_),
lex_lt([I0,J0], [I,J]),
place_ship_nondet(Size, Ship, Grid)
)
).
% Nondeterministically place one ship of Size
place_ship_nondet(Size, ship(Size,[I,J],Vertical), Grid) :-
dim(Grid, [M,N]),
between(1, M, 1, I),
between(1, N, 1, J),
ship(Size, HorizontalPattern),
( Vertical=0, HorizontalPattern = Pattern
; Vertical=1, Size>1, transpose(HorizontalPattern, Pattern)
),
place_pattern(Pattern, I, J, Grid).
% Place a ship or hint pattern on the grid at [I,J]
place_pattern(Pattern, I, J, Grid) :-
dim(Grid, [M,N]),
( foreachelem(Given,Pattern,[K,L]), param(Grid,I,J,M,N) do
X is I+K-2, Y is J+L-2,
( 1=<X,X=<M, 1=<Y,Y=<N ->
arg([X,Y], Grid, Given)
;
Given = 0 % field outside grid, can't be 1
)
).
transpose(P, T) :-
dim(P, [M,N]),
dim(T, [N,M]),
( foreachelem(X,P,[I,J]), param(T) do
arg([J,I], T, X)
).
% Shapes of the different ships (the top left 1 is the reference coordinate)
ship(1, [](
[](0,0,0),
[](0,1,0),
[](0,0,0))).
ship(2, [](
[](0,0,0,0),
[](0,1,1,0),
[](0,0,0,0))).
ship(3, [](
[](0,0,0,0,0),
[](0,1,1,1,0),
[](0,0,0,0,0))).
ship(4, [](
[](0,0,0,0,0,0),
[](0,1,1,1,1,0),
[](0,0,0,0,0,0))).
ship(5, [](
[](0,0,0,0,0,0,0),
[](0,1,1,1,1,1,0),
[](0,0,0,0,0,0,0))).
% What the hints mean
hint(w, [](
[](_,_,_),
[](_,0,_),
[](_,_,_))).
hint(c, [](
[](0,0,0),
[](0,1,0),
[](0,0,0))).
hint(m, [](
[](0,V,0),
[](H,1,H),
[](0,V,0))) :- V #\= H.
hint(t, [](
[](0,0,0),
[](0,1,0),
[](0,1,0))).
hint(b, [](
[](0,1,0),
[](0,1,0),
[](0,0,0))).
hint(l, [](
[](0,0,0),
[](0,1,1),
[](0,0,0))).
hint(r, [](
[](0,0,0),
[](1,1,0),
[](0,0,0))).
print_grid(Grid) :-
( foreachelem(X,Grid,[_,J]) do
( J==1 -> nl ; true ),
( var(X) -> write(' ?') ; X==1 -> write(' x') ; write(' .') )
), nl.
This work is licensed under a Creative Commons Attribution 4.0 International License.