C언어 퍼즐 게임 (puzzle game in C), 퍼즐 맞추기 알고리즘

퍼즐문제

N X N의 숫자판에 1 ~ N²-1까지의 숫자와 빈칸 하나가 주어진다. 숫자를 인접한 빈칸으로 옮기는 작업을 반복함으로 써 목표 숫자판을 만드는 최소한의 이동 횟수를 찾고자 한다.

[ Fig. 1 ] 시작노드(좌)와 목표노드(우)

[ Fig. 2 ] 처리 과정

 

제한 사항

- 테스트 케이스 T의 범위, 3 <= T <= 10

- 숫자판의 크기 N X N에서 N의 범위, 3 <= N <= 10

- 각 수행 시간은 10msec를 넘지 않도록 한다.

입력과 출력

- 입력은 맨 처음은 테스트 횟수(TC), 그 다음 숫자판의 크기 N 을 입력받는다.

- 목표 노드의 숫자 배열들을 입력받는다.

- 게임판의 세부적인 숫자 배열들을 입력받는다.

( 첨부한 input.txt 참고 )

input.txt

입력 예	출력 예
2 3 1 2 3 8 0 4 7 6 5 2 8 3 1 6 4 7 0 5 3 1 2 3 8 0 4 7 6 5 1 2 3 8 0 5 7 4 6 .....	test #1, ? msec. 5  test #2, ? msec. 4

 

실행 결과

 

 

 

세부 내용

A* 알고리즘을 이용하여 문제 해결 

 

소스 코드

 

#include <stdio.h> #include <malloc.h> #include <time.h> #define NMAX        10 #define SPACE       0 #define MV          0 #define FX          1 #define FIND_DEST   1 #define PRE         2 #define TOP         1 #define BOTTOM      2 #define LEFT        3 #define RIGHT       4 typedef struct queue{     int **p;     int f; // the value of f(x)     struct queue *next; }QUEUE; QUEUE *Q; int d[NMAX+1][NMAX]; int astar( int **, int); void enqueue( int **, int, int); int** dequeue( void); void release( int **, int); int q_empty( void); void swap( int **, int, int, int, int); int calc_heuristic( int**, int); void release_queue( int); int main( void) {     time_t time_s, time_e;     int **m = NULL;     int processtime;     int T, TC;     int N, i, j, result;     // get the datas about the tests from "input.txt" file.     freopen("input.txt", "r", stdin);     scanf("%d", &TC);     for( T = 0 ; T < TC ; T ++)     {         // check the time when your algorithm begins.         time_s = clock();         scanf("%d", &N);         // create the array for the main array         m   = (int**)malloc(sizeof(int*) * (N+1));         for( i = 0 ; i <= N ; i ++)         {             *(m + i)    = (int*)malloc(sizeof(int) * N);         }         // input the integers on the goal from the text file.         for( i = 0 ; i < N ; i ++)         {             for( j = 0 ; j < N ; j ++)             {                 scanf("%d", &d[i][j]);             }         }         // input the integers on the init from the text file.         for( i = 0 ; i < N ; i ++)         {             for( j = 0 ; j < N ; j ++)             {                 scanf("%d", &m[i][j]);             }         }         result  = astar( m, N);         // check the time when process ends.         time_e = clock();         // calculate the time that your process.         processtime = (int)(time_e - time_s);         printf("test #%d, %d msec.\n", T+1, processtime);         printf("%d\n", result);         release(m, N);     } } /*     calc_heruistic( int **, int **, int)         after comparing two array, calculate the value of heuristic. */ int calc_heuristic( int **a, int s) {     int i, j;     int cnt = 0;     for( i = 0 ; i < s ; i ++)     {         for( j = 0 ; j < s ; j ++)         {             if( a[i][j] == d[i][j])             {                 cnt ++;             }         }     }     cnt = (s * s) - cnt;     return cnt; } /*     swap( int **, int, int, int, int)     exchange the element */ void swap( int **p, int x, int y, int nx, int ny) {     int temp;     temp        = p[y][x];     p[y][x]     = p[ny][nx];     p[ny][nx]   = temp; } /*     release( int **)     release the memory that holding the array of puzzle. */ void release( int **p, int s) {     int i;     for( i = 0 ; i <= s ; i ++)     {         free(*(p+i));     }     free(p); } /*     release_queue( int)     release the memory on the arrays that holding nodes of queue     and each node. */ void release_queue( int size) {     QUEUE *temp;     while( Q->next != NULL)     {         release( Q->p, size);         temp    = Q;         Q   = Q->next;         free(temp);     } } /*     astar( int)     this function is the main of the algorithm on A-star. */ int astar( int **p, int size) {     int sx  = 0, sy = 0;     int i, j, result;     p[size][MV] = 0;     result  = 0;     enqueue( p, 0, size);         while( !q_empty())     {         p = dequeue();         if( p[size][FX] == 0)         {             result  = p[size][MV];             break;         }         // find the space element(0)         for( i = 0 ; i < size ; i ++)         {             for( j = 0 ; j < size ; j ++)             {                 if( p[i][j] == SPACE)                 {                     sx  = j;                     sy  = i;                     i   = size;                     break;                 }             }         }         p[size][MV] ++; // increase the number of moving.         //find the route that can move.         if( sy - 1 >= 0 && p[size][PRE] != BOTTOM) // up         {             swap( p, sx, sy, sx, sy-1);             enqueue( p, TOP, size);             swap( p, sx, sy, sx, sy-1);         }                 if( sy + 1 < size && p[size][PRE] != TOP) // down         {             swap( p, sx, sy, sx, sy+1);             enqueue( p, BOTTOM, size);             swap( p, sx, sy, sx, sy+1);         }         if( sx + 1 < size && p[size][PRE] != LEFT) // right         {             swap( p, sx+1, sy, sx, sy);             enqueue( p, RIGHT, size);             swap( p, sx+1, sy, sx, sy);         }         if( sx - 1 >= 0 && p[size][PRE] != RIGHT) // left         {             swap( p, sx-1, sy, sx, sy);             enqueue( p, LEFT, size);             swap( p, sx-1, sy, sx, sy);         }         // release the memory on the array.         release( p, size);     }     // release the memory that holding all queues and all arrays.     release_queue( size);     // the queue is empty.     Q   = NULL;     // release the memory on the last array.     release( p, size);     return result; } /*     q_empty( void)     examine whether the queue is empty */ int q_empty( void) {     return Q == NULL; } /*     dequeue( void)     get back the puzzle from the queue */ int** dequeue( void) {     QUEUE *temp = Q;     int **p     = NULL;     int min, index, j, t;     int i   = 0;     // set the starting point     min     = temp->f;     index   = 0;     // find the minimum value of heuristic     while( temp->next != NULL)     {         if( min > temp->f)         {             min = temp->f;             index   = i;         }         i++;         temp    = temp->next;     }         temp    = Q;     for( j = 0  ;j < index ; j ++)     {         temp    = temp->next;     }     // exchange minimum value into first value in the queue     p       = temp->p;     temp->p = Q->p;     Q->p    = p;     t       = temp->f;     temp->f = Q->f;     Q->f    = t;     temp    = Q;     Q   = Q->next;     free(temp);     return p; } /*     enqueue( int **, int)     this is data structure to store the puzzles. */ void enqueue( int **p, int pre, int size) {     QUEUE *temp = Q;     QUEUE *newq = (QUEUE*)malloc(sizeof(QUEUE));     int **newm  = (int**)malloc(sizeof(int*) * (size+1));     int i, j;     newq->next  = NULL;     newq->p     = NULL;     // allocate the memory to pointer variable.     for( i = 0 ; i <= size ; i ++)     {         *(newm+i)   = (int*)malloc(sizeof(int) * size);     }         // new node points the new array.     newq->p     = newm;     // copy the intergers to the new array.     for( i = 0 ; i < size ; i ++)     {         for( j = 0 ; j < size ; j ++)         {             newm[i][j]  = p[i][j];         }     }     // set the moving point on the array     newm[size][MV]  = p[size][MV];     // set the previous point.     newm[size][PRE] = pre;     // calculate the value of heuristic     newm[size][FX]  = calc_heuristic( newm, size);     newq->f = newm[size][MV] + newm[size][FX];     if( temp == NULL)     {         Q   = newq;         return;     }     // search the last node for the queue.     while( temp->next != NULL)     {         temp = temp->next;     }     temp->next  = newq; }