Lights Out with three states.

[LolBbq]

Is a Lights Out game with three states mathematically feasible? Or, should I say, could a random procedure that scrambles the board create an unsolvable board? I was thinking about it and I couldn't figure it out.

[nitacku]

Hmmm...
Try creating one but on a 3x3 scale. If it can be solved, then I would say that a larger one should be solvable as well.

Or you could guarantee solvable ones by just having the program mix the grid up by pressing the lights individually a few times before the game starts

[LolBbq]

[DarkerLine]

Is this the Lights Out where flipping one cell flips all the adjacent ones, or the Lights Out where it flips everything in the same row and column?

I know the flipping random switches approach is probably simpler, but I'm kind of interested in solving the general problem for the heck of it.

I've figured out that for the row-and-column Lights Out, if the number of rows or the number of columns is equal to 1 modulo the number of states (for not-tiny boards), then not all positions are possible to solve.

[LolBbq]

I'm working on the one that flips the cell the cursor is on and ones that are directly adjacent to it. I have a working model in TI-BASIC that has 3 states, maybe I'll post a screenie later.

[DarkerLine]

Ok. For that version: any board that is 2k-1 by 3m-1 (for some k,m) has unreachable positions. I haven't shown that all positions are reachable for other board sizes yet.

[LolBbq]

Well, for simplicity's sake, I'll just resort to randomly toggling each individual square. Although an algorithm would speed things up and greatly increase the randomness.

Oh, and I'm working with square boards, so would odd dimensioned square boards have invalid combinations?

[DarkerLine]

If it's 5x5, 11x11, 17x17, or etc., then yes, it would. Otherwise, I don't think so, but I don't know for sure.

It boils down to finding a combination of flips that results in a totally blank grid again.

[LolBbq]

[Harrierfalcon]

Basic or ASM? Either way, it looks excellent.

[LolBbq]

Basic.
No, really?//

EDIT:Try it out, nothing fancy, just randomizes now:

[Harrierfalcon]

Fun! Gimme a minute...

One minute passes...

Five minutes pass...

Liar! [font="courier new;font-size:9pt;line-height:100%;color:darkblue"]ERR:INVALID

[LolBbq]

Five minutes. Seriously? And this is just the core, lots of little things can be added here and there. Just got to think of them .

[LolBbq]

I should also point out that the dithered squares are merely a placeholder for real gray squares, which won't be implemented until I can get flickerless grayscale (but hey, I'm close to it! Using interlacing I have made headway but I still need crystal timer synch [someone please tell me how...]).

[DarkerLine]

As far as randomizing goes:

Rather than repeatedly flipping a random switch, consider that flipping the same switch 3 times is the same as not flipping it at all. Therefore, it's necessary to flip each cell 0, 1, or 2 times for full randomization.
Here's what you do: generate a bunch of random numbers 0..2 (one for each cell). Then set each cell to the sum of itself plus its four neighbors, modulo 3. This requires generating much less random numbers (for an NxN grid, you need roughly 3N²/2 random cell flips, or 3N² random numbers 1..N, whereas here you need only N² numbers 0..2).

[LolBbq]

You say four neighbors...the same would apply for edge or corner cells?

[DarkerLine]

Yes, except of course you'd add up only the neighbors they actually have.

[LolBbq]

Ok, I dig. Although it does means sacrificing memory for speed...Currently I'm running 49 flips on any random cell coordinate, seems sufficient except for the 3x3 grid which might come out solved or near solved (off by one to three flips).

[DarkerLine]

What memory would you be sacrificing, exactly? All of the saferam areas are at your disposal.

[LolBbq]

What I meant was size.