1
$\begingroup$

I have been doing some research on the reduction of Battleship to bin-packing, but I do not completely understand the input to the problem from this academic paper: http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabilityProblem.pdf The paper states that the input would be an array of positive integers (the items), C (an integer capacity), and B (an integer number of subsets). The question that is posed then becomes: can the items be partitioned into B subsets, each of which has total capacity C? How is this even guaranteed to be possible? For example, if the total size of 6 ships is 19, it seems actually impossible to partition them according to the requirements of the problem? Maybe I am just understanding the reduction wrong. Any ideas?

$\endgroup$
  • $\begingroup$ Welcome to CS.SE! We expect references to fulfill the minimal scholarly requirements and be as robust over time as possible: in particular, they should normally include the title, authors, and where published, in addition to the link. Please take some time to improve your post in this regard. We have collected some advice here. Thank you! $\endgroup$ – D.W. Apr 28 '16 at 4:39
1
$\begingroup$

The idea is to reduce the bin packing problem to battleship, not the other way around.

The variant of bin packing they use in the paper is to decide if it is possible to partition $n$ numbers into $B$ subsets (the bins) so that the numbers into each subset add to a quantity $C$.

Example:

Input:

The set $\{2,3,5\}$ , $B=2$ and $C=5$

Possible solution:

Two subsets $1$ and $2$:

$1 = \{2,3\}$

$2 = \{5\}$

This problem can be reduced to battleships in the following way:

Create a board of width $B \times 2$ and height $S + n$ , where $n$ is the cardinality of the subset we are going to partition and $S$ is the sum of all the elements of the multiset we want to partition.

Then for each pair of columns that belong to each bin, we set the number that the first column should ammount to $0$ and the other one to $C$. These numbers are the number of pieces of a ship that there should be in each column.

For the rows: For each number $a_i$ that belongs to the multiset that we want to partition, we have a separator row with a value of $0$ and $a_i$ rows with a value of $1$. These numbers make reference to the number of boat pieces that there should be in each row. For each row that belongs to a number, we have only a ship piece because we want each of the $a_i$ numbers to be covered by a single ship of that size.

So in one column of each column pair we will have a separator row and a vertical strip of $a_i$ rows of height for each number of the multiset we have to partition. We can cover that strip with a ship or not, but we have to cover enough strips of a column so that the number of ship pieces of that column adds to exactly $C$.

Because a picture is worth a thousand words i made a picture of a solved example board that we obtain by reducing an instance of bin packing to battleship

The instance of bin packing that i'm going to use as an example is:

The set $\{2,3,5\}$.

$B=2$

$C=5$

The shaded squares are squares that are occupied by a boat.

Less ugly drawing

Thanks for bringing my attention to this problem, i didn't know it.

Hope this is helpful.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.