Printable View
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).
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
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
And how would posting the final code here teach you anything? (other than how to copy code from the web?)
--
Mats
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.Quote:
Originally Posted by LordMX
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
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:
Not sure if you will get my point...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);
}
Post what you have tried and what you are stuck on and we will help.
EDIT: deleted. Didn't fully read 1st post....
It's probably like those little tile games where you can shuffle pieces to make a picture. But the OP doesn't specify.Quote:
Originally Posted by rasta_freak
Yes, it's more than sorting (as i firstly assumed).Quote:
Originally Posted by noops
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.Quote:
Originally Posted by LordMX
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.
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
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.
BTW-I found this open source code here:
BUT, I can't compile this code?Code:/************************************************/
/* CS3361: Assignment 2. Solve an eight puzzle. */
/************************************************/
/* INCLUDES */
#include <stdio.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 );
}
/************************************************/
Can someone compile this?
What do you mean? Do you get errors, or you haven't got a compiler or something else?Quote:
Originally Posted by LordMX
--
Mats
Mats,
Nothing more than a complete copy/paste FAIL! Well-deserved, I may add :)
Ah, I see what you mean - the HTML-isation of the source code "gone bad". I didn't actually LOOK at the code when I asked the questions, because I wanted the OP to "Ask Smart Questions", not just dump a bunch of source and hope that we can fix it.Quote:
Originally Posted by rags_to_riches
--
Mats