[C++] 3-dimension 63-Puzzle

프로그래밍 언어 / 2003년 1학기 / 한상영 교수님

[설명]
2차원에서의 15-puzzle을 3차원으로 확장한 개념.
임의의 퍼즐 배치를 입력으로 받아
Optimal Solution(최소move)을 구함.
Cell을 움직이거나, 움직임의 sequence를 입력받아 움직일 수 있음.

[puzzle.cpp]
#include <iostream.h>
#include <fstream.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#define WIDTH 4

short CELL[WIDTH][WIDTH][WIDTH];
short* CELL_S = &(CELL[0][0][0]);                // the 1-dimension alias of the 3-dimension array CELL
short MD[WIDTH*WIDTH*WIDTH][WIDTH*WIDTH*WIDTH];                        // save All possible MD values.
short ANS[1000] = {0};                                        // the optimal solution of minimum moving sequence
int bound;

bool read_input(char* filename)                        // at first, load input file (ex. from puzzle.in)
{
       ifstream in (filename);
       
       char buf;
       int current_cell = 0;
       int counter = 0;

       while (in.get(buf))
       {
               if (buf>='0' && buf<='9')
               {
                       current_cell = current_cell*10 + (buf - '0');
               }
               else if (buf == '$')
                       current_cell = 64;
               else
               {
                       if (current_cell > 64)
                       {
                               cout << "ERROR : Wrong input file." << endl;
                               return false;
                       }
                       else if (current_cell > 0)
                       {
                               CELL_S[counter] = current_cell;                        // save it in to the array
                               counter++;
                               current_cell = 0;
                       }
               }                                
       }

       in.close();

       int inv_count = 0;                        // Check whether this problem can be solved or not

       for (int i=1; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i-1]>CELL_S[i])
                       inv_count++;
       }

       if (inv_count%2 == 0)
       {
               cout << "Impossible to solve!" << endl;
               return false;
       }

       return true;
}

void set_md()                                // compute Manhattan Distance of all possible pair of cells
{
       int i_x, i_y, i_z, j_x, j_y, j_z;

   for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               i_x = i % WIDTH;
               i_z = i / (WIDTH*WIDTH);
               i_y = (i - i_z*WIDTH*WIDTH) / WIDTH;
               for (int j=0; j<WIDTH*WIDTH*WIDTH; j++)
               {
                       j_x = j % WIDTH;
                       j_z = j / (WIDTH*WIDTH);
                       j_y = (j - j_z*WIDTH*WIDTH) / WIDTH;
                       
                       MD[i][j] = abs(i_x - j_x) + abs(i_y - j_y) + abs(i_z - j_z);                // |x1-x2| + |y1-y2| + |z1-z2|
               }
       }

       return;
}

int cur_MD()                                // return current sum of MDs
{
       int md = 0;

       for (int i=0; i<WIDTH*WIDTH*WIDTH; i++)
       {
               if (CELL_S[i] == 64)
                       continue;
               md += MD[i][CELL_S[i]-1];
       }

       return md;
}

bool move_to(int dir)                // move to dir
{
       int x, y, z, idx;                                // find the empty cell
       for (idx=0; idx<WIDTH*WIDTH*WIDTH; idx++)
               if (CELL_S[idx]==64) break;
       x = idx % WIDTH;
       z = idx / (WIDTH*WIDTH);
       y = (idx - z*WIDTH*WIDTH) / WIDTH;

       switch (dir)
       {
       case 1 :                                                // move up
               if (y != 0)
               {
                       CELL[z][y][x] = CELL[z][y-1][x];
                       CELL[z][y-1][x] = 64;
               }
               else
                       return false;                        // impossible to move
               break;

       case 2 :                                                // move down
               if (y != 3)
               {
                       CELL[z][y][x] = CELL[z][y+1][x];
                       CELL[z][y+1][x] = 64;
               }
               else                        
                       return false;
               break;
       
       case 3 :                                                // move left
               if (x != 0)
               {
                       CELL[z][y][x] = CELL[z][y][x-1];
                       CELL[z][y][x-1] = 64;
               }
               else
           return false;
               break;
       
       case 4 :                                                // move right
               if (x != 3)
               {
                       CELL[z][y][x] = CELL[z][y][x+1];
                       CELL[z][y][x+1] = 64;                        
               }
               else
           return false;
               break;

       case 5 :                                                // move forward
               if (z != 0)
               {
                       CELL[z][y][x] = CELL[z-1][y][x];
                       CELL[z-1][y][x] = 64;
               }
               else
           return false;        
               break;

       case 6 :                                                // move backward
               if (z != 3)
               {
                       CELL[z][y][x] = CELL[z+1][y][x];
                       CELL[z+1][y][x] = 64;                        
               }
               else
                       return false;
               break;
       
       default :
               return false;
       }

       return true;                                        // success to move
}

bool IDA(int depth, short prev)                // searching algorithm
{
       depth++;
       short opp;

       for (int i=1; i<=6; i++)
       {
               opp = (i%2 == 0) ? i-1 : i+1;                // the opposite side of moving direction.
               if (prev != opp && move_to(i))
               {
                       if (cur_MD()+depth<=bound)
                       {
                               if (depth == bound || IDA(depth, i))                // recursive call
                               {
                                       move_to(opp);                        // move back
                                       ANS[depth] = i;                        // save the answer
                                       return true;
                               }
                       }
                       move_to(opp);                        // move back
               }
       }

       return false;
}

void print_cur()                                        // print out the current status
{
       for (int i=0; i<WIDTH; i++)
       {
               for (int j=0; j<WIDTH; j++)
               {
                       for (int k=0; k<WIDTH; k++)
                       {
                               if (CELL[j][i][k] == 64)
                                       printf("  $");
                               else
                   printf("%3d", CELL[j][i][k]);
                       }
                       printf(" | ");
               }
               printf("\n");
       }
       return;
}

void search()                                                // find the optimal solution
{
       bound = cur_MD();                                // lower bound of moves in optimal solution

       if (bound != 0)
       {
               cout << "Lower Bound = " << bound << endl << "Now Searching..." << endl;

               cout << "Trying " << bound << endl;

       while(!IDA(0, -1))                        // searching start
               {
                       bound += 2;                                // if the solution wasn't found, try with bound+2 as the lower bound
                       cout << "Trying " << bound << endl;
               }

               cout << "Success!" << endl;
       }

       return;
}

int main(int argc, char* argv[])
{
       char *input_file, *output_file;//, *cmd;

       /*if (argc != 2)                                                // check the arguments
       {
               printf("ERROR : Please enter the input file name as an argument.\n");
               return 1;
       }*/

       input_file = "puzzle.in";//argv[1];

       if (!read_input(input_file))                // read the input file and save it into the array
               return 1;

       char cmd[20];
       //cmd = new char[20];

       set_md();                                                        // set the MD values

       print_cur();

       printf("$>");
       cin.getline(cmd, sizeof(cmd));                                // ready to accept a command

       while (strcmp("quit", cmd))
       {
               if (strlen(cmd)==1 && cmd[0] >= '1' && cmd[0] <= '6')                        // moving command
               {
                       if(!move_to((int)(cmd[0] - '0')))
                               cout << "Illegal Move!" << endl;                        // fail to move
                       else
                               print_cur();                                                                // success to move
               }
               else if (!strncmp("in ", cmd, 3))                        // read a sequence from a file
               {
                       char buf;
                       input_file = cmd + 3;
                       ifstream in(input_file);
                       cout << "Moving... : ";
                       while(in.get(buf))
                       {
                               if (buf >= '1' && buf <= '6')
                               {
                                       cout << buf;
                                       if(!move_to((int)(buf - '0')))
                                       {
                                               cout << " Illegal Move!" << endl;
                                               goto exit;
                                       }
                               }
                       }

                       exit :
                       in.close();
                       cout << endl;
                       print_cur();
               }
               else if (!strncmp("out ", cmd, 4))                        // solve the puzzle, and put out the optimal sequence of moves
               {
                       output_file = cmd + 4;
           search();
                       cout << "Optimal solution : " << bound << " moves." << endl;
                       ofstream out(output_file);
                       for (int i=1; ANS[i] != 0; i++)                        // ANS re-initialization for next solving
                       {
                               out << ANS[i];
                               ANS[i] = 0;
                               if (i%10 == 0)
                                       out << endl;
                       }
                       out.close();

                       print_cur();
               }
               else
                       printf("Wrong Command.\n");

               printf("$>");
               cin.getline(cmd, sizeof(cmd));
       }

       return 0;
}