branch and bound

This is a discussion on branch and bound within the C Programming forums, part of the General Programming Boards category; I need the algorithm with explanation in C to solve the well known 15 puzzle problem.If not possible to give ...

  1. #1
    Registered User
    Join Date
    Aug 2012
    Posts
    73

    Post branch and bound

    I need the algorithm with explanation in C to solve the well known 15 puzzle problem.If not possible to give the entire source code here please give me an idea how to device the solution to this problem.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by progmateur View Post
    I need the algorithm with explanation in C to solve the well known 15 puzzle problem.If not possible to give the entire source code here please give me an idea how to device the solution to this problem.
    Wikipedia has a pretty good entry for many algorithms, along with the pseudo code for it (which is like C in many ways).

    I googled a site that had a 15 puzzle animation on it, and played it until I grokked a pattern I liked, and used that pattern for the program. As I recall, it's logic was to bring the tile up to the row below where it should go, and to the far right hand column. Tiles that didn't belong in the row just above it, were then removed, and the proper tile slid up, with the necessary adjustments. That worked fine for the first two rows. For the last two rows, I got quite explicit with it, which I shouldn't have*, but I wanted it to solve it VERY fast.

    One big tip: You may know this already, but the puzzle has a "handedness" to it. About half the configurations for it, will have the wrong "hand", and can't be solved at all. For this reason, it's important to get only puzzle starting positions, that have the correct "hand" to them. Otherwise, you're up against a brick wall.

    *With the explicit code for the last two rows, the whole program became very long and relatively "ugly", imo.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Best way to conditionally branch this?
    By roll cast in forum C++ Programming
    Replies: 6
    Last Post: 11-02-2011, 01:22 PM
  2. A way to branch structures
    By kiros88 in forum C Programming
    Replies: 2
    Last Post: 09-11-2009, 12:55 PM
  3. Compile GCC Branch
    By Dae in forum Linux Programming
    Replies: 10
    Last Post: 09-06-2009, 02:33 AM
  4. branch
    By only1st in forum C++ Programming
    Replies: 2
    Last Post: 05-07-2007, 11:24 AM
  5. wxWidgets - branch moving
    By pixsta in forum C++ Programming
    Replies: 0
    Last Post: 01-27-2006, 09:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21