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.
You'll have to find the puzzles' rules by yourself tho.
[0] https://en.wikipedia.org/wiki/List_of_NP-complete_problems#G...
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.
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?".
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".
https://lukerissacher.com/battleships?swapmouse=1
If it's a common request I should probably make it a saved setting.
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?]
A number of them are implemented via SGT puzzles https://www.chiark.greenend.org.uk/~sgtatham/puzzles/
The only suggestion I would make is have a middle click that marks a spot as a possibility.
I rewrote it as a web version, should be still available: https://www.kleemans.ch/static/bimaru-web/
* 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
But having it only perform the same action would make things nicer.
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.
Works well on smaller sizes and on Chrome on the same device.