Solution: Battleships

Answer: NAVAL COMMANDER

Written by Jonathan

The first thing to notice is that we have a grid consisting of minsweeper-style numbers on the inside of the grid, and battleship-style numbers and diagrams on the outside of the grid. This indicates to us that this logic puzzle is both a minesweeper and battleships puzzle. However, no rules are given other than the flavor text, which tells us that the “numbers do not differentiate between friend and foe”. Therefore, all the numbers in the grid indicate a cell that is either occupied by a mine or segment of a ship.

With that, the first step is to solve the logic puzzle to obtain the occupied cells (since at this point, the numbers are insufficient to distinguish between friend and foe), which are indicated in yellow. It will turn out that in this first phase, the most useful tool is the standard rules of minesweeper and the row and column constraints. Doing so, we obtain a partial solution to the grid puzzle. A sample solve path is given in Appendix 1 below. We are able to determine all the occupied cells, but we are not yet able to distinguish between whether they are mines or ships yet!

At this point, we turn to the word clues. Given the theme of the puzzle, we might realize that each of these words contains the string “MINE”.

Once the words are found, one might notice that the total number of letters (treating “MINE”s as one space) is equal to the number of cells in the grid! This indicates to us that we should insert the words into the grid, with “MINE”s in the spaces where we have identified a mine. It is also at this point where the standard battleships rules become useful. In particular, battleships follow standard battleship rules (battleships cannot touch, not even diagonally). Doing so we obtain the following grid. See Appendix 2 for a sample solve path of this part.

N	O	MINE	E	D	O	P	A	MINE	3
A	N	T	I	H	I	S	T	A	1
MINE	S	MINE	R	V	A	L	U	MINE	6
S	C	E	N	C	E	A	MINE	B	2
R	O	MINE	I	M	MINE	N	T	E	4
MINE	M	E	X	A	MINE	R	D	O	4
MINE	E	R	I	N	G	MINE	S	T	3
R	O	N	E	D	E	T	E	R	3
MINE	D	P	R	E	E	MINE	N	T	2
6	3	3	0	5	3	3	2	3

Once filled, we read off the letters indicated by the friendly elements (the battleships), which gives the answer, NAVAL COMMANDER.

Author's Notes

This was the last logic puzzle constructed for this hunt. I think this puzzle really pushed the idea of a logic puzzle since a year ago when I set Roller Coasters. This logic puzzle combined 2 logic puzzle variants, used battleships constraints in a relatively unconventional way, and included an English logic portion at the end as well.

[aki's comments:] An earlier version of this logic puzzle omitted the given ship and water in B4 and I9 respectively. It was significantly harder than the current version because the logic puzzle could not be completed without the insertion of the words. I liked that version better.

Appendix 1

Given that all the numbers indicate both battleships and mines, we can only make limited inferences regarding which cells contain mines and ships. In general, we will only be sure if a cell contains something at all, but not what it is. We will color cells that contain nothing in black, and cells that contain something in yellow. For convenience we also label columns with letters and rows with numbers for readability as shown below.

• Firstly, we can black out col D as we know it has no objects.
• Start by looking at row 1. To satisfy the red 3 in B1 and blue 1 in H1, 4 objects must be placed around them in the top 2 rows, that is, in A1:C2 and G1:I2. These 4 objects completely satisfy the row 1 and 2 constraints, thus rows 1 and 2 must be empty in cols E and F.
• Now consider the red 3 in B1. Due to the the constraint on row 2, at most 1 object can be placed in A2:C2. However, there are only 2 other cells that can be used to satisfy the red 3, A1 and C1. This means that they must both be occupied, and the 1 object in row 2 must be in one of A2:C2. We can thus also black out the remainder of row 2.
• Look at the top right corner. The blue 1 requires exactly one object in the squares G1 and I1, which also counts towards the red 3. This means there must only be 2 objects in G3:I3. This leaves 4 more undetermined cells in row 3, with 4 more objects to be placed. Thus the rest of row 3 must be occupied.

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

• Now consider the right end of row 5. The blue 1 in I5 indicates that there must be exactly one object in its H4:I6. However, this object will also satisfy the blue 1 to its left, and therefore G4 and G6 must be empty.
• We can now consider the red 3 in G5. We already know there can be at most one object in H4:H6, but this leaves at least two more objects to place in F5 and F6 to satisfy this red 3. This tells us both F5 and F6 must be occupied, and that there is one object in H4:H6. Thus, the two blue 1's are satisfied by this object, and I4:I6 are empty.
• Now the constraint of col F is satisfied, and we can black out the remainder of its cells.
• Now consider the purple 4 in F8. There are 4 objects to place and 4 remaining undetermined cells touching it, which means they all contain an object.

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

• Now we consider the red 3 in H9. Based on this, we know that H8 and I8 are both occupied. This entry satisfies the red 3 in G8, and therefore H7 must be empty. Now, considering col H, we know there must be one object in H4:H6. This means H3 must be empty.
• To satisfy the constraint on row 3, the remaining cells must be occupied.
• The constraint on col G is complete. G1 must be empty, and by the constraint on row 1, I1 must be occupied.
• The constrint on col I is complete. I7 must be empty.

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

• Consider the red 3 in D5. Due to this red 3 and the col E constraint, we know C4:C6 contains exactly one object. This completes the col C constraint, and so C8:C9 must be empty.
• Now consider rows 4-6. There are a total of 10 objects in these rows, 2 of which we have found and 1 of which is given. For the undetermined cells, we know H4:H6 has exactly 1 object (due to blue 1 in H5), C4:E6 has exactly 3 objects (due to red 3 in D5), and A5:B5 has exactly 1 object (due to red 3 in A4). This leaves 2 objects unaccounted for, and the two cells in A6:B6 undetermined. Thus, these two cells must be occupied.
• Now the blue 1 in C7 is satisfied, so we can black out all undetermined squares it touches.
• Now, to satisfy the constraint on row 7, A7 must be occupied.

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

• At this point, we notice that the constraint on row 8 is satisfied, so A8 must be empty.
• On the other hand, the constraint on row 9 implies that A9 must be occupied.
• Given that B4 is the end of a ship, we know that minimally, B5 must also be occupied. This completes the constraint on col B, and thus, B2 is unoccupied. This also satisfies the red 3 in A4, which implies that A5 must be empty.
• This leaves A2 as the cell to be occupied to satisfy the red 3 in B1 (and the row 2 and col A constraints).

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

• Due to the constraint in row 5, we have 2 undetermined cells which must both be occupied. This completes the constraint on col C, which means C4 is empty.
• Finally, we consider the constraint that a length 4 ship needs to fit. At this point, the grid does not contain a contiguous series of objects of length 4, and the only way to create one is to fill cell E6. This means that E4 and H6 are empty, and H4 is occupied.

	A	B	C	D	E	F	G	H	I
1										3
2										1
3										6
4										2
5										4
6										4
7										3
8										3
9										2
	6	3	3	0	5	3	3	2	3

This completes the first part of the logic puzzle.

Appendix 2

Firstly, we should work towards deducing as much as possible regarding which cells are mines and which cells are ships, to aid us with inserting the words into the right places. For readability we will write words as the minimum prefix required to identify them. Furthermore, [numbers in square brackets] indicate that number of undetermined letters. [?] indicates any number of letters. It is also important to remember that every word must lay over exactly one mine. Note that we are expecting to see 14 mines. We will recolor all black cells to white (to avoid confusion with the black color of the ship cells). Let's begin.

• We begin by observing that there are no length 1 ships, therefore all isolated cells must be mines. A3 must also be a mine, as it touches the ship part in B4. In total, this places 9 mines.
• Next we notice that there is only one contiguous sequence of occupied cells of length 4 (which we constructed earlier), that is, E5:E8. This must be our ship of length 4. Further, all occupied cells touching it (that is, F5 and F6) cannot be ships due to the Battleships rule, and thus must be mines. This places 2 more mines.
• Now notice we need to place 2 ships of length 3 and 2 ships of length 2. There are only 4 more distinct regions that can each only contain one ship (A1:A2, E3:G3, A4:C7 and H8:I8). This tells us that A1:A2 and H8:I8 must be the ships of length 2, and the other two regions contain the ships of length 3. This completes the placement of all the ships.

	A	B	C	D	E	F	G	H	I
1										3		Word Bank
2										1		AMINE					EXAMINER
3										6		ANTIHISTAMINES					IMMINENT
4										2		BROMINE					LUMINESCENCE
5										4		DETERMINED					MINERVA
6										4		DOMINEERING					MINESTRONE
7										3		DOPAMINE					NOMINEE
8										3		EMINEM					PREEMINENT
9										2
	6	3	3	0	5	3	3	2	3

• We can now start inserting words into the grid. The last word must take the form [?]MINE[2], so the only words possible are I and P. However, assume for contradiction that it is I, which starts on E9. Then the word preceding it must take the form [?]MINE[3]. The only word of this form is MINER, but this forces the word preceding it to take the form [?]MINE[11], which does not exist. This is a contradiction. Thus, the last word must be P, starting at C9.
• Continuing backwards, the previous word must take the form [?]MINE[1]. This opens up many possibilites; however, we can also consider the two mines in G7 and A9, which belong to adjacent words. There is a distance of 11 cells between them, which means the two words must take the forms [?]MINE[x] and [11-x]MINE[?] respectively. However, all the words in the word bank have x ≤ 6, therefore, 11-x ≥ 5. The only two words that are of the form [≥ 5]MINE[1] are AN and DE. It is possible to show that the word must be DE, so we can fill it in starting at E8.
• If the word starting at A8 is AN, the word before that must take the form [?]MINE[2], and so must be I starting at E7. This means the one before that must take the form [?]MINE[3], and must therefore be MINER starting at A7. However, this means the word before that must also take the form [?]MINE[3]. However at this point there are no more such words, a contradiction.
• The word before DE now has to take the form [?]MINE[6], which can be L or MINES. However, assume for contradiction that the word is L, starting at E7. This leads to two possibilities. If A7 is a ship, the preceding word must take the form [?]MINE[7], which does not exist. If A7 is a mine, then the preceding word must take the form [?]MINE[3]. The only word of this form is MINER. But then, the word preceding MINER must also take the form [?]MINE[3], and there are no more words that can be used. Therefore, we are forced to pick MINES, starting at G7.
• Proceeding backwards, we are looking for a word of the form [?]MINE[5]. The only word of this form is DOM, which we can insert starting at H6.

A

B

C

D

E

F

G

H

I

1

3

Word Bank

2

1

AMINE

EXAMINER

3

6

ANTIHISTAMINES

IMMINENT

4

2

BROMINE

LUMINESCENCE

5

4

DETERMINED

MINERVA

6

D

O

4

DOMINEERING

MINESTRONE

7

MINE

E

R

I

N

G

MINE

S

T

3

DOPAMINE

NOMINEE

8

R

O

N

E

D

E

T

E

R

3

EMINEM

PREEMINENT

9

MINE

D

P

R

E

E

MINE

N

T

2

6

3

3

0

5

3

3

2

3

• Now, let us work forward from the start. The first word must take the form [2]MINE[?]. The only words satisfying this now are I, L and N. We will find that the only fills for the first row are N + DOP or I + B. In either case, it completes only the entirety of row 1.
  • The first word cannot be L, because the ending of the word will run into the next mine.
  • If the first word is N, the word after it must take the form [4]MINE[?]. The only word matching this is DOP, which completes the row.
  • If the first word is I, the word after it must take the form [3]MINE[?]. At this point it is possibe to use either B or EX. However, EX will not work because it will force the next word to start at B2; then, depending on whether row 3 column 1 is a mine or ship, the next word either has to take the form [8]MINE[?] or [10]MINE[?], both of which do not exist.
• This means the third word must start at A2. Now consider specifically the word AN. To fit this word, we require a continuous sequence of non-mines of at least length 9, for its prefix. The only possible placement is in between the mines in I1 and A3, which tells us that AN must precisely be the third word we are looking for! Therefore, we should place AN starting at A2.
• The word after AN must start in C3, which is itself a mine! The only word that has the form MINE[?] is MINER, which we can now place.
• After that, the next word must take the form [2]MINE[?]. This could be I, L or N. However, if it was I or N, then the word after it must take the forms [5]MINE[?] or [6]MINE[?], both of which we do not have. Therefore the next word must be L.

A

B

C

D

E

F

G

H

I

1

3

Word Bank

2

A

N

T

I

H

I

S

T

A

1

AMINE

EXAMINER

3

MINE

S

MINE

R

V

A

L

U

MINE

6

ANTIHISTAMINES

IMMINENT

4

S

C

E

N

C

E

2

BROMINE

LUMINESCENCE

5

4

DETERMINED

MINERVA

6

D

O

4

DOMINEERING

MINESTRONE

7

MINE

E

R

I

N

G

MINE

S

T

3

DOPAMINE

NOMINEE

8

R

O

N

E

D

E

T

E

R

3

EMINEM

PREEMINENT

9

MINE

D

P

R

E

E

MINE

N

T

2

6

3

3

0

5

3

3

2

3

• At this point, consider the word DOP. It requires a continuous sequence of 4 non-mine cells for its prefix, but there are only two such sequences, that is, D1:H1 and B6:E6. However, DOP cannot be placed in B6:E6 as this would leave G6 blank, which is not allowed. Therefore, we now know the first row must be N + DOP.
• Now let us consider what words can be placed over the mine in F6. It must take the form [?]MINE[1], which can only be EM or EX. If we picked EM starting at E6, the word preceding it must take the form [?]MINE[3], which we do not have any of. Thus, the word must be EX, starting at C6.
• The word preceding it must take the form [?]MINE[1], which now has to be EM.
• The word preceding that must take the form [?]MINE[2], which has to then be I.
• Finally, the word placed over the mine in H4 must take the form [1]MINE[?], which must be AM, leaving the final spot in the middle for B.

A

B

C

D

E

F

G

H

I

1

N

O

MINE

E

D

O

P

A

MINE

3

Word Bank

2

A

N

T

I

H

I

S

T

A

1

AMINE

EXAMINER

3

MINE

S

MINE

R

V

A

L

U

MINE

6

ANTIHISTAMINES

IMMINENT

4

S

C

E

N

C

E

A

MINE

B

2

BROMINE

LUMINESCENCE

5

R

O

MINE

I

M

MINE

N

T

E

4

DETERMINED

MINERVA

6

MINE

M

E

X

A

MINE

R

D

O

4

DOMINEERING

MINESTRONE

7

MINE

E

R

I

N

G

MINE

S

T

3

DOPAMINE

NOMINEE

8

R

O

N

E

D

E

T

E

R

3

EMINEM

PREEMINENT

9

MINE

D

P

R

E

E

MINE

N

T

2

6

3

3

0

5

3

3

2

3

This completes the logic puzzle.