ILP Part 47 — Battleship puzzle

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:

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("");
		}
	}
}

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 = {

};

int[] rows = {

};

// 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.