Dice Puzzle

問題 ACM/ICPC Asia Regional 2004 Ehime: Problem F

概要

側面に数字（１から６）が書かれたサイコロ２７個を使い、
３×３×３×のキューブを完成させる。
入力としてキューブの上面と前面の状態が与えられるので、これを満たさなければならない。
また、隣り合うサイコロにおいて、接している側面に書かれている数字の和が７でなければならない。
求めるものは、キューブ右面に見える数字の合計。

解説

バックトラックで総当り探索。

サンプルプログラム

001 #include<iostream>
002 #include<set>
003 #include<algorithm>
004 using namespace std;
005 
006 int RT[24][6] = {
007     {1,2,3,4,5,6}, {1,3,5,2,4,6}, {1,5,4,3,2,6}, {1,4,2,5,3,6},
008     {4,2,1,6,5,3}, {4,1,5,2,6,3}, {4,5,6,1,2,3}, {4,6,2,5,1,3},
009     {6,2,4,3,5,1}, {6,4,5,2,3,1}, {6,5,3,4,2,1}, {6,3,2,5,4,1},
010     {3,2,6,1,5,4}, {3,6,5,2,1,4}, {3,5,1,6,2,4}, {3,1,2,5,6,4},
011     {5,1,3,4,6,2}, {5,3,6,1,4,2}, {5,6,4,3,1,2}, {5,4,1,6,3,2},
012     {2,1,4,3,6,5}, {2,4,6,1,3,5}, {2,6,3,4,1,5}, {2,3,1,6,4,5}
013 };
014 
015 int T[3][3], F[3][3], puzzle[27];
016 set<int> solved;
017 
018 int getRight(){
019     int sum = 0;
020     for ( int i = 2; i < 27; i += 3 ) sum += RT[puzzle[i]][2];
021     return sum;
022 }
023 
024 void recursive( int pos ){
025     if ( pos == 27 ){ solved.insert(getRight()); return; }
026     int i = (pos%9)/3;
027     int j = (pos%9)%3;
028     int k = pos/9;
029     
030     for ( int r = 0; r < 24; r++ ){
031         if ( i == 0 && T[3-k-1][j] && T[3-k-1][j] != RT[r][0] ) continue;
032         if ( k == 0 && F[i][j] && F[i][j] != RT[r][1] ) continue;
033         if ( i && RT[r][0] + RT[puzzle[k*9+(i-1)*3+j]][5] != 7 ) continue;
034         if ( k && RT[r][1] + RT[puzzle[(k-1)*9+i*3+j]][4] != 7 ) continue;
035         if ( j && RT[r][3] + RT[puzzle[k*9+i*3+(j-1)]][2] != 7 ) continue;
036         puzzle[pos] = r;
037         recursive( pos+1 );
038     }
039 }
040 
041 void compute(){
042     solved.clear();
043     recursive(0);
044     if ( solved.size() == 0 ) {	cout << 0 << endl; return; }
045     set<int>::iterator p = solved.begin();
046     cout << *p;
047     for ( p++; p != solved.end(); p++ ) cout << " " << *p;
048     cout << endl;
049 }
050 
051 main(){
052     int tcase; cin >> tcase;
053     for ( int t = 0; t < tcase; t++ ){
054         for ( int i = 0; i < 3; i++ ) {
055             for ( int j = 0; j < 3; j++ ) cin >> T[i][j];
056         }
057         for ( int i = 0; i < 3; i++ ) {
058             for ( int j = 0; j < 3; j++ ) cin >> F[i][j];
059         }
060         compute();
061     }
062 }