[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
|
|
Problem DescriptionThe original version of the Token Flip puzzle was published two years ago. We are given a square board covered with tokens, black on one side and white on the other. The objective is to turn the board all white in as few moves as possible by flipping tokens from a given staring position. The complication is that when a token is turned, the adjacent tokens directly above, below, right, and left of the flipped token are also flipped. Thus each move may result in three to five tokens being reversed. Here's a sample from the original version can be solved 3 moves -by clicking the tokens in (Col 3, Row 1), (Col 2, Row 3), (Col 3, Row 4)
The moves required to solve these puzzles are not very
intuitive, in fact solving in sizes above 5X5 is quite difficult - this is also
true for the program's attempts to solve the puzzle by a brute force
search. Until now. Flip - the Final chapter can
solve puzzle of any practical size and do it very quickly. (The one shown
here left requires clicking on 54 of the 100 tokens!)
Background & TechniquesA couple of revisions in the past two years has increased the solvable puzzle size from 4X4 to 5X5 and the displayable puzzle size up to 10X10, In March, 2003 I requested user help finding a way to solve the 10X10 puzzle and viewer Bernd Hellema (email: B.Hellema@zonnet.nl), came through! Bernd has done some great work in mathematically analyzing the game and provided the routines to solve boards of any practical size (he says 1000X1000 does take a few seconds though!). Bernd's approach uses linear algebra for solving a set of equations describing the results of clicking on a set of tokens. Two key characteristics of the puzzle:
What are the equations? Using a 3x3 board as an example, number the tokens from 1 through 9 from left to right by row.
Now if we define T1..T9 as the initial token color values
(0=black, 1=white), and X1..X9 as the "click values" for
each of the 9 tokens (0=no click, 1 = click). Then the 9 equations to be
solved would look like this (X1+X2+X4+T1) mod 2 =1 Bernd actually solves the equivalent set: (X1+X2+X4) mod 2 =(1+T1) mod 2 Note that each equation can be treated as containing all nine variables, X1 to X9, with the coefficients of each variable either 0 or 1, so we are solving 9 simultaneous equations in 9 unknowns. Linear algebra is the best and fastest tool for solving such systems of equations. The original solve procedure has been replaced with the unit U_Bernd which contains the Delphi version of Bernd's original Pascal code. Addendum 8/21/2003: While working on converting Bernd's code from Pascal to Delphi, I noticed that it did not return the minimal length game in all cases. (Specifically, the all black 4X4 board can be solved in 4 moves, but the program returned a 10 move solution.) I mentioned that to Bernd, and a few days later he sent me a version that checks all solutions and returns the shortest. I kind of dropped the ball though and just got around to posting it today. So re-download the program if you want the version of Token Flip than returns optimal solutions. Running/Exploring the Program
Suggestions for Further Explorations
|
[Feedback] [Newsletters (subscribe/view)] [About me]Copyright © 2000-2018, Gary Darby All rights reserved. |