我必须编写蛮力算法来用预定方法求解数独。
对于解决方法，我有点犹豫。作业说，我们必须至少使用给定的方法，即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;
}
}
最佳答案
您的代码中有很多问题。
首先，方法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 ! keycheck;接下来，您尝试使用蛮力，但不要回溯。方法对
solve，teilsolve应该在任何级别处理不可接受的值，并且应为：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
关于java - 数独蛮力算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26909236/