Hi,
I have a programming assignment to make a small console game which was suggested by the lecturer. The problem is that neither lecturer nor I know how is it called. The game is simple:
given a randonly initialized grid such as
a b c
------------
1 | * | * | * |
------------
2 | * | * | * |
------------
3 | * | * | |
------------
Make all cells full(*) or emtpty( ). The player specifies a coordinate, for example b2, and all cells in column b and row 2 are inverted:
a b c
------------
1 | * | | * |
------------
2 | | | |
------------
3 | * | | |
------------
I don't help with programming it. What really bothers me is that I cannot win in a grid larger than 2x2. Is there some sort of tactics for this game? I'm starting to think that in some situations it is no possible to win it at all
@ResidentBiscuit: I think in sliding puzzle game only one square would be missing. Here, however, each square is initialised randomly and independently from others
Whoops, I made the same mistake Zhuge did. I thought it was just adjacent tiles, and not all tiles in the row/column. So maybe a variation of Lights Out?
@Disch: that looks a little bit similar.
Anyway, I figred out that winning on 3x3 board is not always possible (at least not after 1 billion random moves). However it seems that 2x2 and 4x4 boards are always solvable.
I saw that game as "Camaleón Binario" (Binary Chameleon) in Cacumen 46 (1986) pages 8--13
Here are the relevant pages where it provides an strategy and an analysis of when a board is solvable. http://www.mediafire.com/download/ionr014ama4ranb/camaleon.cbz
(sorry, they are images and are in spanish, didn't want to spoil the solution but if you don't understand it I could pm you the general idea)
Wow, thanks! I have no idea how did you find a 30-year-old magazine and was able to remember about it... Now if someone could tell me the strategy because I think I'd learn Spanish faster than win this game
Actually, even 3x3 boards are solvable (not all of them, but then not all of 2x2 boards are solvable and so on!!)
This is since you can build up your own board from an empty one.
Then the solution is to reverse your steps.
I actually built a board-size-indipendent solver (It finds all possible combinations for a given board).
At the third try it gave a good solution.
Here's the full source (by the way, the first testcase gets solved, too): http://ideone.com/slSGID
Note: The "solutions found" are actually all the possible steps that can be done for a given table.
It's not a path towards a solution.
-err: 3x3 tables only have 10 solutions (= 3x3 + default solution)
2x2 tables only have 5 solutions (= 2x2 + default solution)
which means I have a bug somewhere that doesn't allow the loop to repeat.
Was just thinking about permutations since there are 4 places to put them and only a filled or not filled. But that isn't really the case here and true they are different rotations.