bashuma.cpp

采用队列实现了八数码问题的求解

#include <stdio.h>

#define N           9
#define SIZE        362880
#define UP          0
#define RIGHT       1
#define DOWN        2
#define LEFT        3
#define FIXED       4

#define X_S         0
#define Y_S         2
#define VIS_S       4
#define DIR_S       5
#define PAR_S       8

#define X_MASK      0x00000003   // 0000 0000 0011   x pos mask
#define Y_MASK      0x0000000c   // 0000 0000 1100   y pos mask
#define VIS_MASK    0x00000010   // 0000 0001 0000   visited mask
#define DIR_MASK    0x000000e0   // 0000 1110 0000   direction mask
#define PAR_MASK    0xffffff00   // 1111 0000 0000   depth mask

#define GET_X( n )        ( ( (n)&X_MASK )>>X_S )
#define GET_Y( n )        ( ( (n)&Y_MASK )>>Y_S )
#define GET_VIS( n )      ( ( (n)&VIS_MASK )>>VIS_S )
#define GET_DIR( n )      ( ( (n)&DIR_MASK )>>DIR_S )
#define GET_PAR( n )      ( ( (n)&PAR_MASK )>>PAR_S )

#define SET_X( n,x )      ( ( (n)&=~X_MASK )|=(x<<X_S) )
#define SET_Y( n,y )      ( ( (n)&=~Y_MASK )|=(y<<Y_S) )
#define SET_VIS( n,vis )  ( ( (n)&=~VIS_MASK )|=(vis<<VIS_S) )
#define SET_DIR( n,dir )  ( ( (n)&=~DIR_MASK )|=(dir<<DIR_S) )
#define SET_PAR( n,par )  ( ( (n)&=~PAR_MASK )|=(par<<PAR_S) )

int aim[N] = { 1,2,3,4,5,6,7,8,0 }, aim_index;
int table[SIZE] = {0};
int open[SIZE/2+5] = {2,2};

int     ArrayToIndex( const int array[N] );
void    IndexToArray( int index, int array[N] );
bool    IsSolvable( int array[N] );
void    UpdateTable( int index, int x, int y, int father, int dir );
void    AddNewNode( int father );
void    PrintPath( int index );

int main( )
{
    char ch;
    int array[N], i, x, y, index;

    for( i=0; i<9; )
    {
        ch = getchar();
        if( ch!=' ' )
        {
            if( ch=='x' )
            {
                array[i] = 0;
                x = i/3;
                y = i%3;
            }
            else
                array[i] = ch-'0';
            i++;
        }
    }

    if( !IsSolvable( array ) )
        printf( "unsolvable" );
    else
    {
        aim_index = ArrayToIndex( aim );
        index = ArrayToIndex( array );
        UpdateTable( index, x, y, PAR_MASK, FIXED );
        open[open[1]++] = index;
        while( open[1] > open[0] )
        {
            index = open[open[0]];
            if( index==aim_index )
                break;
            open[0]++;
            AddNewNode( index );
        }
        PrintPath( aim_index );
    }

    return 0;
}

//////////////////////////////////////////////////////////////////////
void print( int array[N] )
{
    for( int i=0; i<N; i++)
        printf("%3d", array[i]);
    putchar(10);
}

void AddNewNode( int father )
{
    int x,y, p,q, dir;
    int array[N], index;

    IndexToArray( father, array );
    x   = GET_X( table[father] );
    y   = GET_Y( table[father] );
    dir = GET_DIR( table[father] );
    p   = 3*x+y;
    q   = -1;
    
    if( dir!=LEFT && y<2 )
    {
        q = 3*x+y+1;
        array[p] = array[q]; array[q] = 0;
        index = ArrayToIndex( array );

        if( !GET_VIS(table[index]) )
            UpdateTable(index, x, y+1, father, RIGHT);
    }
    
    if( dir!=RIGHT && y>0 )
    {
        if( q!=-1 ) { array[q] = array[p]; array[p] = 0; }

        q = 3*x+y-1;
        array[p] = array[q]; array[q] = 0;
        index = ArrayToIndex( array );

        if( !GET_VIS(table[index]) )
            UpdateTable(index, x, y-1, father, LEFT);
    }
    
    if( dir!=UP && x<2 )
    {
        if( q!=-1 ) { array[q] = array[p]; array[p] = 0; }

        q = 3*(x+1)+y;
        array[p] = array[q]; array[q] = 0;
        index = ArrayToIndex( array );

        if( !GET_VIS(table[index]) )
            UpdateTable(index, x+1, y, father, DOWN);
    }
    
    if( dir!=DOWN && x>0 )
    { 
        if( q!=-1 ) { array[q] = array[p]; array[p] = 0; }

        q = 3*(x-1)+y;
        array[p] = array[q]; array[q] = 0;
        index = ArrayToIndex( array );

        if( !GET_VIS(table[index]) )
            UpdateTable(index, x-1, y, father, UP);
    }
}

void UpdateTable( int index, int x, int y, int father, int dir )
{
    int t;
    SET_VIS( t, 1 );
    SET_DIR( t, dir );
    SET_PAR( t, father );
    SET_X( t, x );
    SET_Y( t, y );   
    table[index]  = t;

    if( index==aim_index )
        open[open[0]] = index;
    else
        open[open[1]++] = index;   
}

///////////////////////////////////////////////////////////////////////
int ArrayToIndex( const int array[N] )
{
    int i, j, t, index, pos[N];

    for( i=0; i<N; i++ )
        pos[ array[i] ] = i;

    for( i=0; i<N; i++ )
    {
        for( t=pos[i], j=0; j<t; j++ )
            if( array[j]>i )
                pos[i]--;
    }
    
    for( index=0, i=2; i<=N; i++ )
    {
        if( index&1 )
            index = index*i +pos[i-1];
        else
            index = index*i + i-1-pos[i-1];
    }

    return index;
}

void IndexToArray( int index, int array[N] )
{
    int i, j, t, pos[N]={0};

    for( i = N; i>1; i-- )
    {
        t = index%i;
        index = index/i;
        if( index&1 )
            pos[i-1] = t;
        else
            pos[i-1] = i-1-t;
    }

    for( i = 0; i<N; i++)
    {
        for( j = i; j>pos[i]; j-- )
            array[j] = array[j-1];
        array[ pos[i] ] = i;
    }
}

bool IsSolvable( int array[N] )
{
    int i,j, r1=0, r2=0;
    for( i=0; i<N; i++ )
    {
        if( array[i] )
        {
            for( j=0; j<i; j++ )
                if( array[j]>array[i] )
                    r1++;
        }
        if( aim[i] )
        {
            for( j=0; j<i; j++ )
                if( aim[j]>aim[i] )
                    r2++;
        }

    }

    return !((r2-r1)%2);
}

void PrintPath( int index )
{
    if( GET_DIR( table[index] )==FIXED )
        return;
    PrintPath( GET_PAR( table[index] ) );
    
    char dir;
    switch ( GET_DIR( table[index] ) )
    {
    case LEFT:
        dir = 'l'; break;
    case RIGHT:
        dir = 'r'; break;
    case UP:
        dir = 'u'; break;
    default:
        dir = 'd'; break;
    }
    printf("%c", dir );
}