# The final showdown

I am amazed at my adviser's brilliance once again. Blackbeard's vanguard fleet was quickly sunk. And as luck would have it, the moment we finished cleaning up the mess, the scout returned with the lost scout from the first engagement. He seemed extremely excited and kept pointing to a piece of paper. Upon closer look, it is another map the scout drew.

$$\begin{array}{|c|c|c|c|c|c|c|c|l} \hline&&&&&&&&4\\ \hline&&&&&&&&2\\ \hline&&&&&&&&5\\ \hline&&&&&&&&2\\ \hline&&&&&&&&1\\ \hline&&&&&&&&6\\ \hline&&&&&&&&1\\ \hline&&&&&&&&4\\ \hline3&1&5&2&5&2&2&5 \end{array} \quad\quad \bbox[4pt,border: 1px solid black]{ \begin{array}{llc} \bf{Legend:}&\\ \hline \text{Man-of-War:}& \blacktriangleleft\blacksquare\blacksquare\blacksquare\blacktriangleright \text{or} &\blacktriangle\\ &&\blacksquare\\ &&\blacksquare\\ &&\blacksquare\\ &&\blacktriangledown\\ \hline \text{Queen Anne's Revenge:}& \blacktriangleleft\blacksquare\blacksquare\blacktriangleright \text{or} &\blacktriangle\\ &&\blacksquare\\ &&\blacksquare\\ &&\blacktriangledown\\ \hline \text{Frigate:}& \blacktriangleleft\blacksquare\blacktriangleright \text{or} &\blacktriangle\\ &&\blacksquare\\ &&\blacktriangledown\\ \hline \text{Corvette:}& \blacktriangleleft\blacktriangleright \text{or} &\blacktriangle\\ &&\blacktriangledown\\ \hline \text{Patrol Boat:}& \blacklozenge \end{array}}$$

After he finally calmed down, he told me the following

I have spotted Blackbeard himself on his Queen Anne's Revenge. However, in addition to his standard setup (1 flagship, 2 frigates, 3 corvettes, and 4 patrol boats), there is a man-of-war with 74 cannons. The size of man-of-war is bigger than even Blackbeard's flagship. Their formation is slightly different though, and they are closer together, but interestingly, none of the ships touch each other, not even diagonally. Unfortunately, since it was still dark, I wasn't able to pinpoint their exactly location, but I have drawn the map with the number of ship pieces on each column and row.

My adviser pondered at the map for a while, and then smiled.

Men, it seems like Blackbeard himself isn't aware of our presence yet, we must strike them now before dawn or we will face Blackbeard's full wrath. I have figured out their exact formation, so follow my orders and I will lead you into victory!

With a cheer from the rest of the sailors, everyone frantically prepare to sail again, leaving me behind pondering just how he managed to find out the enemy fleet formation, and why the scout keeps adding a legend but not using it.

• is diagonal considered touching? – Mekalikot Nov 4 '15 at 2:38
• @Mekalikot yes it is considered touching, I mentioned that in my first question, but forgot to include it in the subsequent, I'll edit the question now – Yaze Nov 4 '15 at 17:45

# Step 1: Find out where Man-of-War can't go.

It can't go in Column 3 or 5

It can't go in Column 8

It can't go in Row 6

That leaves the Man-of-War in Row 3.

# Solve from There:

We know that in column three and five there has to be a vertical segment of at least length two, so we can mark off a couple sea segments.

Fill in a couple segments:

Now column 8 needs to have a vertical segment of length at least two, so we can mark off a couple sea segments.

Extending with known info takes us here:

The two blanks adjacent to the Man-of-War will be a ship piece and a sea piece, leaving column eight, row three as a ship piece. Filling in knowns takes us here:

If column six, row eight is a ship then forced moves leave us with too many ships of size two or larger.

Row one cannot contain the Queen Anne's Revenge. If it did then column 8 would hold the frigate and columns one, three, and five would have to contain a frigate, two corvettes and two patrol boats. This will make the two in row 7 impossible.

Column eight cannot contain the Queen Anne's revenge. If it did then two of columns one, three, and five would contain frigates. Therefore column five, row one would be a sea segment forcing column five to contain a ship of length four, which is not possible.

Therefore column 8, row 1 is sea and forced moves lead us here:

Of the two spaces left, one must contain a frigate, and the other two patrol boats. Column three needs the frigate. This solves the puzzle.

As an aside, there are some steps that I would not have been able to do easily on paper. The hunt and check to mark off row six as impossible for the Man-of-War was a little deep. Curious to see if anyone else has any tricks.

• One step further: If the fiver is in the 1st square then the 6th square must be sea and vice versa. So the 6th segment of that row must be the rightmost square – Ivo Beckers Nov 4 '15 at 15:31
• Thanks! I've already solved the puzzle. Just don't have time to do the rest of the pictures. Will get back later. – LeppyR64 Nov 4 '15 at 15:33
• @LeppyR64 When you said column 7 needs to have vertical segment of length at least two, I think you meant column 8. But this is indeed the right approach. Looking forward to your full solution. – Yaze Nov 4 '15 at 17:58
• @LeppyR64 your logic looks good to me. Though your rows count started from bottom and count upward, i.e. row 1 is the bottom row, and row 8 is the top row. That confused me a bit. Regarding your aside, you can easily deduce the man-of-war cannot fit on the right side of row 6 as you did, and when you placed it on the left side, you'll mark off column 2 and column 7. Thus forcing the flagship in row 3. making it impossible to satisfy column 3 and column 5. I find it easier to always go for the bigger numbers first to reduce the number of levels of indirect inferences. – Yaze Nov 5 '15 at 17:58

The solution is:

┌────────────────────────┐
│ O  ~  ~  ~  Λ  ~  <  > │ 4
│ ~  ~  Λ  ~  x  ~  ~  ~ │ 2
│ O  ~  x  ~  x  ~  <  > │ 5
│ ~  ~  V  ~  V  ~  ~  ~ │ 2
│ ~  ~  ~  ~  ~  ~  ~  Λ │ 1
│ ~  <  x  x  x  >  ~  x │ 6
│ ~  ~  ~  ~  ~  ~  ~  V │ 1
│ O  ~  <  >  ~  O  ~  ~ │ 4
└────────────────────────┘
3  1  5  2  5  2  2  5


I used a computer program to solve it. I actually didn't write it myself. I knew that these kind of puzzles are sometimes called bimaru so I googled for "bimaru solver". I ended up going to https://github.com/galedric/Puzzle-Solvers/blob/master/bimaru.lua . I happened to have lua installed so I used that program and I solved the puzzle by entering:

lua bimaru.lua 4,2,5,2,1,6,1,4 3,1,5,2,5,2,2,5 1=4 2=3 3=2 4=1 5=1

• I just have to ask this now: can't you even try to do riddles without a computer program? – The Dark Truth Nov 4 '15 at 12:54
• @TheDarkTruth I do software engineering for a living and I tend to think in computer program solutions. If there is a very straightforward solution for me that doesn't need a computer of course I'll use that but to me it wasn't. Also, the thing a computer program does can actually be done by hand, it's just much faster. – Ivo Beckers Nov 4 '15 at 15:23
• @Ivo Beckers To find a compromise: I am sure you do not simply let your program brute force every possible solution but rather add some constraints or similar kinks to your program which you thought about yourself to make it run faster. It might be a good idea to add those kinds of constraints to your solutions in the future. – The Dark Truth Nov 4 '15 at 15:45
• @Ivo Beckers This is indeed the correct solution, but alas, my trusty adviser does not have access to such technology, hence it didn't quite answer "how did he managed to find out the enemy fleet formation". Nonetheless, well done on writing the program to solve it, and my adviser is very interested in this "computer" thing. – Yaze Nov 4 '15 at 17:49
• @Yaze, I gave some extra details of the program I used – Ivo Beckers Nov 5 '15 at 7:44