Battleships Logic Puzzle | Hacker News Reader

Battleships Logic Puzzle

lukerissacher.com

254 pointsQuadrupleA87 comments

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.

Also, https://puzz.link/db/

You'll have to find the puzzles' rules by yourself tho.

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.

You're right, but not all of them link to the puzz.link player. The ones using the pzv.jp player, for instance, lack that feature.

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.

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...

> 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.

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.

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?".

So that’s why so many puzzles seem to be impossible to solve except trial and error

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".

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?]

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).

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.

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.

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

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/

Huh, I've never heard of this particular puzzle before! Big fan of Simon Tatham's puzzle app, though.

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.

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!

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/

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/

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.

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.

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?

Think this is fixed now - in dark mode, the numbers didn't gray out properly like in light mode. On some browsers the strikethru lines up with the 4, but the additional graying out hopefully communicates the same thing.

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

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.

Having it support rectangles would work for both use cases I think. Freeform is the worst of both worlds.

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.

Tapping the numbers to fill in water is a nice feature, not very obvious though. I had no idea that was possible.

+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.

Click and drag that doesn't overwrite non-blank squares is a nice feature in Nintendo's Picross series.

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.

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.

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.

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.

If you do it as a purely visual representation of the game state, it won't be a solver, will it? Just all blocks surrounding ships + blocks in rows/cols with a 0.

Kinda addictive. I lost a few hours to this today. I hope you’re happy. ;) After getting pretty quick at the 15x15, it has minesweeper vibes. Works great on iPad, and the implementation is nice. Thank you for sharing.

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.

Nice puzzle, reminds me of Zachtronics' Dungeons & Diagrams.

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.

That might be good. One shortcut I did add, you can click the numbers to auto-fill water once a row is complete.

This is one of the puzzles at BrainBashers:

https://www.brainbashers.com/battleships.asp

An undo button would be nice :) (for when I need to backtrack)

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).

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.

“Ships can’t touch, not even diagonally.” Doesn’t that imply ships can never share an edge, and that you can fill water around a ship?

Yes! That's perfect now.

Thread's pretty old now, but for posterity: there's now an automatic error dot if two ships are touching diagonally: https://lukerissacher.com/battleships

There’s a bug: if a puzzle has multiple solutions, only one of them is considered “correct”.

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!).

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.

That would be a cool direction to explore.

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.

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.

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.

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.

First puzzle I got had four equally good solutions, none of which violated any of those.

Think I found a good solution to this - there's now an immediate error message / red line when connecting incorrectly to a starting ship square: https://lukerissacher.com/battleships

I usually play it on here: https://gridgames.app/battleships/

In this version, the field can be prefilled with some ship parts

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.

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

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

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.

You can't have that configuration: ships must not touch, even at diagonals.

This implementation seems to work a little better: https://www.puzzle-battleships.com/

What makes that one better in your opinion? I've tried both and I think they're both OK.

"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.

"Ships can't touch diagonally." is a rule qualifying valid answers, not what can be drawn on the diagram

Since that instruction's easy to miss - I added an immediate error message / red dot if two ships are placed diagonally from each other: https://lukerissacher.com/battleships

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?

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.

Yes, it’s an additional piece of information that is vital for some puzzles.

I got a puzzle with (at least?) two valid solutions, but one of them is "wrong" and the game refuses to accept it.

Boo.

It's probably this: https://news.ycombinator.com/item?id=41946571

https://www.webpbn.com/

What this needs is a daily puzzle and an easy way to share it in text format, a la Worlde or Domino Fit...

You can find a shareable link to the puzzle by clicking the gear icon.

It's a fun game, but the instructions are unclear. Took me a while to figure it out.

this is really nice. well done

I would vote for this in place of minesweeper on any OS install. Love it!

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.

You can link to a specific puzzle through the share link in the settings menu, but it won’t save your state.

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.

Broken in Safari on Sequoia, unfortunately.

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.

Reply on news.ycombinator.com