Go back to Richel Bilderbeek's homepage.

Go back to Richel Bilderbeek's C++ page.

 

 

 

 

 

(C++) Refrigerator Puzzle Solver

 

This type of puzzle is also called a monkey puzzle [1].

 

Refrigerator Puzzle Solver was programmed to solve a puzzle on my refrigerator. I had a bet with my girlfriend that I could find the solution quicker by writing a program, than her trying by hand. I won (as one would expect, see 'Calcalute the number of configurations to test').

 

  1. View a photo of the refrigerator puzzle (png)
  2. View a screenshot of 'Refrigerator Puzzle Solver' (png)
  3. Download the 'Refrigerator Puzzle Solver' Windows executable (version 1.0)(zip).
  4. Download the 'Refrigerator Puzzle Solver' source code (version 1.0)(zip).

 

Refrigerator Puzzle Solver was programmed at the 28th of December of 2008 in C++ using the IDE C++ Builder 6.0. It uses the STL, VCL and Boost libraries.

 

 

 

 

 

Calculate the number of configurations to test

 

The nine puzzle pieces can be put in 9*8*7*6*5*4*3*2*1 = 9! = 362880 sequences.

 

One puzzle piece has four orientations.

 

For a certain sequence of the nine pieces, there are 4^9=262144 configurations.

 

Therefore, the number of possibilities to test equals 362880 * 262144 = 95126814720.

 

Because there four solutions of the puzzle (due to rotation) one expects to need to test 95126814720 / 4 = 23781703680 configurations. That is more then 23 billion configurations!

 

 

 

 

 

How the program solves the puzzle

 

The program starts with an ordering of the nine puzzle pieces.

 

First, one or more puzzle pieces are rotated in a systematic way, as systematic as adding one to a four-digit number system.

 

Second, these (rotated) puzzle pieces are put in a recursive function. This function takes a set of used and fitting puzzle pieces and a set of unused puzzle pieces. It tries to put an unused puzzle piece in the next place, trying all unused pieces. If successful, the function calls itself with the (new) set of used puzzle pieces and the (new) set of unused puzzle pieces. If the function fails, it returns an empty solution.

 

Click on 'Display current' in the program to see the computer do this. Every try is shown for about 100 milliseconds, so one can actually see what happens.

 

 

 

 

 

References

 

  1. David Harel. Computers Ltd.: What They Really Can't Do. 2000. ISBN-10: 0198505558.

 

 

 

 

 

Licence

 

  The Refrigerator Puzzle Solver, program to solve a refrigerator puzzle
  Copyright (C) 2008 Richel Bilderbeek
 
  This program is free software: you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation, either version 3 of the License, or
  (at your option) any later version.
 
  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  GNU General Public License for more details.
  You should have received a copy of the GNU General Public License
  along with this program. If not, see <http://www.gnu.org/licenses/>.

 

 

 

 

 

Go back to Richel Bilderbeek's C++ page.

Go back to Richel Bilderbeek's homepage.

 

Valid XHTML 1.0 Strict