digit8_dfs.c

8数码问题深度遍历解法

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <sys/time.h>

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

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

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

struct queuestate
{
    int head,tail;
};

struct queue q;
struct board startbd,endbd;
int count;
int minpath;
int maxpath;

char path[4][20] = {                    
                    "-> Left",
                    "-> Right",
                    "-> Up",
                    "-> Down",
                   };       
    
void readText(char *text,struct board *startbd,struct board *endbd);    
void init_queue(struct queue *q);
void en_queue(struct queue *q,struct board *a);
int rule1(struct queue *q,struct board *n);
int rule2(struct queue *q,struct board *n);
int rule3(struct queue *q,struct board *n);
int rule4(struct queue *q,struct board *n);
int bound(struct queue *q,struct board *n);
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);
void display(struct queue *q);
void backup_state(struct queuestate *a,struct queue *b);
void restore_state(struct queue *a,struct queuestate *b);
void backtrack(struct queue *q,struct board *n);
int random_num();


int main(int argc, char *argv[])
{   
    readText("digit8.txt",&startbd,&endbd);    
    
    count = 0;
    minpath = INFINITY;
    maxpath = 0;
    startbd.method = -1;
    startbd.direction = -1;
    
    init_queue(&q);
    en_queue(&q,&startbd);
    
    backtrack(&q,&startbd);
    printf("%d\n",random_num());
    
    printf("count = %d,minpath = %d,maxpath = %d\n",count,minpath,maxpath);
    return EXIT_SUCCESS;
}


int random_num()
{
    struct timeval tv;
    struct timezone tz;
    
    gettimeofday(&tv,&tz);
    
    return tv.tv_usec % 6;
}
void init_queue(struct queue *q)
{
    q->head = 1;
    q->tail = 1;
}

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

int rule1(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.direction = LEFT;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd);  
                
                return TRUE;
            }
        }
    }
    
    return FALSE;
}

int rule2(struct queue *q,struct board *a)
{
    struct board nd;
    
    if(a->n <= 2)
    {
        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.direction = RIGHT;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
                
                return TRUE;
            }
        }
    }
    
    return FALSE;
}

int rule3(struct queue *q,struct board *a)
{
    struct board 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.direction = UP;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
                
                return TRUE;
            }
        }
    }
    
    return FALSE;
}

int rule4(struct queue *q,struct board *a)
{
    struct board nd;  
     
    if(a->m <= 2)
    {
        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.direction = DOWN;
            
            if(!bound(q,&nd))
            { 
                en_queue(q,&nd); 
                
                return TRUE;
            }
        }
    }
    
    return FALSE;
}

int bound(struct queue *q,struct board *n)
{
    int i;
    
    for(i = q->head; i < q->tail; 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->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->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_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("%d ",state->bd[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}


void display(struct queue *q)
{    
    int i;
    
    for(i = q->head; i < q->tail; i++)
    {
        display_board(&q->nqueue[i]);
    }
    printf("\n");
}

void backtrack(struct queue *q,struct board *n)
{
    struct queuestate state;    
    
    if(is_equal(n,&endbd))
    {
        if(q->tail - q->head < minpath)
        {
            minpath = q->tail - q->head;
        }
        
        if(maxpath < q->tail - q->head)
        {
            maxpath = q->tail - q->head;
        }
        printf("The Results:\n");
        display(q);
        count++;
    }
    else
    {
        backup_state(&state,q);
        if(rule3(q,n))
        {            
            printf("%d\n",q->tail - 1);
//             display(q);
            backtrack(q,&q->nqueue[q->tail - 1]);
            restore_state(q,&state);
            printf("%d\n",q->tail - 1);
        }

        if(rule2(q,n))
        {            
            printf("%d\n",q->tail - 1);
//             display(q);
            backtrack(q,&q->nqueue[q->tail - 1]);
            restore_state(q,&state);
            printf("%d\n",q->tail - 1);
        }
        
        if(rule4(q,n))
        {            
            printf("%d\n",q->tail - 1);
//             display(q);
            backtrack(q,&q->nqueue[q->tail - 1]);
            restore_state(q,&state);
            printf("%d\n",q->tail - 1);
        }
        
        if(rule1(q,n))
        {            
            printf("%d\n",q->tail - 1);
//             display(q);
            backtrack(q,&q->nqueue[q->tail - 1]);
            restore_state(q,&state);
            printf("%d\n",q->tail - 1);
        } 
    }
}

void backup_state(struct queuestate *a,struct queue *b)
{
    a->head = b->head;
    a->tail = b->tail;
}

void restore_state(struct queue *a,struct queuestate *b)
{
    a->head = b->head;
    a->tail = b->tail;
}


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;
            }
        }     
                    
        j++;            
    }    
}