[Home] [Puzzles & Projects] [Delphi Techniques] [Math topics] [Library] [Utilities]
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.
A new, simple object type, TPathToHere, is defined containing only two fields:
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 2N-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.
Suggestions for Further Explorations
Copyright © 2000-2017, Gary Darby All rights reserved.