Token Flip Puzzle

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

 

 

Search

Search WWW

Search DelphiForFun.org

As of October, 2016, Embarcadero is offering a free release of Delphi (Delphi 10.1 Berlin Starter Edition ).     There are a few restrictions, but it is a welcome step toward making more programmers aware of the joys of Delphi.  They do say "Offer may be withdrawn at any time", so don't delay if you want to check it out.  Please use the feedback link to let me know if the link stops working.

 

Support DFF - Shop

 If you shop at Amazon anyway,  consider using this link. 

     

We receive a few cents from each purchase.  Thanks

 

Support DFF - Donate

 If you benefit from the website,  in terms of knowledge, entertainment value, or something otherwise useful, consider making a donation via PayPal  to help defray the costs.  (No PayPal account necessary to donate via credit card.)  Transaction is secure.

Mensa® Daily Puzzlers

For over 15 years Mensa Page-A-Day calendars have provided several puzzles a year for my programming pleasure.  Coding "solvers" is most fun, but many programs also allow user solving, convenient for "fill in the blanks" type.  Below are Amazon  links to the two most recent years.

Mensa® 365 Puzzlers  Calendar 2017

Mensa® 365 Puzzlers Calendar 2018

(Hint: If you can wait, current year calendars are usually on sale in January.)

Contact

Feedback:  Send an e-mail with your comments about this program (or anything else).

Search DelphiForFun.org only

 

 

 

 

Problem Description

Here's a simple puzzle (game?) that's not so easy.  16 tokens, black on one side and white on the other, are arranged on a 4X4 board.  The objective is to turn the board all white in as few moves as possible by flipping tokens.  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.    Each move may result in one to five tokens being reversed.   

Here's a sample that can be solved 3 moves -by clicking the tokens in (Col 3, Row 1), (Col 2, Row 3), (Col 3, Row 4)  

Background & Techniques

I ran across this problem in the ACM Programming Contest archive web pages. Implemented  here is a version that allows user play as well as program solve.  The board is a DrawGrid with an OnDrawCell exit to draw the tokens.   An OnClick event exit for the Drawgrid is used to implement user play.   

I couldn't find any references to the game, so I'm not sure that it has been analyzed.  There is no obvious measure of the path from a starting position to the all white target position.  In fact, most randomly generated board configurations seem to have no solution.  

I decided to use a breadth first graph search to find solutions.   Recall these pertinent aspects of breadth first searching.  ("Next" and "adjacent" here refer to board configurations that are one move from the current configuration.)

bulletStarting with the initial configuration, make a queue of all valid next positions.
bulletExamine the queue on a first in, first out basis.  For each entry, check to see if it is a solution and, if not,  add adjacent positions that have not  already been generated to the queue.   As we add these positions, we also need to keep track of the path that led to this configuration.
bulletWhen the solution is found, the path is the solution.

In order to conserve memory, I created a TBoard class defining board configurations as 16 bit words.  "1" bits in the word represent white tokens and "0" bits represent black tokens.   I decided to used the TIntList control to create an integer list for the queue of positions being searched.  (TIntList is a  list similar to TStringlist, but with integer members described here).   The integer used for entries in the list are the 16 bit numbers that reflect the board configuration.  The TBoard instance is added as an object with each entry to carry the score and path information as well.

I added  a Path array to the TBoard definition to contain  the list of moves that led to this configuration.    

There is a 'Build mode" button which allows individual tokens to be flipped without affecting adjacent tokens.  

Addendum:  November 24, 2002:  Version 2 posted today allows board sizes up to 7X7.   The breadth first solution technique described above was replaced by a one that generates trial solutions as combinations of N moves selected from size2  possible move locations.  (This technique takes advantage of the fact that the order of moves is not significant in this game.)    The new technique can solve boards up to 5X5 in a few minutes.   Beyond 5x5 it seems like we'll need to find some intelligent heuristics that will prune the search space dramatically.

Addendum: March 17, 2003:  At the request of a viewer, maximum board size has been  increased to 10X10. although the exhaustive solution search technique will is still not feasible beyond 5X5.  

Addendum: April 16, 2003:   A viewer supplied a method, and Pascal code, which finally closes the book on auto-solving large puzzles.   He cleverly set up the problem as a system of linear equations and solves it using linear algebra matrix techniques.  Check it out at Token Flip - The Final Chapter  

 

Running/Exploring the Program 

bulletBrowse source extract
bulletDownload source
bulletDownload  executable

Suggestions for Further Explorations

I would like to analyze all 65,535 board positions to see the distribution of solution lengths.  Experimentally, most solutions seem to be 4 or 5  moves long.   Randomly generated boards will generally have no solution.    So what property determines if a particular configuration is solvable?    What is the longest solvable configuration?  (The longest I have seen is 7 moves.)
This would be an ideal application to play with the application.onidle exit or thread processing.  The next board to be displayed could be generated in the background so that a "best possible"  target  move count could be displayed with the board. 
This idea just occurred to me this morning while turkey hunting.  I believe that most of the solution CPU cycles are spent checking whether adjacent board configurations are already in the list.   The check could be much faster if the list were sorted, allowing use of the Find binary search method instead of the IndexOf sequential search.  Since it's only important that list sequence be maintained by depth of search, I think we could define the list as sorted and then multiply each of the 16 bit configuration keys by depth*65536 thus using the high portion of the key for depth information without affecting the 16 low order bits.  Multiple Finds would be required for all lower levels but that should still be much faster than IndexOf.        

  

Created: April 20, 2001

Modified: May 15, 2018

 
  [Feedback]   [Newsletters (subscribe/view)] [About me]
Copyright © 2000-2018, Gary Darby    All rights reserved.