Show HN: Linjat, a small puzzle game
linjat.snellman.net
linjat.snellman.net
I thought I'd post it here, since it ended up being kind of fun to play in it's own right, not just an algorithmic experiment.
Unfortunately the overflow: hidden is needed for the touch event handling to work properly. But there's probably some reasonable solution based on resizing / scaling instead.
https://linjat.snellman.net/#game.easy.4
edit: My logic parts are weak
Edit: easy 7 solvable and now my wife is addicted too.
Stage one is just to generate a level by randomly placing numbers on the grid.
Stage two is to run a special solver for the puzzle, which tries to solve the puzzle the way a human would (applying different kinds of local deduction rules, e.g. "only this number can reach that dot, so that's how the line has to be drawn" or "there's not enough space to draw this line vertically, so it has to be horizontal", and then a handful more of increasing complexity). If the solver gets stuck, it adds more dots to the board, with the locations of the dots being such that they're going to provide as little information as possible at the start of the game.
That gives a seed puzzle to work with, which is solvable but usually not very interesting.
Stage three is optimizing the puzzle. That's done with what's basically a hill-climbing algorithm. So take a puzzle (either the original, or a better puzzle that's been found during the optimization) and change it a bit by moving or changing the numbers. Then run the solver again on the modified board, but with all the dots removed. If the new puzzle is solvable, it's scored on a bunch of metrics, and if it's good enough it goes into the pool of improved puzzles for the next iteration to work on.
Obviously for this to produce the feeling of gotchas, the metrics have to be chosen to match human intuition on easy vs. hard moves. That's the tricky part.
That's the gist of it. I'm planning on writing a blog post on it later with more details.
The creator makes sure that each puzzle has a unique solution, right? I don't know if this is intended, but after a few games I notice that knowing this makes it even the expert puzzles relatively straightforward to solve. That is, there are lots of spots where nothing appears to constrain a piece from extending in a given direction, but any solution where it did so wouldn't be unique, so you can rule it out, which makes the puzzle solvable without trial and error.
1. Don't have a single solution, but have any duplicate solutions be trivially transformable to the others. E.g. via the "this piece has two possible orientations, and neither will conflict with another piece".
2. Make having a single solution be part of the rules, and necessary for solving some of the puzzles.
3. Make sure the puzzle generator just never generates a place where the uniqueness of the solution can be used to short-circuit the solution.
4. Punt.
Idea number 1 is probably the best one, but the fear was that players would perceive that as "guessing". But looking at how people actually play the game, I think that fear might have been misplaced.
The puzzle generator is in C++.
I'll put both on Github, but they require a bit of cleanup work first.
I too had problems realising you could drag the lines in both directions, obvious after the tutorial; but who's got time for that!
Overall great game!
However... I would re-label the « Back » button as « Home » and add a « Back » button that undoes the last move...