Battleship-An NP-Complete problem

Battleship-An NP-Complete problem

NP-Complete Problem:

NP stands for Non-deterministic Polynomial time.This means that the problem can be solved in Polynomial time using a Non-deterministic Turing machine. Basically, a solution has to be testable in polynomial time. If that's the case, and a known NP problem can be solved using the given problem with modified then the problem is NP complete.

The NP-class problems are divided as NP Complete and NP Hard.

NP Complete problems:
         The NP Problems (non deterministic polynomial time) are NP Complete if their solutions can be verified quickly for correctness and if the same solving algorithm used can solve all other NP problems.

NP hard problems: 
          Problems that are at least as hard as the hardest problem in NP. A problem H is said to be NP hard if there is an NP complete problem that can be solved in a polynomial time.

The main thing to take away from an NP-complete problem is that it cannot be solved in polynomial time in any known way. NP-Hard/NP-Complete are a way of showing that certain classes of problems are not solvable in realistic time.

INTRODUCTION

We study the logical puzzle of Battleships from a complexity point of view. Battleships puzzles are well playable and are regularly found in magazines, newspapers, and on the Internet. This particular formal angle learns us to appreciate the relationship between the logical solvability on the one hand and the consequences concerning computational classification on the other hand.

A Battleships puzzle consists of a puzzle-grid, a column and row tally, and a fleet containing a certain number of ships of varying length where the width of a ship is 1. The initial grid is partially filled with ship segments or water. The goal of a puzzle is to show that the provided ships can be positioned on the puzzle-grid, meeting the following four conditions:

C1: all ships in the fleet are put in the grid;

C2: the indications in the initial grid are respected;

C3: no two ships occupy adjacent (orthogonally or diagonally) squares;

C4: the number of ship segments in column (row) i is equal to the ith value of the column (row) tally.

THE DECISION PROBLEM OF BATTLESHIPS

Formally, we treat an m × n-sized Battleships puzzle (m rows and n columns) as a tuple <I,C,R,Fi>

where

I : {1,... ,m} × {1,... ,n} → {ship,water,?}

is a function that represents the initial filling of the starting grid. For instance, I(i,j) = ship denotes that cell (i,j) contains a ship segment. If I(i,j) = ?, cell (i,j)’s filling is not given: it is up to the puzzle solver to fill it with either a water or a ship segment. C is a function representing the column tally by adding a number 2 to every column i ∈ {1,... ,n}; idem for the function R representing the row tally, with respect  to j ∈ {1,... ,m}. The function F represents the fleet: there are F(k) ships of ship-length k.

If J is a function such that

J : {1,... ,m} × {1,... ,n} → {ship,water};

it is the case that I(i,j) = J(i,j), if I(i,j) 6= ?; and J meets condition C1 to C4 with respect to C, R and F, then J is a solution to the Battleships puzzle <I,C,R,F>.

It is easily obtained that Battleships is NP-complete. From the example of Bin Packing we can define the problem as follows:

Input: n positive integers a1,... ,an (the items), two integers C (the capacity)

and B (the number of bins) such that a1 + ... + an = CB

Question: can a1,... ,an be partitioned into B subsets, each of which has total sum exactly C?

We transform an instance of Bin Packing into a Battleships puzzle by reserving a vertical strip of length ai per pair of item ai and bin b ∈ {1,... ,B}. All other cells are initially filled with water. Note that this reduction assumes that the numbers a1,... ,an are represented in unary, since the strips themselves are unary representations of these numbers. This assumption does not effect the result, since the problem

Bin Packing is still NP-complete if its numbers are represented in unary. This property makes the problem strongly NP-complete. For definitions we refer to Undefined reference.

The idea is that every open strip represents the possibility of item ai being put in bin b. The item itself is represented by a ship of length ai. To make sure that every item ai is placed in only one bin, we have 1s on the relevant row tally. This also enforces that every ship of length ai is put on a strip of

exactly length ai . The reason is as follows: suppose one would put a ship of length less than ai on a strip of length ai , then at least one ship of greater length aj would have to be placed on a strip which is shorter than aj; this is evidently impossible.

This reduction proves that Battleship is NP-hard. It is easy to see that a non-deterministic guess is checked to be a solution in polynomial time. Hence Battleships is NP-complete.

Ships are deployed and ready to battle

The grid after the attack on ships

CONCLUSION

In this contribution we proved that Battleships puzzles in general cannot be solved effectively. However, Battleships puzzles are often accompanied by their solution, for players to check their solution or to get a hint on how to arrive at the solution. We showed that the fact that such puzzles are humanly solvable cannot be due to the fact that they have unique solutions. Finally, we provided hints as to how one can generate Battleships puzzles, that are both uniquely and humanly solvable.