Template Metaprogramming and Puzzle 15 Optimal Solution

Here is a sample demonstrating how to accelerate finding an optimal Puzzle 15 solution using C++ Template Metaprogramming [1], [2]. It presents a self-descriptive and straightforward implementation of the IDA* search algorithm (Korf, 1985) [3]. It is interesting here how template meta-programming, along with optimizations made by the compiler, fit within this algorithm and make it work significantly faster. From another point of view, in some ways this implementation looks similar to functional programming.

Manhattan distance heuristics are used here. As soon as each move can cause a Manhattan distance change of either 1 or -1, the number of times the Manhattan distance increased during puzzle solution is used as a cost bound. Steepest Ascent Hill-Climbing order, cutting out, and back and forth move sequences are implemented as well. Of improved admissive heuristics [4], only non-interfering Linear Conflict, Last Moves, and Corner Tiles are implemented here for simplicity. Employing better heuristics would significantly increase search speed as well.

The test run parameters are:

puzzle.exe 15 14 _ 4 11 1 6 13 7 5 8 9 3 2 10 12

The result is:

Solved at 2.202 seconds. Number of moves: 66

and the solution log. The execution time is a couple of seconds, depending on the computer speed.

I have compared the application speed with that of elaborated one implemented by Ken'ichiro Takahashi (takaken) [5]. The solution using template metaprogramming (TM) is slower on the test example from takaken's site (1 5 9 13 2 6 10 14 3 7 11 15 4 8 12 0), 34131 sec. against 20813 sec. on a Pentium D 3.00 GHz. However, using examples from [6] gives quite different results:

Problem/Solution Time, in Seconds proposed (TM) by takaken
Problem 2 13 15 14 0 9 10 11 12 5 6 7 8 1 2 3 4 4128 133545
Problem 4 4 3 2 1 8 7 6 5 12 11 10 9 0 14 15 13 415 2533
Problem 6 15 14 13 12 11 10 9 8 7 6 5 4 3 1 2 0 90 239
Problem 12 0 12 9 13 15 11 10 14 7 8 5 6 4 3 2 1 940 961

It demonstrates that an approach described here is quite promising.

Besides generic console application, an interactive WPF based demo is available (requires Microsoft .NET Framework 3.0 or higher):

References

  1. "Template Metaprograms", Todd Veldhuizen
  2. "Generic<Programming>: Mappings between Types and Values", Andrei Alexandrescu
  3. "Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA*", Alexander Reinefeld
  4. "Finding Optimal Solutions to the Twenty-Four Puzzle," Richard E. Korf and Larry A. Taylor
  5. "15puzzle Optimal solver" for windows
  6. Problems from The 15 Puzzle by Jerry Slocum


Downloads

Comments

  • algorithm

    Posted by shieyda on 01/12/2013 04:21am

    hey...is it possible if i want the coding.??? please2

    Reply
  • drawing solution

    Posted by lightning3 on 07/19/2011 05:15am

    Hi I am very impressed by your Project. Please tell me it it possible to change method of drawing solution ? Do not draw every set after change, but draw ONLY numbers that changed. Same way as you enter numbers on Input regards

    Reply
  • Convert FLV to SWF

    Posted by 250baichi on 09/16/2009 05:54am

    I juest bought a Convert FLV to SWF --- Sharing Youtube video with folks On converting FLV to SWF, FLV to SWF Converter is relly the fantastic one. Using this tool, you can convert Youtube(.flv) video to swf and edit flv files before converting.

    Reply
Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • Live Event Date: February 25, 2015 @ 2:00 p.m. ET / 11:00 a.m. PT Secure Shell (SSH) keys provide unmitigated access for privileged users and applications. However, managing and securing these critical privileged credentials poses a real challenge for organizations, putting sensitive data at risk. In fact, more than 50% of organizations report experiencing an SSH Key related compromise. Check out this upcoming eSeminar and join Adam Bosnian, EVP of Global Business Development at CyberArk, as he discusses the …

  • Live Event Date: February 11, 2015 @ 1:00 p.m. ET / 10:00 a.m. PT New computing platforms, expanding information environments, recurrent security breaches and evolving regulatory frameworks are factors that security executives must contend with and address when developing their security strategy. In response to these dynamics, security executives are seeking stronger, more nimble and more pervasive security technologies to help protect business-critical information from unauthorized disclosure, loss or …

Most Popular Programming Stories

More for Developers

RSS Feeds

Thanks for your registration, follow us on our social networks to keep up-to-date