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

Problem Description

Given seven nickels with heads up, reverse them so that they are all heads down by inverting five coins in each move.

Background & Techniques

This puzzle is from one of my favorite puzzle books "Play Thinks".  My implementation was expanded to allow users to specify the number of coins and the number which must be flipped on each turn.   This puzzle provided a good excuse for a little "brain think" of the automated solving variety.

First the math to figure out how many configurations of the 7 coins are possible when 5 are inverted at a time.  The answer is the number of ways that we can choose the five to invert.  There are 7 ways to choose the first coin to flip, but only 6 ways for the second, 5 ways for third, etc. So altogether there are  7x6x5x4x3=2520.  This is the number of permutations of 7 things taken 5 at a time.  But since the order of selecting the coins doesn't matter, we  need to reduce this number by the number of ways in which could have selected the 5. Thus will give the number of combinations of 7 things chosen 5 at a time.  This number ways to pick the 5 is  5! (5 factorial) = 5x4x3x2x1= 120.  So the number of combinations (let's call them "boards" to save ink) that we need to check when moving from one board to the next is  only 2520/120=21 .   

The best way find the shortest solution is to perform a "breadth-first" search, where we generate all 21 boards by inverting 5 coins from the initial all heads, HHHHHHH, board.  None of those happen to be all Tails, TTTTTTT, so we'll generate the 21 possible boards from each of the 21 level 1 boards.  That will give us 441 (21 x 21) level 2 boards in all.   None of these are solutions either, but while working our way through the 9261 level 3 boards we'll find many solutions.  For the computer, generating and checking these 9261 boards is trivial.  Not so simple for humans though.  In the following section I'll describe the queue structure used to keep track of the boards and some of the other tricks used to generate and check them.           

Non-programmers are welcome to read on, but may want to jump to bottom of this page to download the executable program now.

Programmer's Notes:

A new, simple object type, TPathToHere, is defined containing only two fields:

·        Coins is an integer which defines a board configuration using the low order bits to identify the heads/tails status of each coin; bit = 0 for Heads and bit = 1 for Tails.  So, for example, the board HHHTTHT would be encoded as binary 0001101 or decimal 13.   

·        PathToHere is an array of integers representing the sequence of the moves (the test patterns) leading to the current state.   This allows us to display the moves leading to the solution once we find it. 

Let N represent the number of coins on the board and K represent the number of coins to flip for a move. The integer array, TestPatterns, is filled with all integers containing K bits in the low order N bits.  In our default case with N=7 and K=5, Testpatterns has 21 entries as described above.  The array is generated by testing integers from 0 to 2^N-1 (0 to 127 in our test case) and saving those that have K (5) bits in their binary representation.  Function Countbits returns the number of bits value.   

Given a board configuration, say HHHTTHT (decimal 13, binary 0001101) and a test pattern, say 31, binary 0011111, we can generate the resulting board configuration by applying the XOR (exclusive or) operation to the two numbers 13 XOR 31 = 0001101 XOR 0011111 = 0010010 = HHTHHTH; the 5 low order coins have flipped.  (The XOR operation operates bit by bit on two fields setting bits to "1" if one of the two bits being checked is 1 and to "0" if the bits being checked are both 0 or both 1.)  

To perform the breadth-first search, we’ll use the TObjectQueue Delphi control to build a First-in/First-out list of board positions generated. After adding the initial  TPathToHere object representing the  all heads configuration, we’ll enter a loop in which we “Pop” the first (oldest) entry off the queue which also removes it from the queue, then check to see if it represents a solution and if not, generate s and “Push” TPathToHere objects for  all the board positions which result from applying each of the TestPatterns entries to the popped Coins value.  Pushed objects are added to the end of the queue.  The loop continues until a solution is found or we decide that there is no solution and give up the search.  Currently we give up after the queue size reaches 100,000 entries with no solution found.   

The above describes the data structures and algorithm used to find solutions.  There are a few other "tricks" required for user play.  One is dynamically generating an array of TLabel controls to contain the H/T coin indicators.  Clicks on the letters change the font color and count user clicks to determine when to apply the move.  After each turn, the program checks to see if the puzzle has been solved and issues a "congratulations" message if so.  The letters representing coins could easily be changed to actual coin images if desired.

Running/Exploring the Program 

Suggestions for Further Explorations

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

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