RecursionMatrix

package sudoku;

import java.util.stream.IntStream;



public class Matrix {

    public static void main(String[] args) {
        Matrix matrix = new Matrix();

        int[][] M1 = new int[][] {{0, 0, 0, 0},     // Empty Pseudoco
                                  {0, 0, 0, 0},
                                  {0, 0, 0, 0},
                                  {0, 0, 0, 0}};

        int[][] M2 = new int[][] {{1, 2, 0, 0},     // Unsolvable Pseudoco
                                  {4, 3, 0, 0},
                                  {0, 0, 0, 0},
                                  {0, 1, 0, 1}};

        int[][] M3 = new int[][] {{1, 2, 3, 4},     // Mising (i,j) (4,4) to be solved
                                  {3, 4, 1, 2},
                                  {2, 1, 4, 3},
                                  {4, 3, 2, 0}};

        int[][] M4 = new int[][] {{0, 3, 0, 0},
                                  {2, 0, 0, 0},
                                  {3, 0, 1, 0},
                                  {0, 0, 0, 0}};

        int[][] M5 = new int[][] {{3, 0, 6, 5, 0, 8, 4, 0, 0},
                                  {5, 2, 0, 0, 0, 0, 0, 0, 0},
                                  {0, 8, 7, 0, 0, 0, 0, 3, 1},
                                  {0, 0, 3, 0, 1, 0, 0, 8, 0},
                                  {9, 0, 0, 8, 6, 3, 0, 0, 5},
                                  {0, 5, 0, 0, 9, 0, 6, 0, 0},
                                  {1, 3, 0, 0, 0, 0, 2, 5, 0},
                                  {0, 0, 0, 0, 0, 0, 0, 7, 4},
                                  {0, 0, 5, 2, 0, 6, 3, 0, 0}};

        int[][] M6 = new int[][]   {{8, 0, 0, 0, 0, 0, 0, 0, 0},
                                    {0, 0, 3, 6, 0, 0, 0, 0, 0},
                                    {0, 7, 0, 0, 9, 0, 2, 0, 0},
                                    {0, 5, 0, 0, 0, 7, 0, 0, 0},
                                    {0, 0, 0, 0, 4, 5, 7, 0, 0},
                                    {0, 0, 0, 1, 0, 0, 0, 3, 0},
                                    {0, 0, 1, 0, 0, 0, 0, 6, 8},
                                    {0, 0, 8, 5, 0, 0, 0, 1, 0},
                                    {0, 9, 0, 0, 0, 0, 4, 0, 0}};

        System.out.println(matrix.sudokuCount(M1, 1, 1));
    }

    private final int n = 2;
    private volatile long count = 0;

    public boolean BackTrackingSudokuSolver(int[][] M, int i, int j) {
        if (!isSudokuValid(M))
            return false;
        if (outsideGrid(M, i, j))
            return true;
        for (int k = 1; k <= M.length; k++) {
            if (canPlace(M, i, j, k)) {
                boolean isClue;
                isClue = (M[i-1][j-1] != 0) ? true : false;
                M[i-1][j-1] = (isClue) ? M[i-1][j-1] : k;
                //System.out.println("* * * *");
                //printM(M);
                int iPrime = (j < M.length) ? i : i + 1;
                int jPrime = (j < M.length) ? j + 1 : 1;
                if (BackTrackingSudokuSolver(M, iPrime, jPrime))
                    return true;
                M[i-1][j-1] = (isClue) ? k : 0;
                }
            }
        return false;
    }

     public long BackTrackingSudokuSolverCount(int[][] M, int i, int j) {
        if (!isSudokuValid(M))
            return count;
        if (outsideGrid(M, i, j)){
            count++;
            return count;
        }

        int[][] array = new int[M.length][];
        for (int r = 0; r < M.length; r++) {
            array[r] = M[r].clone();
        }

        for (int c = 1; c <= array.length; c++) {
            for (int r = 1; r <= array.length; r++) {
                for (int k = 1; k <= M.length; k++) {
                    for (int a = 0; a < M.length; a++) {
                        array[a] = M[a].clone();
                    }
                    if (canPlace(array, c, r, k)) {
                        boolean isClue;
                        isClue = (array[c-1][r-1] != 0) ? true : false;
                        array[c-1][r-1] = (isClue) ? array[c-1][r-1] : k;
                        //System.out.println("* * * *");
                        //printM(M);
                        int iPrime = (r < M.length) ? c : c + 1;
                        int jPrime = (r < M.length) ? r + 1 : 1;
                        count++;
                        BackTrackingSudokuSolver(array, iPrime, jPrime);
                        if (BackTrackingSudokuSolver(M, iPrime, jPrime))
                            count++;
                            //return true;
                            //array[c-1][r-1] = (isClue) ? k : 0;
                        }
                    }
            }
        }
        return count;
    }

    public long sudokuCount(int[][] M, int i, int j) {
        int[][] array = new int[M.length][];
        for (int r = 0; r < M.length; r++) {
            array[r] = M[r].clone();
        }

        for (int c = 1; c <= array.length; c++) {
            for (int r = 1; r <= array.length; r++) {
                for (int k = 1; k <= array.length; k++) {
                    for (int a = 0; a < M.length; a++) {
                        array[a] = M[a].clone();
                    }
                    if (canPlace(array, c, r, k) && array[c-1][r-1] == 0){
                        boolean isClue;
                        isClue = (array[c-1][r-1] != 0) ? true : false;
                        array[c-1][r-1] = (isClue) ? array[c-1][r-1] : k;
                        if (BackTrackingSudokuSolver(array, i, j) && isSudokuSolved(array))
                            count++;
                    }
                }
            }
        }
        return count;
    }

    public boolean canPlace(int[][] M, int i, int j, int k) {
        if (M[i-1][j-1] != 0 && M[i-1][j-1] != k)
            return false;
        int[][] array = new int[M.length][];
        for (int r = 0; r < M.length; r++) {
            array[r] = M[r].clone();
        }
        array[i-1][j-1] = k;
        return
        rowConstraint(array, i-1) &&
        columnConstraint(array, j-1) &&
        subgridContraint(array, i-1, j-1);
    }

    public boolean rowConstraint(int[][] M, int i) {
        boolean[] constraint = new boolean[n*n];
        return IntStream.range(0, n*n)
                .allMatch(c -> checkConstraint(M, i, constraint, c));
    }

    public boolean columnConstraint(int[][] M, int j) {
        boolean[] constraint = new boolean[n*n];
        return IntStream.range(0, n*n)
                .allMatch(r -> checkConstraint(M, r, constraint, j));
    }

    public boolean subgridContraint(int[][] M, int i, int j) {
        boolean[] constraint = new boolean[n*n];
        int rowStart = (i / n) * n;
        int rowEnd   = rowStart + n;

        int columnStart = (j / n) * n;
        int columnEnd   = (columnStart + n);

        for (int row = rowStart; row < rowEnd; row++) {
            for (int column = columnStart; column < columnEnd; column++) {
                if (!checkConstraint(M, row, constraint, column))
                    return false;
            }
        }
        return true;
    }

    public boolean checkConstraint(int[][] M, int i, boolean[] constraint, int j) {
        if (M[i][j] != 0) {
            if (!constraint[M[i][j] - 1]) {
                constraint[M[i][j] - 1] = true;
            } else {
                return false;
            }
        }
        return true;
    }

    private boolean outsideGrid(int[][] M, int i, int j) {
        try {
            if (M[i-1][j-1] != 0);
            // boolean inBounds = (index >= 0) && (index < array.length);
        } catch (IndexOutOfBoundsException e) {
            return true;
        }
        return false;
    }

    private void printM(int[][] M) {
        for (int row = 0; row < n*n; row++) {
            for (int column = 0; column < n*n; column++) {
                System.out.print(M[row][column] + " ");
            }
            System.out.println();
        }
    }

    public boolean isSudokuSolved(int[][] M) {
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {
                if (!isSolved(M, i, j) || M[i][j] == 0)
                    return false;
            }
        }
        return true;
    }

    public boolean isSudokuValid(int[][] M) {
        for (int i = 0; i < M.length; i++) {
            for (int j = 0; j < M.length; j++) {
                if (!isSolved(M, i, j))
                    return false;
            }
        }
        return true;
    }

    public boolean isSolved(int[][] M, int i, int j) {
        return
        rowConstraint(M, i) &&
        columnConstraint(M, j) &&
        subgridContraint(M, i, j);
    }

}