fork(1) download
copy 
  1. // original: http://w...content-available-to-author-only...s.jp/m_hiroi/puzzle/eight.html
  2. /*
  3.  * eigth1.c : 幅優先探索（双方向）
  4.  *
  5.  */
  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>
  9. #include <time.h>
  10.  
  11. #define TRUE  1
  12. #define FALSE 0
  13. #define FORWARD  1
  14. #define BACKWARD 2
  15. #define SIZE  9
  16. #define NIL   (-1)
  17.  
  18. /* 状態数 (9! / 2) */
  19. #define MAX_STATE 181440
  20.  
  21. /* 隣接リスト */
  22. const char adjacent[SIZE][5] = {
  23.   1, 3,-1,-1,-1,
  24.   0, 4, 2,-1,-1,
  25.   1, 5,-1,-1,-1,
  26.   0, 4, 6,-1,-1,
  27.   1, 3, 5, 7,-1,
  28.   2, 4, 8,-1,-1,
  29.   3, 7,-1,-1,-1,
  30.   4, 6, 8,-1,-1,
  31.   5, 7,-1,-1,-1,
  32. };
  33.  
  34. /* キュー */
  35. char state[MAX_STATE + 1][SIZE];      /* +1 はワーク領域 */
  36. char space_position[MAX_STATE];
  37. int  prev_state[MAX_STATE];
  38. int  number_table[MAX_STATE];
  39.  
  40. /* 同一局面チェックテーブル */
  41. char check_table[MAX_STATE * 2];
  42.  
  43. /* 初期状態 */
  44. char init_state[SIZE] = {
  45.   8, 6, 7, 2, 5, 4, 3, 0, 1
  46. };
  47.  
  48. /* 終了状態 */
  49. char final_state[SIZE] = {
  50.   1, 2, 3, 4, 5, 6, 7, 8, 0
  51. };
  52.  
  53. char dir[SIZE][SIZE] = {
  54.   /* 1 */ { '?', 'l', '?', 'u', '?', '?', '?', '?', '?' },
  55.   /* 2 */ { 'r', '?', 'l', '?', 'u', '?', '?', '?', '?' },
  56.   /* 3 */ { '?', 'r', '?', '?', '?', 'u', '?', '?', '?' },
  57.   /* 4 */ { 'd', '?', '?', '?', 'l', '?', 'u', '?', '?' },
  58.   /* 5 */ { '?', 'd', '?', 'r', '?', 'l', '?', 'u', '?' },
  59.   /* 6 */ { '?', '?', 'd', 'r', 'r', '?', '?', '?', 'u' },
  60.   /* 7 */ { '?', '?', '?', 'd', '?', '?', '?', 'l', '?' },
  61.   /* 8 */ { '?', '?', '?', '?', 'd', '?', 'r', '?', 'l' },
  62.   /* 9 */ { '?', '?', '?', '?', '?', 'd', '?', 'r', '?' },
  63. };
  64.  
  65. /***** 解を表示  *****/
  66. void print_state( int n )
  67. {
  68.   static int last_zero;
  69.   int i;
  70.  
  71. #if 1
  72.   for( i = 0; i < SIZE; i++ ){
  73.      if (state[n][i] == 0) break;
  74.   }
  75.   if (n > 0) putchar(dir[last_zero][i]);
  76.   last_zero = i;
  77. #endif
  78. #if 0
  79.   printf("\n");
  80.   for( i = 0; i < SIZE; i++ ){
  81.     if( i == 3 || i == 6 ) printf("\n");
  82.     printf("%d ", state[n][i] );
  83.   }
  84.   printf("\n\n");
  85. #endif
  86. }
  87.  
  88. void print_answer_forward( int n )
  89. {
  90.   if( n > 1 ) print_answer_forward( prev_state[n] );
  91.   print_state( n );
  92. }
  93.  
  94. void print_answer_backward( int n )
  95. {
  96.   do {
  97.     n = prev_state[n];
  98.     print_state( n );
  99.   } while( prev_state[n] != -1 );
  100. }
  101.  
  102. void print_answer( int pos1, int num1, int num2 )
  103. {
  104.   /* num2 の位置を見つける */
  105.   int pos2 = pos1 - 1;
  106.   while( num2 != number_table[pos2] ) pos2--;
  107.   if( check_table[num1] == FORWARD ){
  108.     print_answer_forward( pos1 );
  109.     print_answer_backward( pos2 );
  110.   } else {
  111.     print_answer_forward( pos2 );
  112.     print_answer_backward( pos1 );
  113.   }
  114.   putchar('\n');
  115. }
  116.  
  117. /* 番号に変換 */
  118. int change_number( char *board )
  119. {
  120.   char work[SIZE];
  121.   static int fact_table[SIZE] = {
  122.     40320, 5040, 720, 120, 24, 6, 2, 1, 0,
  123.   };
  124.   int j, k, value = 0;
  125.   memcpy( work, board, SIZE );
  126.   for( j = 0; j < SIZE - 1; j++ ){
  127.     value += fact_table[j] * work[j];
  128.     for( k = j + 1; k < SIZE; k++ ){
  129.       if( work[j] < work[k] ) work[k]--;
  130.     }
  131.   }
  132.   return value;
  133. }
  134.  
  135. /* キューの初期化 */
  136. void init_queue( void )
  137. {
  138.   int num, i;
  139.   /* スタート */
  140.   memcpy( state[0], init_state, SIZE );
  141.   for (i = 0; i < SIZE; i++) {
  142.         if (init_state[i] == 0) space_position[0] = i;
  143.   }
  144.   prev_state[0] = -1;
  145.   num = change_number( init_state );
  146.   number_table[0] = num;
  147.   check_table[ num ] = FORWARD;
  148.   /* ゴール */
  149.   memcpy( state[1], final_state, SIZE );
  150.   space_position[1] = 8;
  151.   prev_state[1] = -1;
  152.   num = change_number( final_state );
  153.   number_table[1] = num;
  154.   check_table[ num ] = BACKWARD;
  155. }
  156.  
  157. /* 探索 */
  158. void search( void )
  159. {
  160.   int front = 0, rear = 2;
  161.   /* 初期化 */
  162.   init_queue();
  163.   while( front < rear ){
  164.     int s = space_position[front];
  165.     int num1 = number_table[front];
  166.     int num2, i, n;
  167.     for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
  168.       /* 状態をコピー */
  169.       memcpy( state[rear], state[front], SIZE );
  170.       /* 移動 */
  171.       state[rear][s] = state[rear][n];
  172.       state[rear][n] = 0;
  173.       space_position[rear] = n;
  174.       prev_state[rear] = front;
  175.       num2 = change_number( state[rear] );
  176.       if( !check_table[num2] ){
  177.         /* 登録 */
  178.         number_table[rear] = num2;
  179.         check_table[num2] = check_table[num1];
  180.         rear++;
  181.       } else if( check_table[num1] != check_table[num2] ){
  182.         /* 解が見つかった */
  183.         print_answer( rear, num1, num2 );
  184.         return;
  185.       }
  186.     }
  187.     front++;
  188.   }
  189. }
  190.  
  191. int main(int argc, char *argv[])
  192. {
  193.   int i;
  194.   if (argc != 2 || strlen(argv[1]) != 9) {
  195.     fprintf(stderr, "Usage: %s 9numbers\n", argv[0]);
  196.     exit(1);
  197.   }
  198.   for (i = 0; i < 9; i++) {
  199.     int n = argv[1][i] - '0';
  200.     if (n < 0 || 8 < n) {
  201.       fprintf(stderr, "invalid number: %c\n", argv[1][i]);
  202.       exit(1);
  203.     }
  204.     init_state[i] = n;
  205.   }
  206.   search();
  207.   return 0;
  208. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/VIyruB
language:
C (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!