Thread: 8 Puzzle game solver with the Best-First algoritm

  1. #1
    Registered User
    Join Date
    Aug 2008
    Posts
    6

    Lightbulb 8 Puzzle game solver with the Best-First algoritm

    Hi, I have a big problem with the 8 puzzle solver application in C programming language, please, send me the source code in C (using the Best-First algoritm) if you can, I need it so desperate ...I'm running out of time for this source ...please

    The program needs to make first some random state for the puzzle, something like this:
    1 3 2
    _ 4 5
    8 6 7

    And then to solve the puzzle to this state:

    1 2 3
    8 _ 4
    7 6 5

    And then to print the solving path (start (random) state - path - goal state).
    Last edited by LordMX; 08-06-2008 at 07:22 AM.

  2. #2
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    That's not how things work here. We do not do homework on demand - we will happily HELP you to learn and understand, but you will still have to work out the solution yourself.

    And don't even try saying "It isn't homework" - there is NO OTHER reason why you would want to solve that question and be desperate.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  3. #3
    Registered User
    Join Date
    Aug 2008
    Posts
    6
    Yes, it is the homework, and I'm glad to learn and undarstand this problem, BUT, I'm running out of time, and that is the reason why I ask you gays here...

    Chears

  4. #4
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    And how would posting the final code here teach you anything? (other than how to copy code from the web?)

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  5. #5
    Registered User
    Join Date
    Aug 2008
    Posts
    6
    When I get the source code I still have to understand how it works and to explaine that , it is not only copy paste like you said...

    ...btw it looks like you are to aggressive with posts like that, if you don't want to help than say so.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by LordMX View Post
    When I get the source code I still have to understand how it works and to explaine that , it is not only copy paste like you said...

    ...btw it looks like you are to aggressive with posts like that, if you don't want to help than say so.
    You are correct. I like to help people, but I do not like people who cheat. And getting your homework solved by someone else is cheating. And understanding source is quite a bit different from writing source code.

    Unfortunately, this forum [and many others like it, I'm sure] do get requeists like this quite often, and my tone would maybe have been different if you had been the only one in the past week to approach this site for such a problem.

    Now, if you have written ANY code on the subject, perhaps you can post that, and we can help you solve the problem(s) you have. It would help if you ask SPECIFIC questions, such as "I can do X, but when I do Y then A happens, but I want B to happen".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Even if we were to do your homework for you you have not even posted enough information to do so. We have no idea how the puzzle should be solved. If it were me, based on your requirements, I would just write a program that did this:

    Code:
    #include <stdio.h>
    
    int main(void)
    {
         int solution[3][3] = {{1, 2, 3},{8, _, 4}, {7, 6, 5}};
         int i = 0,
             j = 0;
         for (i = 0; i < 3; i++)
         {
              for (j = 0; j < 3; j++)
              {
                   printf("%d ", solution[i][j]);
              }
              printf("\n");
         }
         return(0);
    }
    Not sure if you will get my point...

    Post what you have tried and what you are stuck on and we will help.

  8. #8
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    EDIT: deleted. Didn't fully read 1st post....
    Last edited by rasta_freak; 08-06-2008 at 10:59 AM.

  9. #9
    * noops's Avatar
    Join Date
    Jun 2008
    Posts
    108
    Quote Originally Posted by rasta_freak View Post
    Isn't this just sorting of integers (with qsort() and helper function, or manually) from lowest to highest, and then displaying/arranging them in this 'circular' pattern ?
    It's probably like those little tile games where you can shuffle pieces to make a picture. But the OP doesn't specify.

  10. #10
    Registered User
    Join Date
    Jul 2008
    Posts
    133
    Quote Originally Posted by noops View Post
    It's probably like those little tile games where you can shuffle pieces to make a picture. But the OP doesn't specify.
    Yes, it's more than sorting (as i firstly assumed).

  11. #11
    Registered User
    Join Date
    Aug 2008
    Posts
    6
    In this game we must use Best-First algoritm for the searching the corect path for solving the puzzle.

    "Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule." - (from wikipedia)

    That is all I know

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by LordMX View Post
    In this game we must use Best-First algoritm for the searching the corect path for solving the puzzle.

    "Best-first search is a search algorithm which explores a graph by expanding the most promising node chosen according to some rule." - (from wikipedia)

    That is all I know
    So you need to come up with a rule, then.

    First off, you need to make sure you know the rules of the game -- at any given moment, what plays are there available. Decide which is the "best" (that's your rule you need to come up with) and follow that forward and see what happens.

  13. #13
    Registered User ssharish2005's Avatar
    Join Date
    Sep 2005
    Location
    Cambridge, UK
    Posts
    1,732
    Well, it’s not going to be that simple as you think! The problem needs to go through quite a few phases before you can get the solution for it. My first question for is DO you know how the Best-First search function works?

    The first few phases are that, for any given location on the node, you need to find the successor states from that current location. What I mean by the successor states here, is that, the next possible moves which you can.

    You will have to write a function called Legal Move Generator (LMG) to actual build a parser tree. And then you apply BSF on to that tree to find the best path. Have a look at minmax algorithm that might give you some idea as well.

    ssharish

  14. #14
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    This is quite a difficult task regardless of the programming language used to solve it. I can't off hand think up what the rule for deciding which of the aviailable moves is the most promising, would be. The obvious one would be one which puts a number in its final position, but often there are no such moves that do this. You could also consider a move that takes a piece out of its final place as the least promising. But that doesn't tell you what order you'd try other moves in.
    Hunting around it seems that a reasonable heuristic is to count the number of pieces that are out of their row plus those that are out of their column.

    Ultimately, if you aren't both a capable C programmer AND good with algorithms, then you probably aren't going to be able to complete this assignment. Nobody here is going to just do it for you either. Best idea is for you to get cracking and write as much of it as you possibly can, regardless of how little that is, and hope for partial credit.
    I hope you learn not to procrastinate on your assignments next time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  15. #15
    Registered User
    Join Date
    Aug 2008
    Posts
    6
    BTW-I found this open source code here:

    Code:
    /************************************************/
    /* CS3361: Assignment 2. Solve an eight puzzle. */
    /************************************************/
    /* INCLUDES */
    
    #include &ltstdio.h>
    
    /************************************************/
    /* DEFINES */
    
    #define FALSE 0
    #define TRUE 1
    #define N_POSITIONS 9
    #define MAX_N_MOVES 4
    #define NO_FLAGS 0
    #define ON_SOLUTION_PATH 1
    #define NO_SOLUTION 0
    #define FOUND_SOLUTION 1
    #define HOLE 0
    #define NO_PIECE 255
    
    /************************************************/
    /* TYPEDEFS */
    
    /* The state will be a vector of 9 integers
    (stored in unsigned chars).
    4 2 6
    1 3 _
    5 8 7
    is represented as
    { 4, 2, 6, 1, 3, 0, 5, 8, 7}
    */
    
    typedef unsigned char STATE[ N_POSITIONS ];
    
    /* A node in the search tree: */
    
    typedef struct node
    {
      STATE state;
      unsigned char piece_moved;
      struct node *sibling;
      struct node *first_child;
      struct node *parent;
      int flags;
    }
    NODE;
    
    /************************************************/
    /* GLOBALS */
    
    /* First, let's put the rules in a lookup table.
    We index the table by where the hole is, and look
    up which positions the hole can move to.
    The square indices are
    0 1 2
    3 4 5
    6 7 8
    A -1 in an entry indicates that that position does not
    have this many moves.
    */
    
    int moves[ N_POSITIONS ][ MAX_N_MOVES ] =
    {
    /* From 0: */  { 1, 3, -1, -1 },
    /* From 1: */  { 0, 2, 4, -1 },
    /* From 2: */  { 1, 5, -1, -1 },
    /* From 3: */  { 0, 4, 6, -1},
    /* From 4: */  { 1, 3, 5, 7},
    /* From 5: */  { 2, 4, 8, -1},
    /* From 6: */  { 3, 7, -1, -1},
    /* From 7: */  { 4, 6, 8, -1},
    /* From 8: */  { 5, 7, -1, -1}
    };
    
    /* We need to know what the solution should look like: */
    int solution[ N_POSITIONS ] = { 1, 2, 3, 4, 5, 6, 7, 8, 0 };
    
    int n_nodes = 0; /* Keep count of the number of nodes created. */
    
    /************************************************/
    /* MAIN */
    
    main()
    {
      NODE *search_tree, *solution;
      NODE *malloc_node();
      int depth;
    
      /*
      printf( "A node is %d bytes\n", sizeof( NODE ) );
      */
    
      search_tree = malloc_node();
    
      read_initial_state( search_tree->state );
      for( depth = 1; depth state[i] = i;
      node->piece_moved = NO_PIECE;
      node->sibling = NULL;
      node->first_child = NULL;
      node->parent = NULL;
      node->flags = NO_FLAGS;
    
      n_nodes++;
      return node;
    }
    
    /************************************************/
    
    read_initial_state( state )
         STATE state;
    {
      int i;
      int value;
      int repeats[N_POSITIONS];
    
      printf( "Please type in the initial position of the squares\n" );
      printf( "Give each row from top to bottom in left to right order\n" );
      for( i = 0; i  8 )
        {
          fprintf( stderr,
          "Illegal value %d in position %d, values must between 0 and 8.\n",
              value, i );
          exit( -1 );
        }
          if ( repeats[value] > 0 )
        {
          fprintf( stderr, "Duplicate value %d in position %d.\n", value, i );
          exit( -1 );
        }
          repeats[value] = 1;
          state[i] = (unsigned char) value; /* Do type conversion */
        }
      printf( "Input read:\n" );
      print_board( state );
    }
    
    /************************************************/
    
    print_board( state )
         STATE state;
    {
      printf( "%d %d %d\n", state[0], state[1], state[2] );
      printf( "%d %d %d\n", state[3], state[4], state[5] );
      printf( "%d %d %d\n", state[6], state[7], state[8] );
    }
    
    /************************************************/
    /* Recursive version: Beware of stack overflow */
    
    expand_search_tree_by_one( node )
         NODE *node;
    {
    
      if ( node == NULL )
        {
          fprintf( stderr, "Consistency check 1 failed\n" );
          exit( -1 );
        }
      if ( node->first_child == NULL )
        generate_moves( node );
      else
        expand_search_tree_by_one( node->first_child );
    
      /* Propagate solution */
      if ( on_solution_path( node ) && node->parent != NULL )
        {
          node->parent->flags |= ON_SOLUTION_PATH;
          return;
        }
    
      if ( node->sibling != NULL )
        expand_search_tree_by_one( node->sibling );
    }
    
    /************************************************/
    
    generate_moves( node )
         NODE *node;
    {
      NODE *make_move();
      NODE *child;
      int i;
    
      child = make_move( node, 0 );
      node->first_child = child;
      if ( is_solution( child ) )
        {
          node->flags |= ON_SOLUTION_PATH;
          return FOUND_SOLUTION;
        }
      for( i = 1; i sibling = make_move( node, i );
          if ( child->sibling == NULL )
        return NO_SOLUTION;
          if ( is_solution( child->sibling ) )
        {
          node->flags |= ON_SOLUTION_PATH;
          return FOUND_SOLUTION;
        }
          child = child->sibling;
        }
      return NO_SOLUTION;
    }
    
    /************************************************/
    
    NODE *make_move( node, index )
         NODE *node;
         int index;
    {
      int i, hole_position, piece_position;
      NODE *result;
    
      /* Find hole */
      for( i = 0; i state[i] == HOLE )
        break;
        }
      hole_position = i;
      piece_position = moves[hole_position][index];
      if ( piece_position parent = node;
      for( i = 0; i state[i] = node->state[i];
        }
      /* Swap hole and other piece. */
      result->state[hole_position] = node->state[piece_position];
      result->state[piece_position] = node->state[hole_position];
      result->piece_moved = node->state[piece_position];
    
      /*
      printf( "From\n" );
      print_board( node->state );
      printf( "Generating\n" );
      print_board( result->state );
      */
    
      return result;
    }
    
    /************************************************/
    
    is_solution( node )
         NODE *node;
    {
      int i;
    
      for( i = 0; i state[i] != solution[i] )
        return FALSE;
        }
      node->flags |= ON_SOLUTION_PATH;
      return TRUE;
    }
    
    /************************************************/
    
    on_solution_path( node )
         NODE *node;
    {
      if ( ( node->flags & ON_SOLUTION_PATH ) == 0 )
        return FALSE;
      else
        return TRUE;
    }
    
    /************************************************/
    
    print_out_solution( node )
         NODE *node;
    {
      if ( node == NULL )
        return;
      if ( on_solution_path( node ) )
        {
          if ( node->piece_moved != NO_PIECE )
        {
          printf( "Piece %d moved.\n", node->piece_moved );
          print_board( node );
        }
          else
        {
          printf( "Starting postion:\n" );
          print_board( node );
        }
          print_out_solution( node->first_child );
        }
      else
        print_out_solution( node->sibling );
    }
    
    /************************************************/
    BUT, I can't compile this code?

    Can someone compile this?

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Open-source Game Project
    By Glorfindel in forum Projects and Job Recruitment
    Replies: 0
    Last Post: 03-24-2009, 01:12 AM
  2. 20q game problems
    By Nexus-ZERO in forum C Programming
    Replies: 24
    Last Post: 12-17-2008, 05:48 PM
  3. Open Source / Semi Open source game idea. Help needed
    By CaptainPatent in forum Projects and Job Recruitment
    Replies: 10
    Last Post: 05-16-2007, 10:44 AM
  4. game engine advice?
    By stien in forum Game Programming
    Replies: 0
    Last Post: 01-23-2007, 03:46 PM
  5. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM