Log in

10 August 2006 @ 01:45 pm
Battleship Sudoku!  
On rare occasions, as with the magical combination of chocolate and peanut butter, two satisfying individual things come together to make something that not only maintains the feel of the original members, but adds in a little something extra as well.

For the last week, I've had two puzzle ideas stuck in my head since I finished the Paint By Numbers Sudoku. One of them was to finally do a Battleship Sudoku in a quality way, and that is the focus of this entry.

There are two ways I can imagine making such a puzzle. The first is to try to pack in ships to fill in some fixed number of squares in each row/box/column and then put numbers in the remaining squares. It turns out that this route is a little less interesting but I went forward on it anyway. I stumbled a little at the start, struggling to find some fleet of ships that would reasonably fit a grid. Its hard to pack (possibly impossible) a fleet with say 3 cruisers, 5 destroyers, and 8 battleships (27 total boat parts) into a sudoku grid using standard battleship packing rules. I decided though I could use a Mini-Fleet of 5 destroyers (2 unit ships) and 8 submarines (1 unit ships) for 18 total boat parts, and then give clues on the side of the grid as to how many ships can be seen in each direction. In these puzzles you must place 2 boat units in each row/box/column following battleship touching rules (edit: that is to say, ships cannot be immediately adjacent to each other, not even diagonally) with the numbers 1 through 7 in the remaining empty squares according to standard sudoku rules. Its an ok puzzle type, but it does not feel as much like a battleships puzzle as the second version below. My favorite of this type, which I'll call "Mini-Fleet Sudoku", is by far the rightmost puzzle.

(Note: All given numbers can be consider "sea" spaces and do not contain ships).

The other way to imagine doing a battleship sudoku is to fit a standard fleet of ships into the grid, but number the pieces of these ships so that they end up being part of a standard sudoku grid as well. The few givens that would be placed in the puzzle would be designed at times to help steer boats into particular spots/orientations, resolve non-unique boat placements, etc. Combining both battleship strategies and sudoku logic is therefore essential with this type. I came up with a few themed logical steps I wanted to try to embed in each puzzle, and made a few puzzles of varying difficulty that contained these steps. I'm really proud of this variation and hope the three that follow give you a sense of what the puzzle can be like. They are arranged in apparent increasing difficulty from left to right. I plan on making several more in the future.

To fully explain what your solution will look like: you will have a valid 9x9 sudoku grid with the digits 1 through 9 in each row/box/column. You will also have a fully "docked" fleet of battleships with the numbers on the ships matching exactly the numbers in the sudoku grid, and with boat segments obeying the outside constraints given for the puzzle. I would really appreciate your opinion on these battleship sudoku variants, but to me, the latter example comes pretty close to being like chocolate and peanut butter. They still feel like sudoku and still feel like battleships, but need a little bit of new logic from the other puzzle to get all the way through. From now on I will call this a "Battleship Sudoku" in contrast to the earlier "Mini-Fleet Sudoku". Enjoy!

(Note: Again, all given numbers in the grid can be considered "sea" spaces and do not contain ships).

(Anonymous) on August 12th, 2006 12:02 am (UTC)
I started these yesterday and wanted to make sure this post didn't remain commentless for too long, but also wanted to finish them all beforehand..

Now that I have, these are really really nice variations. I enjoyed the Mini-Fleet, the 'sparse' 7x7 sudoku aspect is a little different feel, kind of like the "End View" puzzle that I really like. I'm not sure I liked it any less than Battleship, but it seems like Battleship might have a little more flexibility in terms of solving methods required, and I can't think of any reason this couldn't fly as an "official" sudoku variation and become more popular and widespread.. This combination of the two puzzles feels so natural, I'm surprised it hasn't shown up in a WPC puzzle or something like that.

Construction-wise, really impressive. I can't even imagine the process of putting together puzzles like these, especially coming up with a particular solving trick and then trying to install it along the way. As a frequent Nikoli solver, I always look for and really appreciate the little flourishes in given-digit placements, whether symmetry, eye-popping designs, or sequencing as in the 3 Battleships puzzles.. It's funny how an aspect like the 1-9 exploded box or 1-9 line in the first two really has little effect on the solving of the puzzle, but almost gives me as much enjoyment as the solve itself. Kind of like an intricate presentation of some fancy food, I admire an attractive unsolved grid for a few moments and get excited about diving into it before eventually doing so. (And imagine the person crafting it, instead of someone pressing 'go' on an algorithm and spitting out 300 blah puzzles in 500 msec)

During the solving I particularly appreciated that they were all solvable using incremental logical steps, even if I got stuck for a while looking for some of the steps. When GAMES first debuted their Battleships puzzles I ate them up, but I got tired of the multi-stage T&E that seemed to be more frequently required by the difficult puzzles. From the nature of the vanilla Battleships puzzle, I understand the need for multiple ambiguities in placements, and I like trying all 4 possible placements of a large ship, as long as I can find the illegality in a few steps, or in my mind.. When each placement forks off another few possibilities for other ships, and eventually only creates a problem on the last few submarine placements, it feels more like rote than solving. But these were very elegantly designed, and extremely enjoyable.

Thanks again for sharing your efforts with everyone! These nifty puzzles you've been churning out recently are really impressive.

motrismotris on August 12th, 2006 12:58 am (UTC)
Re: Fantastic!
Thanks very much for your comments. I remember, as a kid, before I could finish all the crosswords and such in GAMES, absolutely loving the Battleships. I'm pretty sure they were my favorite thing in the magazine for a long long time. I'm sure if I searched the back issues of GWoP and GAMES at home from when I was 10-14 I'd find one page completely solved, and most other pages pretty much blank. Somehow, the magic has faded a little over the years (although not as much as the paint-by-numbers), but battleships is one of the first puzzles I remember absolutely loving.

While the Mini-Fleet variant works - its kind of a twisted 0,0,1-7 sudoku - it doesn't capture the fun magic of Battleships as much as the second one does. I particularly like how the second variant adds in some little twists into the battleship formula including "what direction" for a ship, and also "what ship" for ships of multiple types. Some of the "Word" battleships at WPCs had a little of this flavor, but I've never liked how they were clued compared to how natural it feels here. I mean, what is a cruiser here with two possible orientations but a locked pair in a sudoku puzzle? Admittedly, the first of the Battleship puzzles has a pretty easily defined set of ships, but you're solving strategy goes down the path of where must the battleship be (which uses the numbers), which of the cruisers is which (again using the numbers), where does each destroyer go, etc., and while it is not very hard logic, it is very satisfying to do. I actually started the puzzle with just parked ships and the 1-9 that you see along the 3 "0" rows and tried to define ships nicely. While the sudoku would not end up being uniquely defined with just those 9 givens and the ships, I only needed to add in a couple extra digits (which, as a repeated and mirrored 3 and 6 have nice added symmetry). The second started with, again, a set of parked ships (without numbers) and the row of 1-9 in the middle. Unfortunately, here I could not add in just a couple extra digits without breaking symmetry. The last has a little of this flavor (you can see an embedded 1-3 and 4-6 column hit by a 7/8 row, and then the extra 8 digits are almost another set of 1-8), but this was something I tried to do when making them.

While I've written a bunch of different kinds of "new" puzzles recently, I really like this last battleships variation for some reason, more than any other replicable puzzle type I made (I also like my US States sudoku, but that's kind of a one and done - I could fit some other shapes together, but it would never work as well as that first example). The Battleship Sudoku combination feels so natural, and I think a whole lot more can be embedded in the solving path. I can give "ship parts" with or without numbers as clues in the grid. I could give the straight numbers as in these puzzles, but not say whether they are part of ships or not (there is no reason all the numbers have to be seas, I just started out thinking this way). I can limit the battleship row and column information as is sometimes seen with battleships. I can do the "super-big" fleet variation and maybe get away with no numbers given in the puzzle as having 4 battleships on down to 1 submarine now gives 30 digits from the ships which should be plenty for a unique sudoku. And likely more. While I have one other tantalizing idea to try out, I really want to give more battleship sudoku a try.

Maelstrommlstrm on August 14th, 2006 04:43 am (UTC)
Great stuff. I agree, Mini-Fleets has its moments, but once you've figured out the ground rules, it's pretty easy. (Except you did manage to make #3 tough, and I like that.)

The Battleship variation rocks and I hope to see many more where that came from.

BTW, have you considered submitting any of these to Games or GWoP?
(Anonymous) on August 14th, 2006 03:32 pm (UTC)
It took me forever to write puzzle #3 (actually the first Mini-Fleets I wrote) as it is difficult to make a hard version. I really liked how that result finally flowed - not all ship placements were trivial without solving parts of the sudoku, and even then the top part was a little tricky - which is why I almost had to put it up with the others. It does feel though that "Mini-Fleets" runs out of variety pretty fast.

The second version has a lot more potential interplay with numbers and ship placements and likely a lot more variety. My examples are far too easy on the battleship placement end, but I wanted to focus mainly on how placing ships would be defined by the sudoku numbers and not try to nest too many complex puzzle elements in my first go at it. I will definitely be writing more of the second type - and we'll see on the publishing end :). The good or bad may be that you'll have to catch my puzzles elsewhere and not get them for free on the blog.
(Anonymous) on November 10th, 2006 08:58 am (UTC)
Solution to the fourth?
motrismotris on November 10th, 2006 05:27 pm (UTC)
I'm a bit behind on posting solutions to these puzzles on my puzzle page but I'll get these there eventually. If by fourth you mean the first of the second type, the grid itself is this:


you can play "search a ship" from there and find all the boats.
rikagrobler on June 19th, 2009 11:19 am (UTC)
Battleship Sudoku
These are fantastic, especially the second type. Are there more available?
motrismotris on June 19th, 2009 05:03 pm (UTC)
Re: Battleship Sudoku
Only a whole book of them. :) Battleship Sudoku
rikagrobler on June 20th, 2009 10:44 am (UTC)
Re: Battleship Sudoku
Unfortunately, I live in South Africa and Amazon does not deliver here. But I have a daughter in England who may be able to get me one. I have been doing killer sudoku's but this is a new challenge. :)