Log in

27 May 2011 @ 12:11 am
Friday Puzzle #103 - Towed Battleships  
Last week I explored one concept of "line" in a puzzle, converting a Slitherlink from a loop to a single line. This week I want to introduce another variation that uses "lines" in a different way. In this variation on battleships, the fleet is connected from largest ship to smallest ship by a set of tow lines that can each be stretched to at most 3 cell lengths. This limits how far apart certain ships can be from each other, and introduces some more snake-like logic to this familiar puzzle type. Enjoy.

Rules: Locate the 10-ship fleet in the grid so that each segment of a ship occupies a single cell. Ships are oriented either horizontally or vertically, and do not touch each other, not even diagonally. The numbers on the right and bottom edges of the grid reveal the total number of ships segments that appear in that row or column. Additionally, all the ships in the fleet are connected by tow lines, as indicated, which can be stretched to at most 3 cell lengths.

ETA: Examples are your friends. Since the discussion took off with lots of questions, let me clarify that the example shows valid (Euclidean) distances measured from roughly the centers of the cells containing the end segments. The longest possible distance for a tow line is seen in the leftmost column. Because of the choice of a length of 3 units, you will most likely not run into a case where lines can intersect or cross over another ship that is not part of the line. The unique assignment of lines - while not a requirement of this variation - is a property of my solution and the example.

(Anonymous) on May 27th, 2011 06:01 am (UTC)
Rule clarification
Can tow lines intersect?

(This is before solving. It may become clear when solving.)
TH: pencilrpipuzzleguy on May 27th, 2011 06:16 am (UTC)
Re: Rule clarification
I'm unclear on how you calculate a tow line's length.
(Anonymous) on May 27th, 2011 08:06 am (UTC)
Re: Rule clarification
you dont have to actually calculate.Any cell that is upto 3 rows and 3 cols apart should be fine
(Anonymous) on May 27th, 2011 09:32 am (UTC)
Re: Rule clarification
I'm pretty sure the rule is Euclidean distance, and not
max(|dx|,|dy|). This allows movement of up to (3,0) and
(2,2). The puzzle solves nicely with this condition. The
actual tow lines are completely determined even without
assuming no intersection. If you allow (3,3), the tow
lines are not completely determined even if you disallow
intersection. (see the size 2 ships.) I'm not sure if the
ship placement is unique if you allow (3,3).
(Anonymous) on May 27th, 2011 09:35 am (UTC)
Re: Rule clarification
> I'm not sure if the ship placement is unique if you allow (3,3).

I found another placement. Lower the bottom 3-ship and play around
with the ships on the right.
motrismotris on May 27th, 2011 04:19 pm (UTC)
Re: Rule clarification

No, tow lines cannot intersect, although this is a practical consideration of the length I chose. The "no touching" constraint prevents ships from being far enough apart to allow this, except in configurations where you have two potential ways of drawing tow lines and one doesn't cross, or in one configuration where the lines do not actually cross but would seem to intersect. None of these extreme cases will be seen here.

Yes, a Euclidean distance of 3 is what I mean, using the center of the cell containing the end segment as where distance is measured from. So (3,0) and (0,3) are good, as is any of (2,2), (2,1), .... The example only shows valid distances, including the longest possible distance in the left-most column.
cyrebjrcyrebjr on May 28th, 2011 05:09 pm (UTC)
Re: Rule clarification
Actually, the (2,2) distances would allow tow lines to intersect. A submarine at, say, A3, a destroyer at C56, a cruiser at CDE3, and a battleship at A5678 would allow lines crossing at B4.

Anyway, I just solved the puzzle. I was having trouble yesterday, but once I saw that both the two-subs and the one-destroyer options meant the battleship couldn't be in the fourth row, it went much smoother.
(Anonymous) on May 27th, 2011 08:01 am (UTC)
A good puzzle should not allow intersections of tow lines.the intent of the variation fails ,and on top of that,from the solving perspective you have no way to start.Before that,it is not possible to construct a nice one with such lack of restriction.
Coming back to this sample,it exploits the goodness of the hybrid to a reasonabe extent.I could find an easy opening in the 5th column, and the top 2 rows of clues served as nice pointers.

(Anonymous) on May 27th, 2011 09:34 am (UTC)
I got a solution, but I feel I didn't quite "get" the puzzle.

To make my solution unique, I need to specify the rules as follows:

- Tow lines go straight between the centers of end squares of ships.
- Tow lines must not touch squares containing other ship parts, not even the corners. (In particular, a tow line can't just pass one of the rounded ends.)

It's certainly an interesting hybrid -- I'd like to see this explored further.

(Anonymous) on May 27th, 2011 09:43 am (UTC)
Re: Rules
Warning: My answers are obviously unofficial, and may be wrong.

- Tow lines go straight between the centers of end squares of ships.

I think that is clear.

- Tow lines must not touch squares containing other ship parts, not even the corners. (In particular, a tow line can't just pass one of the rounded ends.)

I think that follows directly from the limitation of distance. Unless you are also allowing larger Euclidean distances, which I don't think are allowed, or disallowing 45 degree angles relative to the (long) ships, which I think is allowed.
motrismotris on May 27th, 2011 04:18 pm (UTC)
Re: Rules
Yes, the tow lines should be viewed as originating at near the center of the cells that contain the "ends" of the ships, with center to center Euclidean distances. You can go up 3 rows (but over no columns), over 3 columns (but not change rows), or go up to 2 rows and 2 columns different before the next "end".

Because of this short length, you should not recognize any opportunities for a line to cross over another ship, or cross another line. While I wouldn't necessarily view a non-unique set of lines as a problem, in this puzzle you will get a set of lines that do not cross and can only be placed one way.
Adam R. Wood: butasanzotmeister on May 27th, 2011 04:43 pm (UTC)
Oooh, you may have given me a new idea... - ZM
motrismotris on May 27th, 2011 05:57 pm (UTC)
Glad I've finally given inspiration where normally I seem to predict/steal it.
TH: pencilrpipuzzleguy on June 1st, 2011 08:08 pm (UTC)
I solved it, but once I figured out that it was going to be 4/4/3/2 on the left, 1/2 in the middle alley, and 1/1/2 on the right, I kinda felt it out. Wondering what logical solution path I missed.
motrismotris on June 1st, 2011 09:52 pm (UTC)
Once you logic out that the big ships are on the left, you can further show that you have a horizontal 3 and 2 and a vertical 3 and 4, and then further show that the horizontal 3 has to go in just one particular row in columns 1-3 to allow the rest of the ships to follow. The logical path isn't immediate from there, but it's pretty close.