digit15.c

一个解决15数码的问题

#include <stdio.h>
#include <stdlib.h>

#define MAX     1000
#define BUFMAX  10
#define FALSE   0
#define TRUE    1   
#define BDMAX   5 
#define LEFT    1
#define RIGHT   2
#define UP     3
#define DOWN  4   


struct board
{
    int bd[BDMAX][BDMAX];
    int m,n;
    int father;
    int method;
    int direction;
};

struct queue
{
    struct board nqueue[MAX];
    int head,tail;
    int first,last;
};

struct queue q;
struct board startbd,endbd;

char path[4][20] = {                    
                    "-> Left",
                    "-> Right",
                    "-> Up",
                    "-> Down",
                   };       
    
void readText(char *text,struct board *startbd,struct board *endbd);    
void bfs(struct queue *q,struct board *n);
void init_queue(struct queue *q);
void en_queue(struct queue *q,struct board *a);
void de_queue(struct queue *q);
void rule(struct queue *q,struct board *n);
int bound(struct queue *q,struct board *n);
void display(struct queue *q,int i);
void copy_board1(struct board *to,struct board *from);
void copy_board2(struct board *to,struct board *from);
int is_equal(struct board *a,struct board *b);
void display_board(struct board *state);

int main(int argc, char *argv[])
{   
    readText("digit15.txt",&startbd,&endbd);    
    
    startbd.father = -1;
    startbd.method = -1;
    startbd.direction = -1;
    
    bfs(&q,&startbd);
    
    return EXIT_SUCCESS;
}

void init_queue(struct queue *q)
{
    q->head = 1;
    q->tail = 1;
    q->first = 1;
    q->tail = 1;
}

void en_queue(struct queue *q,struct board *a)
{    
    copy_board1(&q->nqueue[q->tail],a);
        
    q->tail++;
    q->last++;
}

void de_queue(struct queue *q)
{
    q->head++;
}

void bfs(struct queue *q,struct board *n)
{
    int i;
    
    init_queue(q);
    en_queue(q,n);
    
    while(1)
    {
        de_queue(q);
        if(!is_equal(&endbd,&q->nqueue[q->head - 1]))
        {
            rule(q,&q->nqueue[q->head - 1]);
        }  
        else
        {
            printf("Total States:%d\n",q->last - q->first);
//             for(i = q->first; i < q->last; i++)
//             {
//                 display_board(&q->nqueue[i]);
//             }
            printf("Start State:\n");
            display(q,q->head - 1); //important q->head - 1,not qstore->tail - 1
            return;
        } 
    }
}

void rule(struct queue *q,struct board *a)
{
    struct board nd; 
      
    if(a->n >= 2)
    {
        if(a->direction != RIGHT)
        {
            copy_board2(&nd,a);
            nd.bd[nd.m][nd.n] = nd.bd[nd.m][--nd.n];
            nd.bd[nd.m][nd.n] = 0;
            nd.method = 0;
            nd.father = q->head - 1; // q->head - 1 = bound(qstore,a)
            nd.direction = LEFT;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd);  
            }
        }
    }
    
    if(a->n <= 3)
    {
        if(a->direction != LEFT)
        {
            copy_board2(&nd,a);
            nd.bd[nd.m][nd.n] = nd.bd[nd.m][++nd.n];
            nd.bd[nd.m][nd.n] = 0;
            nd.method = 1;
            nd.father = q->head - 1; // q->head - 1 = bound(qstore,a)
            nd.direction = RIGHT;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
            }
        }
    }
    
    if(a->m >= 2)
    {
        if(a->direction != DOWN)
        {
            copy_board2(&nd,a);
            nd.bd[nd.m][nd.n] = nd.bd[--nd.m][nd.n];
            nd.bd[nd.m][nd.n] = 0;
            nd.method = 2;
            nd.father = q->head - 1; // q->head - 1 = bound(qstore,a)
            nd.direction = UP;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
            }
        }
    }
    
    if(a->m <= 3)
    {
        if(a->direction != UP)
        {
            copy_board2(&nd,a);
            nd.bd[nd.m][nd.n] = nd.bd[++nd.m][nd.n];
            nd.bd[nd.m][nd.n] = 0;
            nd.method = 3;
            nd.father = q->head - 1; // q->head - 1 = bound(qstore,a)
            nd.direction = DOWN;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
            }
        }
    }
}

int bound(struct queue *q,struct board *n)
{
    int i;
    
    for(i = q->first; i < q->last; i++)
    {
        if(is_equal(&q->nqueue[i],n))
        {
            return i;
        }
    }
    
    return FALSE;
}

void copy_board1(struct board *to,struct board *from)
{
    int i,j;
    
    to->m = from->m;
    to->n = from->n;
    to->father = from->father;
    to->method = from->method;
    to->direction = from->direction;
    
    for(i = 1; i < BDMAX; i++)
    {
        for(j = 1; j < BDMAX; j++)
        {
            to->bd[i][j] = from->bd[i][j];
        }
    }   
}

void copy_board2(struct board *to,struct board *from)
{
    int i,j;
    
    to->m = from->m;
    to->n = from->n;
    to->father = from->father;
    to->method = from->method;
    to->direction = from->direction;
    
    for(i = 1; i < BDMAX; i++)
    {
        for(j = 1; j < BDMAX; j++)
        {
            to->bd[i][j] = from->bd[i][j];
        }
    }   
}

int is_equal(struct board *a,struct board *b)
{   
    int i,j;
    
    for(i = 1; i < BDMAX; i++)
    {
        for(j = 1; j < BDMAX; j++)
        {
            if(a->bd[i][j] != b->bd[i][j])
            {
                return FALSE;
            }
        }
     }
     
     return TRUE;   
}

void display(struct queue *q,int i)
{    
    if(q->nqueue[i].father != -1)
    {
        display(q,q->nqueue[i].father);
    }    
    
    if(q->nqueue[i].method != -1)
    {
        printf("  %s\n",path[q->nqueue[i].method]);
    }
    display_board(&q->nqueue[i]);
}

void display_board(struct board *state)
{    
    int i,j,k;
    
    printf("m = %d,n = %d\n",state->m,state->n);
    for(i = 1; i < BDMAX; i++)
    {
        for(j = 1; j < BDMAX; j++)
        {
            printf("%2d ",state->bd[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void readText(char *text,struct board *startbd,struct board *endbd)
{
    FILE *fp;
    char buf[BUFMAX];
    char c;
    int i,j,k;
      
    if((fp = fopen(text,"r")) == NULL)
        {
            printf("Read Text Error!\n");
            return;
        }
    
    j = 1;
    while(1)
    {
        k = 1;
        while((c = fgetc(fp)) == ' ');
        if(c == EOF)
        {
            fclose(fp);
            
            display_board(startbd);
            display_board(endbd); 
            return;
        }
        i = 0;
        buf[i++] = c;
        while((c = fgetc(fp)) != ' ')
            buf[i++] = c;   
        buf[i] = '\0';            
        if(j < BDMAX)
        {   
            startbd->bd[j][k] = atoi(buf);
            if(startbd->bd[j][k++] == 0)
            {
                startbd->m = j;
                startbd->n = k - 1;
            }                
        }
        else
        {
            endbd->bd[j - BDMAX + 1][k] = atoi(buf);
            if(endbd->bd[j - BDMAX + 1][k++] == 0)
            {
                endbd->m = j - BDMAX + 1;
                endbd->n = k - 1;
            }
        }     
        
        while((c = fgetc(fp)) == ' ');
        i = 0;
        buf[i++] = c;                
        while((c = fgetc(fp)) != ' ' && c != '\n')
            buf[i++] = c;
        buf[i] = '\0'; 
        if(j < BDMAX)
        {   
            startbd->bd[j][k] = atoi(buf);
            if(startbd->bd[j][k++] == 0)
            {
                startbd->m = j;
                startbd->n = k - 1;
            }                
        }
        else
        {
            endbd->bd[j - BDMAX + 1][k] = atoi(buf);
            if(endbd->bd[j - BDMAX + 1][k++] == 0)
            {
                endbd->m = j - BDMAX + 1;
                endbd->n = k - 1;
            }
        }     
        
        while((c = fgetc(fp)) == ' ');
        i = 0;
        buf[i++] = c;                
        while((c = fgetc(fp)) != ' ' && c != '\n')
            buf[i++] = c;
        buf[i] = '\0'; 
        if(j < BDMAX)
        {   
            startbd->bd[j][k] = atoi(buf);
            if(startbd->bd[j][k++] == 0)
            {
                startbd->m = j;
                startbd->n = k - 1;
            }                
        }
        else
        {
            endbd->bd[j - BDMAX + 1][k] = atoi(buf);
            if(endbd->bd[j - BDMAX + 1][k++] == 0)
            {
                endbd->m = j - BDMAX + 1;
                endbd->n = k - 1;
            }
        }     
        
        while((c = fgetc(fp)) == ' ');
        i = 0;
        buf[i++] = c;                
        while((c = fgetc(fp)) != ' ' && c != '\n')
            buf[i++] = c;
        buf[i] = '\0'; 
        if(j < BDMAX)
        {   
            startbd->bd[j][k] = atoi(buf);
            if(startbd->bd[j][k++] == 0)
            {
                startbd->m = j;
                startbd->n = k - 1;
            }                
        }
        else
        {
            endbd->bd[j - BDMAX + 1][k] = atoi(buf);
            if(endbd->bd[j - BDMAX + 1][k++] == 0)
            {
                endbd->m = j - BDMAX + 1;
                endbd->n = k - 1;
            }
        }         
                    
        j++;            
    }    
}