import java.util.ArrayList;

public class SudokuCSP {
    public int[][] board = boardSetUp();
    public int count = 0;
    public ArrayList<int[][]> boardList = new ArrayList<int[][]>();

    public static void main(String[] args) {
        SudokuCSP sudoku = new SudokuCSP();
        sudoku.commitSudoku();
    }

    public SudokuCSP() {
    }

    public int[][] boardSetUp() {
        int[][] board2 = new int[9][9];
        board2[0][1] = 9;
        board2[0][7] = 2;
        board2[0][8] = 5;
        board2[1][0] = 4;
        board2[1][2] = 5;
        board2[1][3] = 2;
        board2[2][1] = 6;
        board2[2][4] = 3;
        board2[3][0] = 2;
        board2[3][1] = 8;
        board2[3][3] = 3;
        board2[3][6] = 1;
        board2[3][8] = 9;
        board2[4][3] = 8;
        board2[4][5] = 1;
        board2[5][0] = 3;
        board2[5][2] = 7;
        board2[5][5] = 6;
        board2[5][7] = 4;
        board2[5][8] = 8;
        board2[6][4] = 1;
        board2[6][7] = 8;
        board2[7][5] = 3;
        board2[7][6] = 7;
        board2[7][8] = 2;
        board2[8][0] = 6;
        board2[8][1] = 3;
        board2[8][7] = 9;

        return board2;
    }

    public boolean checkRows(int value, int xPos, int yPos, int[][] b) {
        for (int i = 0; i < 9; i++) {
            if (b[yPos][i] == value && xPos != i)
                return false;
        }
        return true;

    }

    public boolean checkCols(int value, int xPos, int yPos, int[][] b) {
        for (int i = 0; i < 9; i++) {
            if (b[i][xPos] == value && yPos != i)
                return false;
        }
        return true;
    }

    public boolean checkSquare(int value, int xPos, int yPos, int[][] b) {
        for (int x = xPos / 3 * 3; x < xPos / 3 * 3; x++) {
            for (int y = yPos / 3 * 3; y < yPos / 3 * 3; y++) {
                if (x != xPos && y != yPos && value == b[y][x]) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean isLegalBoard(int value, int xPos, int yPos, int[][] b) {
        return checkRows(value, xPos, yPos, b)
                && checkCols(value, xPos, yPos, b)
                && checkSquare(value, xPos, yPos, b);
    }

    public int[] getNextPos(int b[][]) {
        int[] pos = new int[2];
        for (int x = 0; x < 9; x++) {
            for (int y = 0; y < 9; y++) {
                if (b[y][x] == 0) {
                    pos[0] = y;
                    pos[1] = x;
                    return pos;
                }
            }
        }
        pos[0] = 10;
        pos[1] = 10;
        return pos;
    }

    public boolean isGoal(int[] pos) {
        if (pos[0] == 10 && pos[1] == 10)
            return true;
        return false;
    }

    public void generateBoards(int[][] b, int[] pos) {
        for (int i = 1; i < 10; i++) {
            int[][] nb = generateDuplicate(b);
            nb[pos[0]][pos[1]] = i;
            if (isLegalBoard(i, pos[1], pos[0], nb)) {
                boardList.add(0, nb);
                count++;
            }
        }
    }

    public static int[][] generateDuplicate(int[][] b){
        int[][] nb = new int[9][9];
        for(int y=0;y<9;y++){
            for(int x=0;x<9;x++){
                nb[x][y] = b[x][y];
            }
        }
        return nb;
    }

    public void commitSudoku() {
        boardList.add(0, board);
        int[] pos = getNextPos(board);
        while (!boardList.isEmpty() && !isGoal(pos)) {
            int[][] newBoard = boardList.remove(0);
            generateBoards(newBoard, pos);
            pos = getNextPos(boardList.get(0));

        }
        for (int x = 0; x < 9; x++) {
            System.out.println();
            for (int y = 0; y < 9; y++) {
                System.out.print("" + boardList.get(0)[x][y] + " ");
            }
        }
    }
}