This is the forty seventh part of the ILP series. For your convenience you can find other parts in the table of contents in Part 1 – Boolean algebra

Today we are going to solve Battleship puzzle. It is very similar to nonograms which we already solved so let’s start with the code:

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 |
using System; using System.Linq; using CplexMilpManager.Implementation; using MilpManager.Abstraction; using MilpManager.Implementation; namespace BattleshipPuzzle { class Program { static void Main() { var solver = new CplexMilpSolver(10); int[] columns = { 1, 2, 1, 3, 2, 2, 3, 1, 5, 0 }; int[] rows = { 3, 2, 2, 4, 2, 1, 1, 2, 3, 0 }; // ship length - ships count Tuple< int, int>[] ships = { Tuple.Create(4, 1), Tuple.Create(3, 2), Tuple.Create(2, 3), Tuple.Create(1, 4) }; var variables = Enumerable.Range(0, rows.Length) .Select( r => Enumerable.Range(0, columns.Length).Select(column => solver.CreateAnonymous(Domain.BinaryInteger)).ToArray()) .ToArray(); foreach (var tuple in ships) { int shipLength = tuple.Item1; int shipCount = tuple.Item2; var place = solver.FromConstant(0); for (int row = 0; row < rows.Length; ++row) { for (int column = 0; column < columns.Length; ++column) { // Horizontal if (column + shipLength <= columns.Length) { var shipSum = solver.Operation(OperationType.Addition, Enumerable.Range(0, shipLength).Select(i => variables[row][column + i]).ToArray()); var neighbourSum = solver.Operation(OperationType.Addition, new[] {-1, 1}.SelectMany(rowDiff => Enumerable.Range(-1, shipLength + 2).Select(columnDiff => Tuple.Create(rowDiff, columnDiff))) .Concat(new [] {Tuple.Create(0, -1), Tuple.Create(0, shipLength)}) .Select(t => Tuple.Create(row + t.Item1, column + t.Item2)) .Where(t => t.Item1 >= 0 && t.Item1 < rows.Length && t.Item2 >= 0 && t.Item2 < columns.Length) .Select(t => variables[t.Item1][t.Item2]).ToArray()); place = place.Operation(OperationType.Addition, shipSum.Operation(OperationType.IsEqual, solver.FromConstant(shipLength)) .Operation(OperationType.Conjunction, neighbourSum.Operation(OperationType.IsEqual, solver.FromConstant(0)))); } if (shipLength > 1 && row + shipLength <= rows.Length) { // Vertical var shipSum = solver.Operation(OperationType.Addition, Enumerable.Range(0, shipLength).Select(i => variables[row + i][column]).ToArray()); var neighbourSum = solver.Operation(OperationType.Addition, new[] { -1, 1 }.SelectMany(columnDiff => Enumerable.Range(-1, shipLength + 2).Select(rowDiff => Tuple.Create(rowDiff, columnDiff))) .Concat(new[] { Tuple.Create(-1, 0), Tuple.Create(shipLength, 0) }) .Select(t => Tuple.Create(row + t.Item1, column + t.Item2)) .Where(t => t.Item1 >= 0 && t.Item1 < rows.Length && t.Item2 >= 0 && t.Item2 < columns.Length) .Select(t => variables[t.Item1][t.Item2]).ToArray()); place = place.Operation(OperationType.Addition, shipSum.Operation(OperationType.IsEqual, solver.FromConstant(shipLength)) .Operation(OperationType.Conjunction, neighbourSum.Operation(OperationType.IsEqual, solver.FromConstant(0)))); } } } place.Set(ConstraintType.Equal, solver.FromConstant(shipCount)); } for (int column = 0; column < columns.Length; ++column) { solver.Operation(OperationType.Addition, Enumerable.Range(0, rows.Length).Select(row => variables[row][column]).ToArray()) .Set(ConstraintType.Equal, solver.FromConstant(columns[column])); } for (int row = 0; row < rows.Length; ++row) { solver.Operation(OperationType.Addition, Enumerable.Range(0, columns.Length).Select(column => variables[row][column]).ToArray()) .Set(ConstraintType.Equal, solver.FromConstant(rows[row])); } solver.AddGoal("Goal", solver.FromConstant(1)); solver.Solve(); Console.Write("+"); Console.Write(string.Join("", Enumerable.Range(0, columns.Length).Select(_ => "-"))); Console.WriteLine("+"); for (int row = 0; row < rows.Length; ++row) { Console.Write("|"); for (int column = 0; column < columns.Length; ++column) { Console.Write(variables[row][column].GetValue() >= 0.5 ? "X" : "."); } Console.Write("|"); Console.WriteLine(rows[row]); } Console.Write("+"); Console.Write(string.Join("", Enumerable.Range(0, columns.Length).Select(_ => "-"))); Console.WriteLine("+"); Console.Write(" "); foreach (var column in columns) { Console.Write(column); } Console.WriteLine(""); } } } |

Application is pretty obvious. First, we create collections of numbers representing how many fields are occupied in row or column. Next, we crate tuples describing ships: first tuple element indicates ship length (or type), second element indicates how many ships of that type we need to place on the board.

Next, for every field we create a binary variable indicating whether that field is occupied or not.

Next, we want to place each type of ships on the board. We iterate over types, over rows, and over columns. For every field we check whether it is theoretically possible to place ship horizontally (so leftmost piece of ship is in the current field). We simply sum variables which would create the ship and make sure that neighboring variables are zero. For vertical assignment we perform similar checks. Finally, we make sure that there are enough ships of the type on the board.

Next, we add two loops to make sure that number of marked fields matches board requirements (defined at the beginning). Finally, we solve the problem and print the result. That’s all.