How is this game called?
Pages: 12
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
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:
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
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
Is it a sliding puzzle game (http://en.wikipedia.org/wiki/15_puzzle)?
Your description of the game is pretty bare, but that first picture looks kinda like a sliding puzzle game.
Your description of the game is pretty bare, but that first picture looks kinda like a sliding puzzle game.
@ResidentBiscuit: I think in sliding puzzle game only one square would be missing. Here, however, each square is initialised randomly and independently from others
Unfortunately, I don't know what the puzzle is called either, but here's a winning move set for your given example:
Bolded are the squares I flipped.
*** OO* O** *O* OO* **O OOO *** O** *OO OOO **O *OO OOO **O **O *OO *OO OOO OOO OOO |
Bolded are the squares I flipped.
@Zhuge: I believe all of the squares in the columns/rows are flipped. For example, flipping the top left corner would result in:
|
|
AFAIK it's called "Lights Out".
EDIT: Yep:
http://en.wikipedia.org/wiki/Lights_Out_%28game%29
EDIT2:
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?
EDIT: Yep:
http://en.wikipedia.org/wiki/Lights_Out_%28game%29
EDIT2:
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?
Last edited on
@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.
So far, I managed to win only once on bigger than 2x2 board. If anyone is interested: http://uosis.mif.vu.lt/~rist1954/zv.zip
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.
So far, I managed to win only once on bigger than 2x2 board. If anyone is interested: http://uosis.mif.vu.lt/~rist1954/zv.zip
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)
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
It was a good magazine (it was a second hand article, I'm not as old as Disch)
I just pm you the general idea.
I just pm you the general idea.
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.
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.
Last edited on
> not all of 2x2 boards are solvable
yes, they are.
Even sized boards are always solvable.
yes, they are.
Even sized boards are always solvable.
So, maybe I had a bug?
-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.
-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.
Last edited on
For a 2x2 there are more than 5 possible boards.
There should be 12 if my math is correct since
4! / (4-2)! = 4! / 2! = 4*3 = 12.
Here are the ones I can think of:
4 set:
11
11
3 set:
11
10
11
01
10
11
01
11
2 set:
11
00
10
10
01
01
00
11
10
01
01
10
1 set:
10
00
01
00
00
10
00
01
0 set:
00
00
Though I get 16 so I am unsure of the math formula or I have some duplicates.
There should be 12 if my math is correct since
4! / (4-2)! = 4! / 2! = 4*3 = 12.
Here are the ones I can think of:
4 set:
11
11
3 set:
11
10
11
01
10
11
01
11
2 set:
11
00
10
10
01
01
00
11
10
01
01
10
1 set:
10
00
01
00
00
10
00
01
0 set:
00
00
Though I get 16 so I am unsure of the math formula or I have some duplicates.
Last edited on
But a lot of those are simply rotations or symmetry of others
Discounting them, it ends with 6 possibilities
> if my math is correct since
> 4! / (4-2)! = 4! / 2! = 4*3 = 12
¿care to explain what you are doing there?
Discounting them, it ends with 6 possibilities
0 0 0 0 * 0 0 0 * * 0 0 * 0 0 * * * * 0 * * * * |
> if my math is correct since
> 4! / (4-2)! = 4! / 2! = 4*3 = 12
¿care to explain what you are doing there?
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.
Pages: 12