java - 数独蛮力算法

Question

我必须编写一个蛮力算法以使用预定方法解决数独问题。对于解决方法，我有点精神上的障碍。作业说我们必须至少使用给定的方法，它们是isPermutation、isPermutationRow、isPermutationCol、isPermutationBlock、isPermutationMatrix、isValid 和solve。

我真的不知道什么时候在 solve 方法中返回值，因为它必须是递归的。

如果有任何帮助，我将不胜感激 :)

package gdp.aufgabe22;

public class Sudoku {

public static void main(String[] args) {
    int[][] d = { {0,0,3,0,2,0,6,0,0},
                  {9,0,0,3,0,5,0,0,1},
                  {0,0,1,8,0,6,4,0,0},
                  {0,0,8,1,0,2,9,0,0},
                  {7,0,0,0,0,0,0,0,8},
                  {0,0,6,7,0,8,2,0,0},
                  {0,0,2,6,0,9,5,0,0},
                  {8,0,0,2,0,3,0,0,9},
                  {0,0,5,0,1,0,3,0,0}
    };
    int[][] s = solve(d);
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            System.out.print(s[i][j] + " ");
        }
        System.out.print("\n");
    }
    System.out.println();
}

public static boolean isPermutation(int[] a) {
    int[][] key = new int[2][a.length];
    key[0] = a;
    for (int i = 0; i < key.length; i++) {
        key[1][i] = 0;
    }
    for (int i = 0; i < key.length; i++) {
        if (a[i]>0) {
            key[1][a[i]-1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < a.length; i++) {
        if(key[1][i]>1) {
            keycheck = true;
        }
    }
    if (keycheck == true) {
        return false;
    }
    else {
        return true;
    }
}

public static boolean isPermutationRow(int[][] a, int row) {
        int[] key = new int[a[row].length];
        key = a[row];
        return isPermutation(key);
}

public static boolean isPermutationCol(int[][] a, int col) {
    int[] key = new int[a.length];
    for (int i = 0; i < key.length; i++) {
        key[i] = a[i][col];
    }
    return isPermutation(key);
}

public static boolean isPermutationMatrix(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        if (!isPermutationRow(a, i)) {
            return false;
        }
    }
    for (int i = 0; i < a.length; i++) {
        if (!isPermutationCol(a, i)) {
            return false;
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            switch (i) {
            case 0: switch(j) {
                case 0: if(!isPermutationBlock(a,0,2,0,2)) {
                    return false;
                }
                case 3: if(!isPermutationBlock(a,0,2,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,0,2,6,8)) {
                    return false;
                }
                default: break;
            }
            case 3: switch(j) {
                case 0: if(!isPermutationBlock(a,3,5,0,2)) {
                    return false;
                }   
                case 3: if(!isPermutationBlock(a,3,5,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,3,5,6,8)) {
                    return false;
                }
                default: break;
            }   
            case 6: switch(j) {
                case 0: if(!isPermutationBlock(a,6,8,0,2)) {
                    return false;
                }   
                case 3: if(!isPermutationBlock(a,6,8,3,5)) {
                    return false;
                }
                case 6: if(!isPermutationBlock(a,6,8,6,8)) {
                    return false;
                }
                default: break;
            }   
            default: break;
        }
        }
    }
    return true;
}

public static boolean isPermutationBlock(int[][] a, int minRow, int maxRow, int minCol, int maxCol) {
    int[][] key = new int[2][(maxRow-minRow+1)+(maxCol-minCol+1)];
    int[][] countfeld = new int[2][9];
    for (int i = 0; i < 9; i++) {
        countfeld[0][i] = i+1;
    }
    int keycount = 0;
    for (int i = minRow; i<maxRow; i++) {
        for (int j = minCol; j<maxCol; j++) {
            key[0][keycount] = a[i][j];
            keycount++;
        }
    }
    for (int i = 0; i < countfeld[0].length; i++) {
        countfeld[1][i] = 0;
    }
    for (int i = 0; i < key[0].length; i++) {
        if (key[0][i]>0) {
            countfeld[1][key[0][i]-1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < key[0].length; i++) {
        if(countfeld[1][i]>1) {
            keycheck = true;
        }
    }
    if (keycheck == true) {
        return false;
    }
    else {
        return true;
    }
}

public static boolean isValid(int[][] a) {
    if (a.length != 9 || a[0].length != 9) {
        return false;
    }
    return (isPermutationMatrix(a));
}

public static int[][] solve(int[][] a) {
    int[] freeslot = findfreeslot(a);
    int f1 = freeslot[0];
    int f2 = freeslot[1];
    if (f1 == -1) {
        return a;
    }
    teilsolve(f1, f2, a);
    return a;
}

public static void teilsolve(int f1, int f2, int[][] a) {
    int[][] temp = new int[a.length][a[0].length];
    for (int y = 0; y < a.length; y++) {
        for (int z = 0; z < a[0].length; z++) {
            temp[y][z] = a[y][z];
        }
    }
    for (int i = 1; i < 10; i++) {
        a[f1][f2] = i;
        boolean valide = isValid(a);
        if (valide) {
            a = solve(a);
            break;
        }
    }
}

public static int[] findfreeslot(int[][]a) {
    int[] key = {-1,-1};
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (a[i][j] == 0) {
                key[0] = i;
                key[1] = j;
                return key;
            }
        }
    }
    return key;
}
}

Answer 1

你的代码中有很多问题。

首先，isPermutation 方法是错误的:您循环直到 key.length 为 2 而您应该循环到 9 a.length !该方法应该是:

public static boolean isPermutation(int[] a) {
    int[][] key = new int[2][a.length];
    key[0] = a;
    for (int i = 0; i < a.length; i++) {
        key[1][i] = 0;
    }
    for (int i = 0; i < a.length; i++) {
        if (a[i] > 0) {
            key[1][a[i] - 1]++;
        }
    }
    boolean keycheck = false;
    for (int i = 0; i < a.length; i++) {
        if (key[1][i] > 1) {
            keycheck = true;
            break;
        }
    }
    if (keycheck == true) {
        return false;
    } else {
        return true;
    }
}

正如 Patrick J Abare II 所指出的，结尾确实应该是 return !键盘检查；

接下来您尝试使用蛮力，但永远不要原路返回。 solve、teilsolve 这对方法应该处理任何级别的 Not Acceptable 值，并且应该是:

public static int[][] solve(int[][] a) {
    int[] freeslot = findfreeslot(a);
    int f1 = freeslot[0];
    int f2 = freeslot[1];
    if (f1 == -1) {
        return a;
    }
    a = teilsolve(f1, f2, a);
    return a;
}

public static int [][] teilsolve(int f1, int f2, int[][] a) {
    int [][] temp2;
    int[][] temp = new int[a.length][a[0].length];
    for (int y = 0; y < a.length; y++) {
        for (int z = 0; z < a[0].length; z++) {
            temp[y][z] = a[y][z];
        }
    }
    for (int i = 1; i < 10; i++) {
        temp[f1][f2] = i;
        boolean valide = isValid(temp);
        if (valide) {
            temp2 = solve(temp);
            if (temp2 != null) {return temp2;}
        }
    }
    return null;
}

这样，程序返回:

4 5 3 9 2 1 6 8 7 
9 2 7 3 6 5 8 4 1 
2 3 1 8 9 6 4 7 5 
5 4 8 1 7 2 9 3 6 
7 6 9 5 3 4 1 2 8 
1 9 6 7 4 8 2 5 3 
3 7 2 6 8 9 5 1 4 
8 1 4 2 5 3 7 6 9 
6 8 5 4 1 7 3 9 2