1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 | % % 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. |