[Home]   [Puzzles & Projects]    [Delphi Techniques]   [Math topics]   [Library]   [Utilities]

Problem Description

The 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 & Techniques

A 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: 

1. The order of clicking on the tokens doesn't matter
2. A second click on a token exactly reverses the effect of the first click, so any solvable puzzle can be solved  no click or only a single click on each token    

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
 (X1+X2+X3+X5+T2) mod 2 =1
 (X2+X3+X6+T3) mod 2 =1 
.
.
.
(X6+X8+X9+T9) mod 2 =1

Bernd actually solves the equivalent set:

(X1+X2+X4) mod 2 =(1+T1) mod 2
 (X1+X2+X3+X5) mod 2 =(1+T2) mod 2
 (X2+X3+X6) mod 2 =(1+T3) mod 2 
.
.
.
(X6+X8+X9) mod 2 =(1+T9) 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

Even though this version is labeled,  the "Final Chapter", when I noticed that there were a few cases where the program did not produce the shortest solution, Bernd went to work and whipped out a "Final Final"  version.  I'll be post it  "real soon now".  (Done 8/21/03!)

  [Feedback]   [Newsletters (subscribe/view)] [About me]

Copyright © 2000-2018, Gary Darby    All rights reserved.