stephenlf3 days ago
Love it. The “par” value is a huge hint. You might consider hiding it
edit: found a way to solve it in 6, but not in 4
—-
Edit: and the right answer was so obvious, too
Took ages to find an algorithm that produces mostly interesting puzzles in the goldilocks difficulty zone.
I'll be particularly curious to hear the pattern(s) in how many solutions there are, and/or the probability of a random board being solvable.
The haptic feedback on mobile is really on point in this implementation.
Regarding the number of solvable boards. It is actually possible to calculate the exact number. The solvable boards correspond to the image of the matrix of moves. It will be a vector (sub)space over Z/2Z, so it will always be a power of 2, and its size will be determined by the rank of the matrix. For example for 5x5, there are 2^22 valid boards.
And regarding the number of solutions to a given board, (assuming you ignore the order of moves, because it doesn't matter) it will always be the exact same number, and in the case of 5x5 it will be 2^8. 8 is the nullity of the matrix of moves.
Note that 22+8=30, which is 44+33+22+11, which is the number of possible moves.
1. The flippable regions need be flipped at most once, in any order. So, one could think of a solution as a collection of boolean variables, one for each region, indicating whether to flip it (true/1 if so, false/0 otherwise, feels natural).
2. A tile needs to be flipped an even number of times if it starts in the desired state, and an odd number of times otherwise. So: Give each tile an equation by forming the XOR (or addition modulo 2) of the variables for all the regions it inhabits, and then setting that expression equal to 0 if the tile starts out in the desired state, otherwise 1.
3. Observe that such equations are always easy to rearrange so as to solve for any desired variable.
4. Observe that we can therefore run through a familiar substitution process, and good things will happen.
What I find elegant here is that the resulting algorithm is known to many from early algebra and has a much more clearly bounded runtime than the backtracking searches that suit other logic puzzles. Of course, as you've evinced, the fuller representation with linear algebra opens many doors to both implementing this well and exploring its other properties.
Finding par, on the other hand, I'll have to consider further. I suspect that, after representing the solution space succinctly, you could get a fair way with a backtracking search therein (where to make a forward step is to concretely assign a value to a variable), with the search tree trimmed via the best par observed so far. If you have something drastically better than that, I'm sure that would be interesting!
Looking forward to seeing what you do next, also perhaps the potential blog post you mentioned elsewhere in this thread, etc.
https://archive.org/details/Quadromania_1987_CP_Verlag_de-en_cr_CHR_Docs
It took me a while to get past the instruction screen (I needed to press space, then "E" for english, then press escape) Now I can't seem to figure out the controls for the actual game.
I was thinking of making weekly levels be very big (like 12x12) where I don't know what the par is myself, and have it be a challenge to see who in the community can figure out a way to get the lowest number of moves.
And daily levels would probably be more similar to the regular levels.
On my games I usually go with five levels [1], in different tabs that can be solved concurrently, from very easy to very hard. People seem to enjoy the progression.
Also, the game does give you a hint about how to bruteforce the level if you only have one square left. Good job.
Well done!
Edit: limiting it to square flips was a great idea. There are just enough moves to make the answer non-obvious (after lvl 15), but not so many possible moves that you get overwhelmed.
---
Edit 2: I just remembered I made a similar "game"[1], where you select columns to XOR with other columns and try to reach the target pattern. Use the scroll wheel and shift+wheel to change the pattern and size.
That was actually part of a real research project in optimizing circuits for computing binary finite fields, where the "game" was a sandbox to try different algorithms. The best algorithm was actually found by someone playing in this sandbox and coming up with an efficient strategy.
[1] https://boppreh.com/source/playreduce/
Although interestingly some other people in the comments here say they liked how the progression goes.
And that's an interesting little game you made.
And I spent quite some time creating an algorithm and solver to find the par for Unflip. I'm planning to release a blog post about it soon