Timeline for How can I know if my puzzle game is always possible?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 8, 2018 at 23:39 | comment | added | corsiKa | @PeterTaylor It will definitely take far longer to code the simulator than it will to run the results. | |
| Feb 8, 2018 at 16:27 | comment | added | Peter Taylor | 33.5 million? Replace "couple of hours" with "couple of seconds" and it's probably still pessimistic. | |
| Feb 8, 2018 at 10:06 | comment | added | Arthur | Math time: If you want to calculate the number of distinct boards (regardless of solvability), taking all symmetries into account, then Burnside's lemma is the way to go: There are 16 symmetries (one trivial, three rotations, four reflections, and then each of those 8 combined with inversion of on/off), and for each of those symmetries some number of boards are entirely unchanged. If you take the average of entirely unchanged boards per symmetry, that's equal to the number of distinct boards. | |
| Feb 8, 2018 at 8:13 | comment | added | GrandOpener | It turns out, as Robert Mastragostino mentioned in his answer, this is actually a well known, well studied problem. Each solvable puzzle has exactly 4 solutions, and the majority of random boards are not solvable. Searching all of that space might be fun, but since there already exists a proof (math.ksu.edu/math551/math551a.f06/lights_out.pdf) you could also do a couple of dot products and have the same answer in a few microseconds. :) | |
| Feb 8, 2018 at 5:32 | comment | added | Arcanist Lupus | @Clockwork-Muse, yes, but that's harder to calculate an exact number for, because while asymmetric designs can be rotated and flipped in 8 permutations, symmetric designs have fewer permutations. So I only mentioned the white/black inverting, since every solution has exactly 1 inverse. (Although for that inverse to work, you do have to prove that you can flip the entire board) | |
| Feb 8, 2018 at 3:31 | comment | added | Clockwork-Muse | More than half are "inverses" - besides horizontal reflections, you have vertical reflections and rotations. | |
| Feb 8, 2018 at 3:02 | history | answered | Arcanist Lupus | CC BY-SA 3.0 |