Battleships Logic Puzzle
89 comments
·October 25, 2024namuol
tangus
Also, https://puzz.link/db/
You'll have to find the puzzles' rules by yourself tho.
angus-g
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.
tangus
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.
QuadrupleA
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
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
> 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
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
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?".
charlieyu1
So that’s why so many puzzles seem to be impossible to solve except trial and error
gs17
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".
QuadrupleA
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
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.
olliej
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
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).
pavel_lishin
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
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
Huh, I've never heard of this particular puzzle before! Big fan of Simon Tatham's puzzle app, though.
jandrese
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.
RedNifre
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!
SilasX
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:
akleemans
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/
dmurray
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
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
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?
QuadrupleA
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.
o11c
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
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
Having it support rectangles would work for both use cases I think. Freeform is the worst of both worlds.
pimlottc
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
Tapping the numbers to fill in water is a nice feature, not very obvious though. I had no idea that was possible.
pimlottc
+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.
jonny_eh
Click and drag that doesn't overwrite non-blank squares is a nice feature in Nintendo's Picross series.
waterhouse
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.
ndarray
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
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
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.
ndarray
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.
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.