Friday Puzzle #109 - Better Know your Battleships
This is part 3 of a "Better Know the USPC" preview series. The United States Puzzle Championship is scheduled for August 27th, 1PM EDT.
Type: Battleships
USPC History: The classic form has appeared every year from 1999 to 2010 (twice in 1999), and has been the first puzzle since the first "Google" form of the championship in 2003, continuing in that spot in the current post-Google era. Variations have appeared several times including Digital Battleships (2000, 2001), Retrograde Battleships (2001), and Path Battleships (2002). Battleships was also one quarter of the Four Square puzzles in 2009, 2010.
The most frequent contributor of the lead battleships puzzle is Moshe Rubin, who used to be a GAMES contributing editor for the Battleships column before partnering with Conceptis many years ago to sell his computer-generated puzzles under their brand name. Other contributors have included the Dutch publisher Puzzelsport in the early years, Erich Friedman for some of the variants, and Jay Baxter one year apparently as a gift for dad that ended up on the USPC.
Notation tips: Battleships are a fiddly puzzle type. Even if it weren't the case that over 95+% of the Battleships puzzles you encounter are computer-generated, you'd probably still find that most of them fall from trial and error approaches more quickly than strict logic, most often from finding contradictions in limited placement options of large ships.
When solving a battleships puzzle, I try to use a 2-way notation system to keep track of things I know for sure, and things I'm more speculative about at that moment. When marking ships, I'll shade in dark anything I got from logic/starting conditions. When I'm on a trial/error pathway, I'll simply outline the ships but leave them unshaded, so I know what to fully erase if things don't work out. Since you almost always start such a pathway by placing a 4- or 3-unit ship, I tend to remember what was the first part of the guess. But you might find it wise to note this to yourself if you lack that kind of short-term memory.
With seas, I draw full lines to mark out unused rows/columns and also make "loops" around the parts of ships I can immediately eliminate, often U shapes but sometimes full boxes. If I can't draw a line as I only have an isolated cell as a sea cell, I'll put a dot. Along speculative paths, I'll draw lighter lines (which is most efficient for me) or, once the battle of constant erasing is going against me, slashed cells.
USPC Battleship puzzles are rarely too hard, so I don't have a real battleground of a past paper to show you. Or any puzzle I've had to guess at. But this is my solved copy from 2003 for a nice 12 points per minute to start the test.
Strategies: Aside from the obvious steps, battleships puzzles get constrained by a combination of "nearly empty" and "nearly full" spaces. A "nearly empty" row is one that can take just one more ship segment anywhere in it. A "nearly full" row is one that can only accept one more unmarked sea segment with everything else having to be a ship. You may not know where the ships go in the "nearly full" row, but if you ever mark one more sea in that row you would know every such placement. The value of "nearly full" rows is that placements elsewhere in the grid often directly affect them, and can be ruled out if they make completing that row impossible. Where a "nearly empty" row intersects a "nearly full" row, you can almost always mark some cells 1 away from the nearly full row as seas because of this kind of thinking. But more distant placements will have the same effect. Learning these interactions is how to actually get good at solving battleships puzzles by logic, as you can see the contradictions 2 or 3 steps down the line that most often get encountered by trial-and-error. Extremes are also key to observe. You cannot have more than 8 cells filled in any row in a standard 10x10 puzzle (and there aren't many ways to do this but you must use either the 4-cell battleship or both 3-cell cruisers). But similarly you can't easily have as many as 9 or 10 cells filled in adjacent rows. If you see large numbers of ships left to place in close spots or, considering all the marked seas, a lot of cells to fill in adjacent rows that don't have a lot of spaces left, this is where you need to focus your attention.
But that is all probably higher-level thinking than you'll need to solve the USPC battleship puzzle, so the main thing to learn to really get started is how to be meticulous at the bookkeeping of cells. Anytime a cell is marked as a ship segment, make sure you've marked out all the cells that cannot be ships. This is at least the 4 diagonally adjacent cells, but often much more. With my line notation for seas, I draw a loop around completed ships to mark all those cells out. I then specifically check if anywhere I just placed a ship left a row as empty or nearly empty. I then also specifically check if anywhere I just placed some seas left a row full or nearly full. You need to do both of these independent searches to get very efficient at marking the next seas and the next ships. The "simple steps" all involve ID'ing the rows that no longer have more options (all remaining cells are ships or seas) and you must observe these spots as quickly as possible and chain productive steps together.
Outside of the focus on rows and columns is a focus on the fleet; it should be obvious that there are lots of ways to place small ships in a grid but many fewer ways to place the large ships. This is due both to the available sum of segments remaining from the outside clues, but also to the fact that with marked seas there could just be no open space for a 1x4 set of cells to be ships regardless of the outside clues. Almost every battleships puzzle you'll encounter will therefore solve by going through a process where you identify all the possible places the battleship can go, quickly eliminating as many as possible by direct observation, and then eliminating the rest by trial and error. After the battleship is placed, transition your thinking to the next biggest ships, the two cruisers. Repeat until finished. If you are good at the bookkeeping of ships and seas, you can be pretty efficient at this exploration process. The hard puzzles just involve searching a much broader tree. It is only on the harder puzzles where perhaps learning logical rules about "near empty" and "near full" from practice can give you a leg up as marking some of the harder to find seas will shrink the search space faster than random search. I need to know these rules to comfortably construct these puzzles, as I can only have one answer, even if my solvers' approach may leave them without the certainty of there being just one answer.
Comments: Battleships was the first logic puzzle I ever loved, at a rather young age, as the only page of GAMES I'd reliably solve. I was too young for that ornery crossword or most other things but the variety word search. But those 6 Battleships were manna from heaven. I'd gradually grow more into Paint by Numbers, and then over the next 20 years to the present towards solving much more interesting puzzle types than those that are less fiddly and have more compelling and interesting logic.
But I still appreciate, when crafted well, what a great Battleships puzzle can be. And I've stretched the form in various ways myself. The basis of my first leap into the professional puzzle constructing world was a book that combined Battleships with Sudoku, with two very different kinds of logic combined in interesting and unique ways. I've also shared here variations with Yajilin and Fillomino and Snake-like concepts thrown in, as well as simple digit-labelling as a more mathematically minded variation that does a lot more for me than the "Digital Battleships" variation that did appear on the USPC twice.
In a competition sense, you must be able to do the battleships puzzle pretty fast. It's going to be there every year, on that first page you pull from the printer, so if you don't start on an observational puzzle that doesn't need the printout, you'll likely be starting on it. With the strategies above, you'll just want lots of practice to be really quick with the solving. You can certainly play some of Conceptis' Battleships puzzles as in GAMES since those are pretty much what I'd call Moshe Rubin's puzzles. Or you can play through the Battleships books on the market including the sudoku fad inspired name of "Yubotu" or the republished Gordon/Shenk puzzles in BATTLESHIP Puzzles. Or check out the 25 hand-crafted ones that form their own training section in my Battleship Sudoku. They're pretty good puzzles compared to most of what you'll find out there, but then I don't write puzzles like most people in the market do.
About this puzzle: I have a lot of goals for this series. But the largest is probably to write representative puzzles of types that appear all the time so even beginners may know where to look to get better at the championship. So I couldn't avoid Battleships forever. And with a heavier work schedule this week, it is an easier type to write for a 5 or 10 point puzzle. I violate what seem to be the standard design rules for these puzzles all the time. Here, USPC in seas will set up enough for you to place all the ships. Enjoy!
Rules:
Locate the position of the 10-ship fleet in the grid. The fleet is shown to the right of the grid: one 4-unit battleship, two 3-unit cruisers, three 2-unit destroyers, and four 1-unit submarines. Each segment of a ship occupies a single cell. Ships are oriented either horizontally or vertically, and they do not touch each other, not even diagonally. The numbers on the right and bottom edges of the grid reveal the total number of the ship segments that appear in each respective row or column.
Type: Battleships
USPC History: The classic form has appeared every year from 1999 to 2010 (twice in 1999), and has been the first puzzle since the first "Google" form of the championship in 2003, continuing in that spot in the current post-Google era. Variations have appeared several times including Digital Battleships (2000, 2001), Retrograde Battleships (2001), and Path Battleships (2002). Battleships was also one quarter of the Four Square puzzles in 2009, 2010.
The most frequent contributor of the lead battleships puzzle is Moshe Rubin, who used to be a GAMES contributing editor for the Battleships column before partnering with Conceptis many years ago to sell his computer-generated puzzles under their brand name. Other contributors have included the Dutch publisher Puzzelsport in the early years, Erich Friedman for some of the variants, and Jay Baxter one year apparently as a gift for dad that ended up on the USPC.
Notation tips: Battleships are a fiddly puzzle type. Even if it weren't the case that over 95+% of the Battleships puzzles you encounter are computer-generated, you'd probably still find that most of them fall from trial and error approaches more quickly than strict logic, most often from finding contradictions in limited placement options of large ships.
When solving a battleships puzzle, I try to use a 2-way notation system to keep track of things I know for sure, and things I'm more speculative about at that moment. When marking ships, I'll shade in dark anything I got from logic/starting conditions. When I'm on a trial/error pathway, I'll simply outline the ships but leave them unshaded, so I know what to fully erase if things don't work out. Since you almost always start such a pathway by placing a 4- or 3-unit ship, I tend to remember what was the first part of the guess. But you might find it wise to note this to yourself if you lack that kind of short-term memory.
With seas, I draw full lines to mark out unused rows/columns and also make "loops" around the parts of ships I can immediately eliminate, often U shapes but sometimes full boxes. If I can't draw a line as I only have an isolated cell as a sea cell, I'll put a dot. Along speculative paths, I'll draw lighter lines (which is most efficient for me) or, once the battle of constant erasing is going against me, slashed cells.
USPC Battleship puzzles are rarely too hard, so I don't have a real battleground of a past paper to show you. Or any puzzle I've had to guess at. But this is my solved copy from 2003 for a nice 12 points per minute to start the test.
Strategies: Aside from the obvious steps, battleships puzzles get constrained by a combination of "nearly empty" and "nearly full" spaces. A "nearly empty" row is one that can take just one more ship segment anywhere in it. A "nearly full" row is one that can only accept one more unmarked sea segment with everything else having to be a ship. You may not know where the ships go in the "nearly full" row, but if you ever mark one more sea in that row you would know every such placement. The value of "nearly full" rows is that placements elsewhere in the grid often directly affect them, and can be ruled out if they make completing that row impossible. Where a "nearly empty" row intersects a "nearly full" row, you can almost always mark some cells 1 away from the nearly full row as seas because of this kind of thinking. But more distant placements will have the same effect. Learning these interactions is how to actually get good at solving battleships puzzles by logic, as you can see the contradictions 2 or 3 steps down the line that most often get encountered by trial-and-error. Extremes are also key to observe. You cannot have more than 8 cells filled in any row in a standard 10x10 puzzle (and there aren't many ways to do this but you must use either the 4-cell battleship or both 3-cell cruisers). But similarly you can't easily have as many as 9 or 10 cells filled in adjacent rows. If you see large numbers of ships left to place in close spots or, considering all the marked seas, a lot of cells to fill in adjacent rows that don't have a lot of spaces left, this is where you need to focus your attention.
But that is all probably higher-level thinking than you'll need to solve the USPC battleship puzzle, so the main thing to learn to really get started is how to be meticulous at the bookkeeping of cells. Anytime a cell is marked as a ship segment, make sure you've marked out all the cells that cannot be ships. This is at least the 4 diagonally adjacent cells, but often much more. With my line notation for seas, I draw a loop around completed ships to mark all those cells out. I then specifically check if anywhere I just placed a ship left a row as empty or nearly empty. I then also specifically check if anywhere I just placed some seas left a row full or nearly full. You need to do both of these independent searches to get very efficient at marking the next seas and the next ships. The "simple steps" all involve ID'ing the rows that no longer have more options (all remaining cells are ships or seas) and you must observe these spots as quickly as possible and chain productive steps together.
Outside of the focus on rows and columns is a focus on the fleet; it should be obvious that there are lots of ways to place small ships in a grid but many fewer ways to place the large ships. This is due both to the available sum of segments remaining from the outside clues, but also to the fact that with marked seas there could just be no open space for a 1x4 set of cells to be ships regardless of the outside clues. Almost every battleships puzzle you'll encounter will therefore solve by going through a process where you identify all the possible places the battleship can go, quickly eliminating as many as possible by direct observation, and then eliminating the rest by trial and error. After the battleship is placed, transition your thinking to the next biggest ships, the two cruisers. Repeat until finished. If you are good at the bookkeeping of ships and seas, you can be pretty efficient at this exploration process. The hard puzzles just involve searching a much broader tree. It is only on the harder puzzles where perhaps learning logical rules about "near empty" and "near full" from practice can give you a leg up as marking some of the harder to find seas will shrink the search space faster than random search. I need to know these rules to comfortably construct these puzzles, as I can only have one answer, even if my solvers' approach may leave them without the certainty of there being just one answer.
Comments: Battleships was the first logic puzzle I ever loved, at a rather young age, as the only page of GAMES I'd reliably solve. I was too young for that ornery crossword or most other things but the variety word search. But those 6 Battleships were manna from heaven. I'd gradually grow more into Paint by Numbers, and then over the next 20 years to the present towards solving much more interesting puzzle types than those that are less fiddly and have more compelling and interesting logic.
But I still appreciate, when crafted well, what a great Battleships puzzle can be. And I've stretched the form in various ways myself. The basis of my first leap into the professional puzzle constructing world was a book that combined Battleships with Sudoku, with two very different kinds of logic combined in interesting and unique ways. I've also shared here variations with Yajilin and Fillomino and Snake-like concepts thrown in, as well as simple digit-labelling as a more mathematically minded variation that does a lot more for me than the "Digital Battleships" variation that did appear on the USPC twice.
In a competition sense, you must be able to do the battleships puzzle pretty fast. It's going to be there every year, on that first page you pull from the printer, so if you don't start on an observational puzzle that doesn't need the printout, you'll likely be starting on it. With the strategies above, you'll just want lots of practice to be really quick with the solving. You can certainly play some of Conceptis' Battleships puzzles as in GAMES since those are pretty much what I'd call Moshe Rubin's puzzles. Or you can play through the Battleships books on the market including the sudoku fad inspired name of "Yubotu" or the republished Gordon/Shenk puzzles in BATTLESHIP Puzzles. Or check out the 25 hand-crafted ones that form their own training section in my Battleship Sudoku. They're pretty good puzzles compared to most of what you'll find out there, but then I don't write puzzles like most people in the market do.
About this puzzle: I have a lot of goals for this series. But the largest is probably to write representative puzzles of types that appear all the time so even beginners may know where to look to get better at the championship. So I couldn't avoid Battleships forever. And with a heavier work schedule this week, it is an easier type to write for a 5 or 10 point puzzle. I violate what seem to be the standard design rules for these puzzles all the time. Here, USPC in seas will set up enough for you to place all the ships. Enjoy!
Rules:
Locate the position of the 10-ship fleet in the grid. The fleet is shown to the right of the grid: one 4-unit battleship, two 3-unit cruisers, three 2-unit destroyers, and four 1-unit submarines. Each segment of a ship occupies a single cell. Ships are oriented either horizontally or vertically, and they do not touch each other, not even diagonally. The numbers on the right and bottom edges of the grid reveal the total number of the ship segments that appear in each respective row or column.