CS3361 Spring 1996
Introduction to Artificial Intelligence
Example 1: A C program to do the 8 Puzzle.
Missing Features
/************************************************/
/* 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 < 100; depth++ )
{
expand_search_tree_by_one( search_tree );
if ( on_solution_path( search_tree ) )
break;
printf( "Finished depth %d: %d total nodes\n", depth, n_nodes );
}
printf( "Total depth %d: %d total nodes\n", depth, n_nodes );
print_out_solution( search_tree );
printf( "Total depth %d: %d total nodes\n", depth, n_nodes );
}
/************************************************/
NODE *
malloc_node()
{
NODE *node;
int i;
node = (NODE *) malloc( sizeof(NODE) );
if ( node == NULL )
{
fprintf( stderr, "failure in allocating cell in malloc_node()\n" );
exit( -1 );
}
for( i = 0; i < N_POSITIONS; i++ )
node->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 < N_POSITIONS; i++ )
repeats[i] = 0;
for( i = 0; i < N_POSITIONS; i++ )
{
if( scanf( "%d", &(value) ) < 1 )
{
fprintf( stderr, "Error reading input: %d\n", i );
exit( -1 );
}
if ( value < 0 || value > 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 < MAX_N_MOVES; i++ )
{
child->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 < N_POSITIONS; i++ )
{
if ( node->state[i] == HOLE )
break;
}
hole_position = i;
piece_position = moves[hole_position][index];
if ( piece_position < 0 )
return NULL;
/* Make new node */
result = malloc_node();
result->parent = node;
for( i = 0; i < N_POSITIONS; i++ )
{
result->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 < N_POSITIONS; i++ )
{
if ( node->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 );
}
/************************************************/