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.
> 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?".
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".
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.
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).
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.
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.
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.
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.
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.
+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.
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! 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.
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.
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
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.
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.
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
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.
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
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.
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.
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.
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.
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.