User:MacGyverMagic/Discussions/Blackflip

From Wikipedia, the free encyclopedia

[edit] Paths

Answering this question by clicking the link on the right will take you to a subpage of my userspace. - Mgm|^(talk) 22:22, 18 October 2007 (UTC)

I've developed an addiction for the game at http://www.blackflip.org Some of those puzzles are particularly devilish and I wondered what math applies to puzzles like this. Maybe reading up on those theories and rules makes solving some of them easier. - Mgm|^(talk) 08:48, 17 October 2007 (UTC)

Well I took a look at those puzzles, very addictive indeed. I think graph theory would help but It seems the most difficult part is deciding what color each horizontal row should be, based on the layout. In general, the study of problems like these falls under game theory. I also think analysis (mathematics) and perhaps Galois theory may help, but those are inherently more advanced and thus less easily understood. A math-wiki 11:27, 17 October 2007 (UTC)

I've a feeling a similar sort of logic to the Seven Bridges of Königsberg may prove to be of some help. To start workout what are illegal moves, for example you can't move horizontally from black to white. They you could try exaustive enumeration of simple 2 by 2 and 3 by 3 sub-grids, for example if you have a t-shape will imply something or other. game theory may be a readherring as the sort of games studied there are more like poker than strictly logical one, all though some ideas like the Decision tree may be of help. --Salix alba (talk) 14:22, 17 October 2007 (UTC)

This comes under combinatorial game theory in some sense, but I doubt that's a very useful observation. math-wiki: how on earth do you intend to apply Galois theory to this situation? Algebraist 15:46, 17 October 2007 (UTC)

Never mind Galois theory. Analysis, which I presume to mean mathematical analysis? Isn't that the polar opposite of what we have here? Salix has already commented on game theory, but I would like to emphasize that the study of problems like this certainly does not fall under what is usually called "game theory".

A math-wiki, your enthusiasm to provide help is appreciated, but perhaps some more reflection about whether your suggestions are truly relevent is in order? -- Meni Rosenfeld (talk) 21:28, 17 October 2007 (UTC)

After playing for a bit, I suspect a logic based way to solve these puzzles can be very useful. You can look at small subgrids of the whole puzzle and make certain logical conclusions. "If I'm ever going to make this square black, I'll have to come from there, so that row will need to be white. If I go over this square, then that becomes unreachable, etc". You can probably formulate a basic set of rules like this, and based on that you can determine for some subgrid a small set of possible paths to take along it. Once you run out of logical rules to apply, you can search the possible paths that are left exhaustively. If you have some paths left for each 3x3 grid, there will only be very few ways to combine those into one full path, if your set of rules is good enough, you will only have a few paths left to check. risk 18:34, 17 October 2007 (UTC)

(after edit conflict) Heres a partial method. Consider a game with n-rows. For the final state each row can be either all black or all white hence there are 2ⁿ possible final state. For each such final state mark the differences between the final state and the starting state with an X. A few things are imediatly obvious, each X must be connected by X's to the edges of the grid (or all X's are connected, but don't touch the edge). Next count the number of dead-ends, that is X's with only one imediate neighbour, here the edge of the board can be counted as X's. There can be at most 2 of these and if they exist the dead ends much be starting or ending points. Similarly T shapes and + shapes count as 1 and 2 end points. Once you eliminate the impossible final states you would have a much smaller set of possibilities. --Salix alba (talk) 19:11, 17 October 2007 (UTC)

Ok, so i only understand Galois Theory vaguely, my reference to analysis is mainly to constructivist analysis (again only a vague understanding), but from the description it would seem to have something to do with constructing the possible solutions from allowable moves.

After having played a lot more, here are a few nifty shortcuts. If your puzzle has one color in such a pattern that their are at most two dead ends (that is say a black square with three white ones adjacent to it) then it is basically analogus to a Hamiltonian circuit. the solution is generally very easy. If you have a one or more diagonals, try pathing right next to it, and then next to the path you created (a stair-step pattern). And if you have one vertical the is opposite colors it neighbor, you can usually solve these by pathing down the vertical (e.g. if you have a checkerboard pattern somwhere) With these few tricks and some logical thought, I can already solve most easy ones in under a minute and most moderately difficults ones in a few minutes tops. A math-wiki 22:52, 17 October 2007 (UTC)

The game is Polarium on the Nintendo DS, by the way. Don't know if the flash game is a rip-off or a proper version of it, but that's where I recognised it from.--PaulTaylor 22:57, 17 October 2007 (UTC)

I think it is a rip of Polarium, there is an acknowledgement of it at the bottom of the page. --Salix alba (talk) 07:29, 18 October 2007 (UTC)

I think I have a preliminary technique for finding general solutions. Consider the flipable rectangle, and m*n rectangle, that means your graph is an (m+2)x(n+2) set of vertices (remember that you can use the edge). All the vertices are linked in a "square lattice." There are 2ⁿ possible combinations of colors, meaning that their are that many graphs to analize in total, but it is often possible to cut down on that number significantly. What your do to create these graphs is select one of the color combinations and mark all the vertices that need to be flipped. Then look to see if the graph (including the extra edges) has a path sure that the degree of all but 2 of the vertice is 2, the two should be degree 1 "Hamiltonian Case"(unless the path starts and stops next to itself "Euler Case"). This may not be a general solution but it definately comes close. The one thing I have not throughly investigated is how the edge squares which are used "at will" affect possible paths, but it would seem to allow a few different choices for the pather, so they all should be checked. A math-wiki 23:57, 17 October 2007 (UTC)

Upon putting it to the test, the restriction that the degree need be 2 is not actually the case, just as long as those with degree 3 are adjancent and have their 3rd edge on the same side so that your can parallel your earlier path. All in all, logical thought is still the most efficient. A math-wiki 00:39, 18 October 2007 (UTC)

Hamiltonian Case should be called Hamiltonian path Case, and Euler Case should be called Hamiltonian circuit Case. A math-wiki 00:54, 18 October 2007 (UTC)

It seems likely to be NP-complete, as it's closely related to finding Hamiltonian paths in a grid graph (A. Itai, C.H. Papadimitriou, J.L. Szwarcfiter, Hamiltonian paths in grid graphs, SIAM J. Comput. 11 (1982) 676–686.) If so, there wouldn't be a simple strategy that would be guaranteed to always work: you'd have to actually think to solve it. —David Eppstein 07:47, 18 October 2007 (UTC)