% new zinc file SolitaireBattleships.mzn % At attempt to build a solution entirely within the IDE % By Peter Stuckey August 2009 % Solitaire Battleships is a puzzle where % we are given a partially filled in board and the number % of ships in each row and column and have to fill it with ships % "Improved" version does not introduce reified set_in int: width; % height of board (usually 10) int: height; % width of board (usually 10) int: maxship; % maximal length of ship (usually 4) set of int: ROWS = 1..width; set of int: COLS = 1..height; set of int: XROWS = 0..width+1; % extended rows set of int: XCOLS = 0..height+1; % extended cols %% ship types enumerated type set of int: SHIPS = 1..maxship; % different ship types int: submarine = 1; int: destroyer = 2; int: cruiser = 3; int: battleship = 4; %% the PIECES enumerated type! set of int: PIECES = 1..7; int: w = 1; % water int: c = 2; % circle (submarine) int: l = 3; % left end of ship int: r = 4; % right end of ship int: t = 5; % top of ship int: b = 6; % bottom of ship int: m = 7; % middle of ship array[PIECES] of string: code = [".","c","l","r","t","b","m"]; array[ROWS,COLS] of 0..7: hint; % the initial board configuration array[ROWS] of int: rowsum; % sums for each row array[COLS] of int: colsum; % sums for each col array[SHIPS] of int: ship; % the number of each type of ship (usually [4,3,2,1]). % variables array[XROWS,XCOLS] of var PIECES: board; % the board array[XROWS,XCOLS] of var 0..1: fill; % which pieces are ships array[PIECES] of var 0..width*height: npiece; % number of pieces of each type % model % ensure hints are respected constraint forall(i in ROWS, j in COLS)( if hint[i,j] != 0 then board[i,j] == hint[i,j] else true endif ); % make extended rows and cols empty constraint forall(i in XROWS)(board[i,0] == w /\ board[i,width+1] == w); constraint forall(j in COLS)(board[0,j] == w /\ board[height+1,j] == w); % ensure that the fill array matches the board constraint forall(i in XROWS, j in XCOLS)( fill[i,j] = bool2int(board[i,j] != w) ); % spacing constraints: gaps betwen ships constraint forall(i in ROWS, j in COLS)( (board[i,j] == w \/ board[i+1,j+1] == w) /\ (board[i,j] == w \/ board[i+1,j-1] == w) % diagonal constraints /\ (board[i,j] in {c,l,r,t} -> board[i-1,j] == w) /\ (board[i,j] in {c,l,r,b} -> board[i+1,j] == w) /\ (board[i,j] in {c,l,t,b} -> board[i,j-1] == w) /\ (board[i,j] in {c,r,t,b} -> board[i,j+1] == w) ); % ship shape constraints constraint forall(i in ROWS, j in COLS)( %% a left piece needs a right piece or middle to the right (board[i,j] == l -> (board[i,j+1] == r \/ board[i,j+1] == m)) /\ (board[i,j] == r -> (board[i,j-1] == l \/ board[i,j-1] == m)) /\ (board[i,j] == t -> (board[i+1,j] == b \/ board[i+1,j] == m)) /\ (board[i,j] == b -> (board[i-1,j] == t \/ board[i-1,j] == m)) %% a middle piece has to have two opposite sides filled /\ (board[i,j] == m -> ( fill[i-1,j] == fill[i+1,j] /\ fill[i,j-1] == fill[i,j+1] /\ fill[i-1,j] + fill[i,j-1] == 1)) ); % sum up pieces constraint forall(p in PIECES)( sum(i in ROWS, j in COLS)(bool2int(board[i,j] == p)) == npiece[p] ); % piece sum constraints constraint npiece[c] == ship[submarine]; % submarines constraint npiece[l] == npiece[r]; % left right (probably redundant) constraint npiece[t] == npiece[b]; % top bottom constraint npiece[l] + npiece[t] == sum(s in destroyer..maxship)(ship[s]); % no of ends constraint npiece[m] == sum(s in cruiser..maxship)(ship[s] * (s - 2)); % no of middles % count number of bigger ships % at least for standard battleships you can probably simply % enforce this constraint for s in destroyer..destroyer % and still be guaranteed a correct solution constraint forall(s in destroyer..maxship)( sum(i in ROWS,j in COLS)(bool2int( if j + s - 1 <= width then board[i,j] == l /\ board[i,j+s-1] == r % ship length s lr /\ forall(k in j+1..j+s-2)(board[i,k] == m) else false endif \/ if i + s - 1 <= height then board[i,j] == t /\ board[i+s-1,j] == b % ship length s tb /\ forall(k in i+1..i+s-2)(board[k,j] == m) else false endif )) = ship[s] ); % row sums respected constraint forall(i in ROWS)( sum(j in COLS)(fill[i,j]) == rowsum[i] ); % column sums respected constraint forall(j in COLS)( sum(i in ROWS)(fill[i,j]) == colsum[j] ); solve :: int_search([ fill[i,j] | i in ROWS, j in COLS], input_order, indomain_min, complete) satisfy; output [ code[fix(board[i,j])] ++ if j == width then " " ++ show(rowsum[i]) ++ "\n" else "" endif | i in ROWS, j in COLS ] ++ [ show(colsum[j]) | j in COLS ] ++ ["\n"];