/**
 * Program Name: Unique.java, for 數獨
 * Author: Shiuh-Sheng Yu at
 *         Department of Infromation Management
 *         National ChiNan University
 * Since: 2005/09/12
 */
import java.util.Vector;
public class Unique {
    // 以下是各位置的坐標
    //  0  1  2  3  4  5  6  7  8
    //  9 10 11 12 13 14 15 16 17
    // 18 19 20 21 22 23 24 25 26
    // 27 28 29 30 31 32 33 34 35
    // 36 37 38 39 40 41 42 43 44
    // 45 46 47 48 49 50 51 52 53
    // 54 55 56 57 58 59 60 61 62
    // 63 64 65 66 67 68 69 70 71
    // 72 73 74 75 76 77 78 79 80
    public static int near[][] = { // 依遊戲規則, 每個位置都有20個不得重複的位置
        {  1,  2,  3,  4,  5,  6,  7,  8,  9, 18, 27, 36, 45, 54, 63, 72, 10, 11, 19, 20}, // 0
        {  0,  2,  3,  4,  5,  6,  7,  8, 10, 19, 28, 37, 46, 55, 64, 73,  9, 11, 18, 20}, // 1 
        {  0,  1,  3,  4,  5,  6,  7,  8, 11, 20, 29, 38, 47, 56, 65, 74,  9, 10, 18, 19}, // 2
        {  0,  1,  2,  4,  5,  6,  7,  8, 12, 21, 30, 39, 48, 57, 66, 75, 13, 14, 22, 23}, // 3
        {  0,  1,  2,  3,  5,  6,  7,  8, 13, 22, 31, 40, 49, 58, 67, 76, 12, 14, 21, 23}, // 4
        {  0,  1,  2,  3,  4,  6,  7,  8, 14, 23, 32, 41, 50, 59, 68, 77, 12, 13, 21, 22}, // 5
        {  0,  1,  2,  3,  4,  5,  7,  8, 15, 24, 33, 42, 51, 60, 69, 78, 16, 17, 25, 26}, // 6
        {  0,  1,  2,  3,  4,  5,  6,  8, 16, 25, 34, 43, 52, 61, 70, 79, 15, 17, 24, 26}, // 7
        {  0,  1,  2,  3,  4,  5,  6,  7, 17, 26, 35, 44, 53, 62, 71, 80, 15, 16, 24, 25}, // 8
        { 10, 11, 12, 13, 14, 15, 16, 17,  0, 18, 27, 36, 45, 54, 63, 72,  1,  2, 19, 20}, // 9
        {  9, 11, 12, 13, 14, 15, 16, 17,  1, 19, 28, 37, 46, 55, 64, 73,  0,  2, 18, 20}, // 10 
        {  9, 10, 12, 13, 14, 15, 16, 17,  2, 20, 29, 38, 47, 56, 65, 74,  0,  1, 18, 19}, // 11
        {  9, 10, 11, 13, 14, 15, 16, 17,  3, 21, 30, 39, 48, 57, 66, 75,  4,  5, 22, 23}, // 12
        {  9, 10, 11, 12, 14, 15, 16, 17,  4, 22, 31, 40, 49, 58, 67, 76,  3,  5, 21, 23}, // 13
        {  9, 10, 11, 12, 13, 15, 16, 17,  5, 23, 32, 41, 50, 59, 68, 77,  3,  4, 21, 22}, // 14
        {  9, 10, 11, 12, 13, 14, 16, 17,  6, 24, 33, 42, 51, 60, 69, 78,  7,  8, 25, 26}, // 15
        {  9, 10, 11, 12, 13, 14, 15, 17,  7, 25, 34, 43, 52, 61, 70, 79,  6,  8, 24, 26}, // 16
        {  9, 10, 11, 12, 13, 14, 15, 16,  8, 26, 35, 44, 53, 62, 71, 80,  6,  7, 24, 25}, // 17
        { 19, 20, 21, 22, 23, 24, 25, 26,  0 , 9, 27, 36, 45, 54, 63, 72,  1,  2, 10, 11}, // 18
        { 18, 20, 21, 22, 23, 24, 25, 26,  1, 10, 28, 37, 46, 55, 64, 73,  0,  2,  9, 11}, // 19 
        { 18, 19, 21, 22, 23, 24, 25, 26,  2, 11, 29, 38, 47, 56, 65, 74,  0,  1,  9, 10}, // 20
        { 18, 19, 20, 22, 23, 24, 25, 26,  3, 12, 30, 39, 48, 57, 66, 75,  4,  5, 13, 14}, // 21
        { 18, 19, 20, 21, 23, 24, 25, 26,  4, 13, 31, 40, 49, 58, 67, 76,  3,  5, 12, 14}, // 22
        { 18, 19, 20, 21, 23, 24, 25, 26,  5, 14, 32, 41, 50, 59, 68, 77,  3,  4, 12, 13}, // 23
        { 18, 19, 20, 21, 22, 23, 25, 26,  6, 15, 33, 42, 51, 60, 69, 78,  7,  8, 16, 17}, // 24
        { 18, 19, 20, 21, 22, 23, 24, 26,  7, 16, 34, 43, 52, 61, 70, 79,  6,  8, 15, 17}, // 25
        { 18, 19, 20, 21, 22, 23, 24, 25,  8, 17, 35, 44, 53, 62, 71, 80,  6,  7, 15, 16}, // 26
        { 28, 29, 30, 31, 32, 33, 34, 35,  0,  9, 18, 36, 45, 54, 63, 72, 37, 38, 46, 47}, // 27
        { 27, 29, 30, 31, 32, 33, 34, 35,  1, 10, 19, 37, 46, 55, 64, 73, 36, 38, 45, 47}, // 28 
        { 27, 28, 30, 31, 32, 33, 34, 35,  2, 11, 20, 38, 47, 56, 65, 74, 36, 37, 45, 46}, // 29
        { 27, 28, 29, 31, 32, 33, 34, 35,  3, 12, 21, 39, 48, 57, 66, 75, 40, 41, 49, 50}, // 30
        { 27, 28, 29, 30, 32, 33, 34, 35,  4, 13, 22, 40, 49, 58, 67, 76, 39, 41, 48, 50}, // 31
        { 27, 28, 29, 30, 31, 33, 34, 35,  5, 14, 23, 41, 50, 59, 68, 77, 39, 40, 48, 49}, // 32
        { 27, 28, 29, 30, 31, 32, 34, 35,  6, 15, 24, 42, 51, 60, 69, 78, 43, 44, 52, 53}, // 33
        { 27, 28, 29, 30, 31, 32, 33, 35,  7, 16, 25, 43, 52, 61, 70, 79, 42, 44, 51, 53}, // 34
        { 27, 28, 29, 30, 31, 32, 33, 34,  8, 17, 26, 44, 53, 62, 71, 80, 42, 43, 51, 52}, // 35
        { 37, 38, 39, 40, 41, 42, 43, 44,  0,  9, 18, 27, 45, 54, 63, 72, 28, 29, 46, 47}, // 36
        { 36, 38, 39, 40, 41, 42, 43, 44,  1, 10, 19, 28, 46, 55, 64, 73, 27, 27, 45, 47}, // 37
        { 36, 37, 39, 40, 41, 42, 43, 44,  2, 11, 20, 29, 47, 56, 65, 74, 27, 28, 45, 46}, // 38
        { 36, 37, 38, 40, 41, 42, 43, 44,  3, 12, 21, 30, 48, 57, 66, 75, 31, 32, 49, 50}, // 39
        { 36, 37, 38, 39, 41, 42, 43, 44,  4, 13, 22, 31, 49, 58, 67, 76, 30, 32, 48, 50}, // 40
        { 36, 37, 38, 39, 40, 42, 43, 44,  5, 14, 23, 32, 50, 59, 68, 77, 30, 31, 48, 49}, // 41
        { 36, 37, 38, 39, 40, 41, 43, 44,  6, 15, 24, 33, 51, 60, 69, 78, 34, 35, 52, 53}, // 42
        { 36, 37, 38, 39, 40, 41, 42, 44,  7, 16, 25, 34, 52, 61, 70, 79, 33, 35, 51, 53}, // 43
        { 36, 37, 38, 39, 40, 41, 42, 43,  8, 17, 26, 35, 53, 62, 71, 80, 33, 34, 51, 52}, // 44
        { 46, 47, 48, 49, 50, 51, 52, 53,  0,  9, 18, 27, 36, 54, 63, 72, 28, 29, 37, 38}, // 45
        { 45, 47, 48, 49, 50, 51, 52, 53,  1, 10, 19, 28, 37, 55, 64, 73, 27, 29, 36, 38}, // 46
        { 45, 46, 48, 49, 50, 51, 52, 53,  2, 11, 20, 29, 38, 56, 65, 74, 27, 28, 36, 37}, // 47
        { 45, 46, 47, 49, 50, 51, 52, 53,  3, 12, 21, 30, 39, 57, 66, 75, 31, 32, 40, 41}, // 48
        { 45, 46, 47, 48, 50, 51, 52, 53,  4, 13, 22, 31, 40, 58, 67, 76, 30, 32, 39, 41}, // 49
        { 45, 46, 47, 48, 49, 51, 52, 53,  5, 14, 23, 32, 41, 59, 68, 77, 30, 31, 39, 40}, // 50
        { 45, 46, 47, 48, 49, 50, 52, 53,  6, 15, 24, 33, 42, 60, 69, 78, 34, 35, 43, 44}, // 51
        { 45, 46, 47, 48, 49, 50, 51, 53,  7, 16, 25, 34, 43, 61, 70, 79, 33, 35, 42, 44}, // 52
        { 45, 46, 47, 48, 49, 50, 51, 52,  8, 17, 26, 35, 44, 62, 71, 80, 33, 34, 42, 43}, // 53
        { 55, 56, 57, 58, 59, 60, 61, 62,  0,  9, 18, 27, 36, 45, 63, 72, 64, 65, 73, 74}, // 54
        { 54, 56, 57, 58, 59, 60, 61, 62,  1, 10, 19, 28, 37, 46, 64, 73, 63, 65, 72, 74}, // 55
        { 54, 55, 57, 58, 59, 60, 61, 62,  2, 11, 20, 29, 38, 47, 65, 74, 63, 64, 72, 73}, // 56
        { 54, 55, 56, 58, 59, 60, 61, 62,  3, 12, 21, 30, 39, 48, 66, 75, 67, 68, 76, 77}, // 57
        { 54, 55, 56, 57, 59, 60, 61, 62,  4, 13, 22, 31, 40, 49, 67, 76, 66, 68, 75, 77}, // 58
        { 54, 55, 56, 57, 58, 60, 61, 62,  5, 14, 23, 32, 41, 50, 68, 77, 66, 67, 75, 76}, // 59
        { 54, 55, 56, 57, 58, 59, 61, 62,  6, 15, 24, 33, 42, 51, 69, 78, 70, 71, 79, 80}, // 60
        { 54, 55, 56, 57, 58, 59, 60, 62,  7, 16, 25, 34, 43, 52, 70, 79, 69, 71, 78, 80}, // 61
        { 54, 55, 56, 57, 58, 59, 60, 61,  8, 17, 26, 35, 44, 53, 71, 80, 69, 70, 78, 79}, // 62
        { 64, 65, 66, 67, 68, 69, 70, 71,  0,  9, 18, 27, 36, 45, 54, 72, 55, 56, 73, 74}, // 63
        { 63, 65, 66, 67, 68, 69, 70, 71,  1, 10, 19, 28, 37, 46, 55, 73, 54, 56, 72, 74}, // 64
        { 63, 64, 66, 67, 68, 69, 70, 71,  2, 11, 20, 29, 38, 47, 56, 74, 54, 55, 72, 73}, // 65
        { 63, 64, 65, 67, 68, 69, 70, 71,  3, 12, 21, 30, 39, 48, 57, 75, 58, 59, 76, 77}, // 66
        { 63, 64, 65, 66, 68, 69, 70, 71,  4, 13, 22, 31, 40, 49, 58, 76, 57, 59, 75, 77}, // 67
        { 63, 64, 65, 66, 67, 69, 70, 71,  5, 14, 23, 32, 41, 50, 59, 77, 57, 58, 75, 76}, // 68
        { 63, 64, 65, 66, 67, 68, 70, 71,  6, 15, 24, 33, 42, 51, 60, 78, 61, 62, 79, 80}, // 69
        { 63, 64, 65, 66, 67, 68, 69, 71,  7, 16, 25, 34, 43, 52, 61, 79, 60, 62, 78, 80}, // 70
        { 63, 64, 65, 66, 67, 68, 69, 70,  8, 17, 26, 35, 44, 53, 62, 80, 60, 61, 78, 79}, // 71
        { 73, 74, 75, 76, 77, 78, 79, 80,  0,  9, 18, 27, 36, 45, 54, 63, 55, 56, 64, 65}, // 72
        { 72, 74, 75, 76, 77, 78, 79, 80,  1, 10, 19, 28, 37, 46, 55, 64, 54, 56, 63, 65}, // 73
        { 72, 73, 75, 76, 77, 78, 79, 80,  2, 11, 20, 29, 38, 47, 56, 65, 54, 55, 63, 64}, // 74
        { 72, 73, 74, 76, 77, 78, 79, 80,  3, 12, 21, 30, 39, 48, 57, 66, 58, 59, 67, 68}, // 75
        { 72, 73, 74, 75, 77, 78, 79, 80,  4, 13, 22, 31, 40, 49, 58, 67, 57, 59, 66, 68}, // 76
        { 72, 73, 74, 75, 76, 78, 79, 80,  5, 14, 23, 32, 41, 50, 59, 68, 57, 58, 66, 67}, // 77
        { 72, 73, 74, 75, 76, 77, 79, 80,  6, 15, 24, 33, 42, 51, 60, 69, 61, 62, 70, 71}, // 78
        { 72, 73, 74, 75, 76, 77, 78, 80,  7, 16, 25, 34, 43, 52, 61, 70, 60, 62, 69, 71}, // 79
        { 72, 73, 74, 75, 76, 77, 78, 79,  8, 17, 26, 35, 44, 53, 62, 71, 60, 61, 69, 70}  // 80
    };
    int[] board;  // 棋盤
    int[] count; // 每個格子被消去的數目
    boolean[][] elim;  // 紀錄每個格子被消掉的數字
    int found; // 有幾個格子已經決定好了
    public Unique(int[] data) {
        int i, j;
        board = new int[81];
        count = new int[81];
        elim = new boolean[81][9];
        for (i = 0; i < 81; i++) { // 先掃瞄題目
            if (data[i] != 0) { // 這位置的數字已知
                board[i] = data[i];
                found++;
                for (j = 0; j < 20; j++) { // 掃描不能重複的其它20格
                    if (elim[near[i][j]][data[i]-1] == false) { // 如果這位置還沒被消去
                        count[near[i][j]]++;
                    }
                    elim[near[i][j]][data[i]-1] = true;
                }
            }
        }
    }
    public Unique print() {
        for (int i = 0; i < 81; i++) {
            System.out.print((char)(board[i]+'0'));
            if ((i + 1) % 9 == 0) {
                System.out.println();
            }
        }
        System.out.println();
        return this;
    }
    public Vector sol() {
        int i, j, max, maxAt;
        Vector rel = new Vector();
        for (i = 0; i < 81; i++) { // 掃瞄每個格子
            if (board[i] == 0 && count[i] == 8) { // 如果還沒確定,但只剩一種可能了, 則直接選取
                for (j = 0; j < 9; j++) { // 檢查該填那個數字
                    if (!elim[i][j]) {
                        board[i] = j + 1; // 填上去
                        found++; // 多找到一個
                        for (int k = 0; k < 20; k++) { // 標示其它20格不能再選此數字
                            if (elim[near[i][k]][j] == false) {
                                count[near[i][k]]++;
                            }
                            elim[near[i][k]][j] = true;
                        }
                        break;
                    }
                }
                i = -1; // 重頭在掃一次
            }
        }
        if (found == 81) {
            rel.addElement(this);
        } else {
            max = maxAt = -1;
            // 只展開最少可能的格子
            for (i = 0; i < 81; i++) {
                if (board[i] == 0 && count[i] > max) {
                    max = count[i];
                    maxAt = i;
                }
            }
            // 依次展開各種可能性
            for (i = 0; i < 9; i++) { // 逐一檢查
                if (!elim[maxAt][i]) {
                    board[maxAt] = i + 1;
                    Vector tmp = (new Unique(board)).sol(); // 複製一份,並找其解
                    for (j = 0; j < tmp.size(); j++) { // 將找到的解記下來
                        rel.addElement(tmp.elementAt(j));
                    }
                    board[maxAt] = 0; // 還元, 以展開下一個可能性
                }
            }
        }
        return rel;
    }
    public static void printResult(Vector tmp) {
        for (int i = 0; i < tmp.size(); i++) {
            System.out.println("Solution "+(i+1)+":");
            ((Unique)tmp.elementAt(i)).print();
        }
    }
    public static void main(String[] argv) {
        int[] data0 = {
            5,3,0,0,7,0,0,0,0,
            6,0,0,1,9,5,0,0,0,
            0,9,8,0,0,0,0,6,0,
            8,0,0,0,6,0,0,0,3,
            4,0,0,8,0,3,0,0,1,
            7,0,0,0,2,0,0,0,6,
            0,6,0,0,0,0,2,8,0,
            0,0,0,4,1,9,0,0,5,
            0,0,0,0,8,0,0,7,9};
        int[] data1 = {
            0,5,0,0,0,1,4,0,0,
            2,0,3,0,0,0,7,0,0,
            0,7,0,3,0,0,1,8,2,
            0,0,4,0,5,0,0,0,7,
            0,0,0,1,0,3,0,0,0,
            8,0,0,0,2,0,6,0,0,
            1,8,5,0,0,6,0,9,0,
            0,0,2,0,0,0,8,0,3,
            0,0,6,4,0,0,0,7,0};
        int[] data2 = {
            6,0,0,1,0,0,0,5,0,
            0,4,0,0,0,2,0,0,3,
            0,0,3,0,5,0,1,0,0,
            0,1,0,0,0,3,0,0,4,
            0,0,5,0,6,0,9,0,0,
            2,0,0,9,0,0,0,1,0,
            0,0,6,0,8,0,7,0,0,
            3,0,0,7,0,0,0,6,0,
            0,2,0,0,0,6,0,0,1};
        int[] data3 = {
            3,2,0,0,0,0,7,0,0,
            0,0,9,8,0,0,3,0,0,
            0,0,0,0,0,6,0,0,2,
            0,5,0,0,0,9,0,0,3,
            0,4,0,0,0,0,0,2,0,
            7,0,0,3,0,0,0,4,0,
            1,0,0,7,0,0,0,0,0,
            0,0,6,0,0,2,5,0,0,
            0,0,4,0,0,0,0,8,6};
        int[] data4 = {
            4,5,0,0,0,0,0,0,6,
            0,0,3,0,0,1,0,0,7,
            0,0,0,0,2,3,0,0,0,
            0,0,0,0,4,0,2,5,0,
            0,0,9,3,0,2,1,0,0,
            0,8,1,0,7,0,0,0,0,
            0,0,0,5,8,0,0,0,0,
            9,0,0,7,0,0,8,0,0,
            7,0,0,0,0,0,0,6,4};
        int[] data5 = {
            0,0,4,0,5,0,0,6,0,
            0,6,0,1,0,0,8,0,9,
            3,0,0,0,0,7,0,0,0,
            0,8,0,0,0,0,5,0,0,
            0,0,0,4,0,3,0,0,0,
            0,0,6,0,0,0,0,7,0,
            0,0,0,2,0,0,0,0,6,
            1,0,5,0,0,4,0,3,0,
            0,2,0,0,7,0,1,0,0};
        int[] data6 = {
            0,0,0,0,0,4,0,0,7,
            0,0,8,5,0,1,0,0,4,
            0,5,0,0,0,0,2,8,0,
            0,7,0,4,0,0,0,0,0,
            0,0,1,9,0,3,5,0,0,
            0,0,0,0,0,8,0,7,0,
            0,2,4,0,0,0,0,6,0,
            8,0,0,1,0,2,3,0,0,
            5,0,0,8,0,0,0,0,0};
        int[] data7 = {
            0,0,0,0,0,0,0,0,0,
            0,0,7,8,3,0,0,0,0,
            0,0,5,0,0,2,6,4,0,
            0,0,2,6,0,0,0,7,0,
            0,4,0,0,0,0,0,8,0,
            0,6,0,0,0,3,2,0,0,
            0,2,8,4,0,0,5,0,0,
            0,0,0,0,9,6,1,0,0,
            0,0,0,0,0,0,0,0,0};
        int[] data8 = {
            6,0,0,0,0,0,5,4,0,
            0,3,0,0,2,7,0,0,0,
            0,0,0,0,0,9,0,0,0,
            0,0,0,0,0,0,0,5,3,
            0,0,4,0,0,0,8,0,0,
            2,6,0,0,0,0,0,0,0,
            0,0,0,8,0,0,0,0,0,
            0,0,0,4,6,0,0,7,0,
            0,5,9,0,0,0,0,0,2};
        int[] data9 = {
            0,7,0,0,1,0,0,9,0,
            9,0,0,8,0,0,0,0,7,
            0,0,3,0,0,0,0,0,6,
            0,4,0,0,0,1,5,0,0,
            0,3,0,0,0,0,0,1,0,
            0,0,2,7,0,0,0,6,0,
            5,0,0,0,0,0,6,0,0,
            6,0,0,0,0,5,0,0,2,
            0,8,0,0,2,0,0,7,0};
        int[] data10 = {
            2,0,0,6,7,0,0,0,0,
            0,0,6,0,0,0,2,0,1,
            4,0,0,0,0,0,8,0,0,
            5,0,0,0,0,9,3,0,0,
            0,3,0,0,0,0,0,5,0,
            0,0,2,8,0,0,0,0,7,
            0,0,1,0,0,0,0,0,4,
            7,0,8,0,0,0,6,0,0,
            0,0,0,0,5,3,0,0,8};
        printResult((new Unique(data0)).print().sol());
        printResult((new Unique(data1)).print().sol());
        printResult((new Unique(data2)).print().sol());
        printResult((new Unique(data3)).print().sol());
        printResult((new Unique(data4)).print().sol());
        printResult((new Unique(data5)).print().sol());
        printResult((new Unique(data6)).print().sol());
        printResult((new Unique(data7)).print().sol());
        printResult((new Unique(data8)).print().sol());
        printResult((new Unique(data9)).print().sol());
        printResult((new Unique(data10)).print().sol());
    }
}