[HN Gopher] Battleships Logic Puzzle
___________________________________________________________________
Battleships Logic Puzzle
Author : QuadrupleA
Score : 235 points
Date : 2024-10-25 15:12 UTC (1 days ago)
(HTM) web link (lukerissacher.com)
(TXT) w3m dump (lukerissacher.com)
| pavel_lishin wrote:
| Ooh, this is a fun variant of nonograms! If you like this puzzle,
| I think you'd enjoy those too:
| https://en.wikipedia.org/wiki/Nonogram
| jldugger wrote:
| Battleships is a pretty common puzzle on the World Puzzle
| Championship tests. If this is new to you, you may enjoy
| Nikoli's broader range of puzzle sets listed on wikipedia
| https://en.wikipedia.org/wiki/Nikoli_(publisher)#Nikoli_puzz...
|
| A number of them are implemented via SGT puzzles
| https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
| pavel_lishin wrote:
| Huh, I've never heard of this particular puzzle before! Big
| fan of Simon Tatham's puzzle app, though.
| eapriv wrote:
| There's a bug: if a puzzle has multiple solutions, only one of
| them is considered "correct".
| QuadrupleA wrote:
| Author here - check that the revealed ships in your puzzle are
| keeping their particular shape. E.g. a revealed-at-start "D"
| shape ship-end can't be the middle of a ship, or an "O"
| submarine, or face a different way that it's initially facing.
| 99.9% of the time people report this, it's a confusion about
| that aspect (if you can think of a way I can make it clearer
| definitely let me know!).
| hibikir wrote:
| The simplest way would be to also pre-fill forced empty
| spaces. It 'solves' part of the puzzle for the player, but
| hopefully that wasn't a key part of the fun. You go as far as
| to explain all of those bits at the bottom anyway.
|
| This kind of thing is done to great effect in "Good Sudoku",
| which gives players a lot of automated tools for the simplest
| things, as to lead players to handling the more fun, more
| complicated parts of the hard puzzles.
| QuadrupleA wrote:
| That would be a cool direction to explore.
| rtkwe wrote:
| Putting a blank space in front of or behind as
| appropriate for the starting revealed square(s) would
| make sure people don't keep having the problem.
| QuadrupleA wrote:
| Here's an experimental implementation, reveals the water
| cells around any revealed boats:
|
| https://lukerissacher.com/battleships?revealwater=1
|
| Not sure I like it, kinda makes the starting puzzle
| noisy/crowded.
| acheron wrote:
| Yeah took me a bit to catch how the starting spaces worked.
| Not sure how to clarify that other than just writing it out
| in the instructions below.
| andrewla wrote:
| I think the easiest way to make it clearer is to highlight it
| in red as a mistake if done incorrectly, as you do with the
| counts on the row ends. If you try to place a ship token
| close to another one then you should also highlight it in
| red.
| pkasting wrote:
| First puzzle I got had four equally good solutions, none of
| which violated any of those.
| tcmb wrote:
| What this needs is a daily puzzle and an easy way to share it in
| text format, a la Worlde or Domino Fit...
| kibwen wrote:
| You can find a shareable link to the puzzle by clicking the
| gear icon.
| justinpombrio wrote:
| This is one of the puzzles at BrainBashers:
|
| https://www.brainbashers.com/battleships.asp
| akleemans wrote:
| Bimaru is a fun puzzle. I remember putting an Android App in the
| store containing the phrase "Battleships", only to receive a
| copyright claim from Hasbro, and Google immediately took the App
| down from the Store.
|
| I rewrote it as a web version, should be still available:
| https://www.kleemans.ch/static/bimaru-web/
| gnramires wrote:
| An undo button would be nice :) (for when I need to backtrack)
| QuadrupleA wrote:
| If you turn on hardmode there's a "Save Checkpoint" button. But
| not easy mode at the moment (I wanted to keep the UI clean).
| t00ny wrote:
| Nice puzzle, reminds me of Zachtronics' Dungeons & Diagrams.
| gs17 wrote:
| Thank you for making it mobile-friendly. I almost made my own
| Android version of this just because the usual site I played it
| on wasn't usable and the best I could find in the Play store was
| mostly there to sell you $1.99 packs of 50 puzzles as if there
| was any actual effort put into generating them (seriously, they
| acted like 1 free puzzle per week was generosity).
|
| Although can we get a setting to switch left and right click's
| default actions? I prefer puzzle games like this to use "click
| where there is something, right click to mark where there isn't
| something".
| olliej wrote:
| Depending on the puzzle there is "actual effort", a lot of
| these puzzles are not generated.
|
| If you're experienced with solving you can also generally
| distinguish generated from constructed puzzles.
|
| [Edit: Are you looking specifically for battleship puzzles? or
| just variant sudoku?]
| gs17 wrote:
| It was the exact same puzzle that's in the OP. With the scale
| of available puzzles they had for sale, I'm fairly confident
| it was automated (they also weren't noticably different from
| the generated puzzles I played before).
| QuadrupleA wrote:
| Sure thing - just added a quick button swap URL parameter:
|
| https://lukerissacher.com/battleships?swapmouse=1
|
| If it's a common request I should probably make it a saved
| setting.
| thaumasiotes wrote:
| Having two mouse buttons available for two actions would make
| sense, except that right-clicking on the puzzle brings up a
| context menu. So regardless of the swapmouse setting, only
| the left click is a real possibility.
| uses wrote:
| I've spent quite a few hours on this thing when I've needed
| something non-linguistic for my brain to engage in. If it was
| World of Warcraft, I'd probably be a level 30 rogue.
| lupire wrote:
| "Ships can't touch diagonally."
|
| But it lets you do it and then tells you it's wrong at the end.
|
| When the "4" has a strikethrough, the strike is almost impossible
| to see.
| dmonitor wrote:
| "Ships can't touch diagonally." is a rule qualifying valid
| answers, not what can be drawn on the diagram
| zeugmata9 wrote:
| Nice! In line with other apps like this (e.g. LinkedIn's queens),
| I think the grid should be marked complete once you have all the
| boats, without needing to mark all the water.
| QuadrupleA wrote:
| That might be good. One shortcut I did add, you can click the
| numbers to auto-fill water once a row is complete.
| QuadrupleA wrote:
| Interesting tidbit, the Battleships puzzle is NP-complete
| (http://www.mountainvistasoft.com/docs/BattleshipsAsDecidabil...)
| - there's no known solver algorithm that can do it in polynomial
| time, as the size of the puzzles / boards expand.
| abetusk wrote:
| I think NP-Completness is the norm rather than the exception.
| Wikipedia has a list of NP-Complete problems [0].
|
| [0] https://en.wikipedia.org/wiki/List_of_NP-
| complete_problems#G...
| thaumasiotes wrote:
| > I think NP-Completeness is the norm rather than the
| exception.
|
| I don't think that's possible. Being NP-complete means a
| problem is as hard as any NP problem, _and no harder_. But
| there 's not an upper limit to how difficult a problem can
| be.
|
| Note that the problem of determining whether two different
| regular expressions match the same set of strings is _much
| harder_ than any NP-complete problem.
| ianferrel wrote:
| When you think about the class of things that humans
| consider to be "fun logic puzzles", NP-Completeness seems
| more common, since it encapsulates broadly the set of
| puzzles that require a certain amount of brute-force to
| find a solution to, and any reasonably entertaining human-
| solvable puzzle is easy to verify that something is in fact
| a solution.
| abetusk wrote:
| I think that's an unkind reading of my response. I was
| implicitly talking about decision problems or puzzle
| problems like the one in the OP.
|
| If you're talking about PSPACE complete problems or general
| Turing machine equivalence, I would extend the statement to
| include those as well. That is, PSPACE-completeness or
| general Turing machine equivalence are the norm rather than
| the exception.
|
| I'll also point out that a slight rephrasing of the
| question makes a statement about general computation into
| an NP-Complete problem. For example, instead of "Does this
| TM halt?" to "Is there some input for which this TM halts
| with finite tape length N in at most K steps?".
| dmurray wrote:
| This doesn't work for me on Firefox Mobile on Android at 10x10 or
| above. It's as if the touch targets get too small to select: I
| can click on the numbers to turn them red, but I can't seem to
| select any square.
|
| Works well on smaller sizes and on Chrome on the same device.
| QuadrupleA wrote:
| Thanks, weird one - I just put in a fix, you can refresh the
| page to get it. Some kind of CSS glitch where the cells (<i>
| elements) got a height of 0 at narrow screen sizes, in Firefox
| only, despite those and their parent <td>s having an explicit
| height. Just added an absolute positioning hack to fix it.
| Neywiny wrote:
| Didn't see the old way but I'm having no issues on Firefox
| Android as of now. I really like the checkpoint thing. It's
| something I've craved from other platforms. I will note
| though that the 4 with the like through it (maybe just my
| phone) is just a 4 (the line ends up being the crossbar of
| the 4). Maybe a diagonal line would be better?
| cjfd wrote:
| This implementation seems to work a little better:
| https://www.puzzle-battleships.com/
| joemi wrote:
| What makes that one better in your opinion? I've tried both and
| I think they're both OK.
| waterhouse wrote:
| I think "doesn't engage the language center of my brain" is more
| accurate (and less pejorative) than "mindless". It certainly
| engages spatial reasoning and some logic.
| namuol wrote:
| Love it!
|
| If you like this sort of thing, be sure to check out Simon Tatham
| (creator of PuTTY)'s Puzzles:
| https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
|
| The Android and iPhone ports are also excellent and free from
| ads/garbage.
| tangus wrote:
| Also, https://puzz.link/db/
|
| You'll have to find the puzzles' rules by yourself tho.
| angus-g wrote:
| There is a Help->Rules link on all of the puzzles linked
| here. It can be a little tricky to decipher them if you're
| coming to them completely brand new, however. I mostly use
| them as a refresher.
| ndarray wrote:
| Given the rules, it would be a better experience if squares only
| have two states: ship block or empty. There is no point to
| letting the user draw water. The feature probably exists with the
| intent of letting users mark squares that can't possibly be
| ships, but why wouldn't the game do that step by itself based on
| the blocks placed? That would make the game a lot less tedious.
| joemi wrote:
| It's indeed the way it is so that you can indicate a square
| that must be water. What you propose sounds like a solver to
| me, and I much prefer solving it myself.
| snewman wrote:
| Note that very often, the solution process for a more
| difficult puzzle involves going through nontrivial logic to
| prove that a particular square must be water. It's important
| to be able to record non-obvious "must be water" squares.
| RedNifre wrote:
| It took me some time to unlearn the Nonogram rules of assuming
| the numbers on the side indicate continuous ships. After that, it
| was great fun!
| o11c wrote:
| I find the implementation of dragging really annoying compared to
| similar engines. What I'm used to is:
|
| * click and drag will only operate in a single line, either
| horizontally or vertically
|
| * click and drag will only perform the same operation
| (considering both original type and new type). In particular, if
| I've already filled in every other cell as water, dragging in
| "ship" mode should only fill in the empty cells, not overwrite
| the water.
|
| * there should be "undo" support, both Ctrl-Z and U as well as a
| button
|
| Another feature usually _not_ found in similar engines, but
| really useful in order to regain some of the experience from
| solving them on paper:
|
| * have a nearby text box for keeping notes; clear it when a new
| puzzle is started
| ajanuary wrote:
| Having click and drag not be limited to a line is actually
| useful for ringing around a completed ship. You can tap a
| number clue on the outside to fill in the missing water, which
| can help avoid needing to draw long straight lines.
|
| But having it only perform the same action would make things
| nicer.
| o11c wrote:
| Having it support rectangles would work for both use cases I
| think. Freeform is the worst of both worlds.
| pimlottc wrote:
| Restricting to straight lines would be the most
| straightforward, I think. It follows the convention of only
| changing squares that you touch.
|
| Drawing rectangles introduces a new paradigm where you can
| fill in squares you don't actually touch, so it might be
| less intuitive. At the least, you would probably want to
| highlight the affected squares in a different color before
| finalizing the action.
| pimlottc wrote:
| Tapping the numbers to fill in water is a nice feature, not
| very obvious though. I had no idea that was possible.
| pimlottc wrote:
| +1 for undo, it's very easy to tap the wrong squares by mistake
| on mobile (especially on larger grids) and hard to figure out
| what the previous state was.
| tgeery wrote:
| this is really nice. well done
| jandrese wrote:
| Weirdly I find the 15x15 puzzles to be easier in general than the
| 6x6 ones. Maybe it is because the 15x15 ones aren't packed as
| tightly so you don't have to use as much second order logic?
|
| The only suggestion I would make is have a middle click that
| marks a spot as a possibility.
| NooneAtAll3 wrote:
| having played a lot of this puzzle on https://www.puzzle-
| battleships.com/ ... I'd love a couple QoL improvements, one from
| there and one to be better than that one
|
| - counters for columns/rows would be a nice idea to steal
|
| - inverse control (so, lmb for ship) would help with not
| interfering with default behaviour, for people switching to/from
| different puzzles
|
| Also ship helper really should come with each type on its own
| line - your listing is harder to parse than on that website
| adamredwoods wrote:
| I think there's a bug. If we have two two-length ships, that are
| next to each other in a connected in an "L" shape, it's not
| possible to define it on the board.
| oneeyedpigeon wrote:
| You can't have that configuration: ships must not touch, even
| at diagonals.
| oneeyedpigeon wrote:
| The way the shapes draw themselves -- e.g. the curves -- seem to
| indicate if a shape is at the end, in the middle, etc. Is that
| intentional?
| Zanni wrote:
| It seems to be intentional. (I was confused by this at first,
| too). If your starting grid contains, e.g., a dot, you can
| safely assume it's a one-ship. But if you add a ship, the
| initial state is a block that resolves to a dot or end as
| appropriate when you complete it.
| pimlottc wrote:
| Yes, it's an additional piece of information that is vital for
| some puzzles.
| jader201 wrote:
| Do some puzzles require trial and error solving? I'm in a 7x7
| that doesn't seem to have a way to 100% rule in/out squares early
| on.
|
| Good chance I'm not seeing one, but I've been staring at it for a
| while, and not seeing it.
|
| If someone told me "yeah, all puzzles have exactly one solution,
| but may require trial and error", I would feel (only slightly)
| less dumb.
|
| The puzzle is:
|
| Ships: 4, 3, 2, 2, 1, 1, 1
|
| Top numbers: 4 2 1 2 1 1 3
|
| Left numbers: 2 1 4 2 0 4 1
|
| Freebie ship square: col 4, row 3
|
| Edit: one thing I just realized is that I could have eliminated
| the diagonal squares from the freebie.
|
| Side suggestion: I can't go back to my puzzle -- would be nice if
| the puzzle was hashed into the URL somehow.
|
| Edit 2: Also just realized that the freebie square(s) may point
| in a direction, so the adjacent square is guaranteed a ship.
| Don't know why I didn't figure that out sooner. I assumed it
| wouldn't hint at that or else it would've just filled it in for
| you.
| tpstevens wrote:
| You can link to a specific puzzle through the share link in the
| settings menu, but it won't save your state.
| bsammon wrote:
| An important detail is what kind of ship piece was pictured in
| the freebie square. It could be an entire-size-one-ship (a
| circle), the end of a ship (which would indicate what direction
| the rest of the ship would continue in), or the middle of a
| ship (which indicates a size 3 or 4 ship).
|
| I decided to go with the assumption that it was a middle-of-a-
| ship square, thinking you would more likely have mentioned if
| it was one of the other two types. Then, based on the numbers
| around the outside, you can quickly determine whether the ship
| is horizontally or vertically oriented, and fill in two more
| squares as a result (and rule out a few more squares as a
| result of that). the rest of the solution proceeded quickly
| after that.
|
| I used to do these Battleships puzzles regularly around 15
| years ago, when I regularly bought/read Games magazine, which
| included them. My process, especially for harder puzzles,
| involved darkening (or otherwise tagging) the boundary between
| pairs of squares, as I determine that a 2-or-longer ship could
| not span that particular boundary. Usually based on a logic of
| "Well, if there was a 2 or longer ship there, there'd be a
| problem for the next row/column over" or just "there can't be a
| 2 or longer ship because I'm only allowed to darken one more
| square in that row/column"
|
| This web-app version doesn't appear to have a mechanic for
| marking boundaries -- I frequently find electronic versions of
| traditional puzzles to (understandably) lack the flexibility to
| support the ad-hoc annotative solving process I developed over
| the years of solving these kind of puzzles on paper.
| SilasX wrote:
| Another similar puzzle game is Dungeons & Diagrams on
| Zachtronics's _Last Call BBS_. You have to build a dungeon on an
| 8x8 grid by deciding which spaces are wall tiles, with some
| constraints (such as "dead ends must have monsters and vice
| versa"). That game likewise tells you a sum that each row and
| column must meet.
|
| Someone made a free clone here:
|
| https://netchips.dev/
| Gunax wrote:
| This is advice to the creator:
|
| I think there are unstated rules. Some are implied by the hints
| (eg 'you can fill water around a ship') but it's not clear to me
| at first _why_ that hint works. It looks like ships can never
| share an edge, just based on the puzzles so far.
|
| I am enjoying the game. Thanks for introducing me to something
| new.
| sans_souse wrote:
| I would vote for this in place of minesweeper on any OS install.
| Love it!
| mproud wrote:
| https://www.webpbn.com/
| captaincrowbar wrote:
| Broken in Safari on Sequoia, unfortunately.
| luplex wrote:
| I usually play it on here: https://gridgames.app/battleships/
|
| In this version, the field can be prefilled with some ship parts
| levzettelin wrote:
| Nice collection of puzzles. But the ads on this are bloody
| awful. Can't even pay to get rid of them. What a pity.
|
| TIP: Don't sign up! It doesn't give you any benefits, and you
| still can't get rid of the ads.
| frank90lee wrote:
| I've been using Simon Tatham's Puzzles for years, but I
| appreciate this clean, web-based implementation of Battleships.
| The mobile responsiveness is particularly well done. One
| suggestion: it would be great to have a 'pencil mark' feature for
| noting potential ship locations, similar to how Sudoku puzzles
| handle candidates.
| throwaway313373 wrote:
| It's a fun game, but the instructions are unclear. Took me a
| while to figure it out.
| cwmoore wrote:
| Cool to see this here. I like the design and instructions.
|
| I'm publishing a paperback book of (numeric) logic puzzles:
|
| https://www.kakurokokoro.com
| PhasmaFelis wrote:
| I got a puzzle with (at least?) two valid solutions, but one of
| them is "wrong" and the game refuses to accept it.
|
| Boo.
___________________________________________________________________
(page generated 2024-10-26 23:04 UTC)