[Java] Soma Cube

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

[설명]
임의의 블럭들의 모양을 입력으로 받은 다음
그 블럭들을 이용해 3*3*3의 큐브를 만들 수 있는
distinct한 모든 해를 구하는 프로그램.
Soma Cube라고 널리 알려진 문제.

[cube.java]
/************************************************************ http://zzun.net ******************************************************/

import java.io.*;

class Piece                                                                // a class of each piece
{
       public Piece(char s)
       {
               ptn = new int[2][27*24/2];                // patterns will save here
               symbol = s;                                                // symbol of pattern
               count = new int[2];                                                // # of patterns (two groups)
       }

       public void setBase(int base)                        // setting the base pattern
       {
               String temp = "";
               for (int i=0; i<27; i++)
                       if ( ((base >> i) % 2) == 1 )        // determine the piece's shape
                       {
                               temp += (char)i;
                               size++;
                       }
               
               basePtn = new int[size][3];
               for (int i=0; i<size; i++)
               {
                       basePtn[i][0] = temp.charAt(i)%3 - temp.charAt(0)%3;                        // saving the base pattern as if it starts at first cell
                       basePtn[i][2] = temp.charAt(i)/9 - temp.charAt(0)/9;
                       basePtn[i][1] = (temp.charAt(i) - basePtn[i][2]*9) / 3 - (temp.charAt(0) - basePtn[0][2]*9) / 3;
               }
       }

       private void push(int type, int s)                        // add a pattern by type
       {
               ptn[type][count[type]] = s;
               count[type]++;                                                // act like stack
       }

       public void generate(int i)                        // generate i-th pattern
       {
               int[][] next = rotate(i);                // read a rotated pattern
               int[] xyz = new int[3];
               int pushing;

               for (int j=0; j<27; j++)                // through all positions in cube
               {
                       pushing = 0;

                       xyz[0] = j % 3;
                       xyz[2] = j / 9;
                       xyz[1] = (j - xyz[2]*9) / 3;        // calculate coordinates

                       int[] temp = new int[3];
                       int newCoord;

                       big:
                       for (int k=0; k<size; k++)
                       {
                               for (int l=0; l<3; l++)
                               {
                                       newCoord = next[k][l] + xyz[l];                // moving the rotated piece
                                       if (newCoord < 0 || newCoord > 2)                // if rotated piece has illegal cube, then break, try another position
                                       {
                                               pushing = 0;
                                               break big;
                                       }
                                       else
                                                temp[l] = (char)newCoord;
                               }
                               pushing |= (1 << (temp[0] + temp[1]*3 + temp[2]*9));                // save the current rotated pattern
                       }

                       boolean exist = false;                // already exist
                       if (pushing != 0)                        // legal rotating
                       {
                               int type = (pushing>>13)%2;                                        // if a ptn have cube no.13 TYPE 1, if not TYPE 0. every ptn is distinguishable by this rule.
                               for (int k=count[type]-1; k>=0; k--)
                                       if (ptn[type][k] == pushing)                        // check whether the same pattern exists already or not
                                               exist = true;
                               if (!exist)
                                       push(type, pushing);                                                        // if the pattern is unique, push it.
                       }
               }

               return;
       }

       private int[][] rotate(int idx)                                        // return a rotated piece (=pattern) by idx
       {
               int[][] rtn = new int[size][3];

               for (int i=0; i<size; i++)
                       for (int j=0; j<3; j++)
                               rtn[i][Math.abs(rotate[idx][j])-1] = basePtn[i][j] * ((rotate[idx][j] > 0) ? 1 : (-1));        // now rotating

               return rtn;
       }

       public int size = 0;
       public char symbol;
       public int count[];
       public int[][] ptn;                                // possible patterns
       private int[][] basePtn;                // base pattern
       private static int[][] rotate = { {1,2,3}, {1,-2,-3}, {1,3,-2}, {1,-3,2}, {-1,2,-3}, {-1,-2,3}, {-1,3,2}, {-1,-3,-2},
                                                                         {2,1,-3}, {2,-1,3}, {2,3,1}, {2,-3,-1}, {-2,1,3}, {-2,-1,-3}, {-2,3,-1}, {-2,-3,1},
                                                                         {3,1,2}, {3,-1,-2}, {3,2,-1}, {3,-2,1}, {-3,1,-2}, {-3,-1,2}, {-3,2,1}, {-3,-2,-1}
                                                                       };                // the rotating patterns {3,-2,1} means x->z, y->-y, z->x
}

public class cube
{
       public static String inputFileName;
       public static String outputFileName = "cube.out";
       public static Piece[] p;
       public static int[] answer;
       public static int status = 0;
       public static BufferedReader fin;                        // input stream
       public static PrintWriter fout;                                // output stream
       public static boolean typeCheck;

       public static void initialize() throws IOException                        // initialize for a search
       {
               String buffer;
               int pos;
               char sym;
               for (int i=0; i<p.length; i++)
               {
                       buffer = fin.readLine();
                       sym = buffer.charAt(0);                                // check the symbol of the piece
                       p[i] = new Piece(sym);                                // make an object presenting the piece

                       pos = 0;                                                        // initial pattern
                       for (int j=0; j<27; j++)
                               if (buffer.charAt(j+2) == sym)
                                       pos |= (1 << j);
                       p[i].setBase(pos);                                                // set a base pattern

                       if (i==0)
                               p[i].generate(0);                        // if it is the first piece
                       else                                                        // otherwise
                               for (int j=0; j<24; j++)
                                       p[i].generate(j);
               }

               return;
       }

       public static void search(int type, int idx) throws IOException
       {
               int temp;
               
               for (int i=0; i<p[idx].count[type]; i++)
               {
                       temp = p[idx].ptn[type][i];                                                                // get a pattern of current piece

                       if ((status & temp) == 0)
                       {
                               status |= temp;
                               answer[idx] = temp;

                               if (idx == p.length - 1)                                                        // if the pushed piece is the last piece
                                       prodAns();                                                                                // We Find One! Produce the Answer!
                               else
                               {
                                       if (typeCheck)                                                                        // if any above piece has the 13-cube,
                                               search(0, idx+1);                                                        // find next piece in type 0
                                       else                                                                                        // if not
                                       {
                                               typeCheck = true;                                                        // set typeCheck
                                               search(1, idx+1);                                                        // find next piece in type 1
                                               typeCheck = false;                                                        // unset
                                               search(0, idx+1);                                                        // and find remaining in type 0
                                       }
                               }

                               status &= ~temp;                                // unpush the piece
                       }
               }
               
               return;
       }

       private static void prodAns() throws IOException                        // output the answer
       {
               char[] out = new char[27];
               for (int i=0; i<27; i++)
                       for (int j=0; j<p.length; j++)
                               if ( ((answer[j] >> i) % 2) == 1 )
                               {
                                       out[i] = p[j].symbol;
                                       break;
                               }

               fout.println(out);
       }

       public static void main(String[] args) throws IOException
       {
               if (args.length!=1 || args[0] == null)
               {
                       System.out.println("ERROR : please enter the input file name as an argument");
                       System.exit(0);
               }
               else
                       inputFileName = args[0];
               fin = new BufferedReader(new FileReader(inputFileName));
               int number = Integer.parseInt(fin.readLine());                                // # of pieces
               p = new Piece[number];
               answer = new int[number];
               System.out.println("Initializing...");
               initialize();
               fin.close();

               fout = new PrintWriter(new FileOutputStream(outputFileName));
               System.out.println("Searching...");
               typeCheck = true;
               search(1, 0);                                                // find as the first piece in type 1
               typeCheck = false;
               search(0, 0);                                                // in type 2
               
               fout.close();

               System.out.println("Finished!");
               return;
       }
}