我最近编写了一个简单直接的 C 代码来解决数独问题,并使用递归和回溯。您将在下面找到我刚刚描述的代码。一切正常。
#include <stdio.h>
# define INsigned 0
int grid[9][9];
void printGrid(){
int row,col;
for(row=0;row<9;row++){
for(col=0;col<9;col++){
printf("%2d",grid[row][col]);
}
printf("\n");
}
}
int Unsigned(int *row, int* col){
int i,j;
for(i=0;i<9;i++){
for(j=0;j<9;j++){
if(grid[i][j]==0){
*row=i;
*col=j;
return 1;
}
}
}
return 0;
}
int check(){
int row=0;
int col=0;
int i;
if(Unsigned(&row, &col)==0)
return 1;
for(i=1;i<=9;i++){
if(conflict(i,row-row%3, col-col%3, row, col)==0){
grid[row][col]=i;
if(check()==1)
return 1;
}
grid[row][col]=0;
}
return 0;
}
int conflict (int num, int srow, int scol, int row, int col){
int i,j;
for(i=0;i<9;i++){
if(grid[row][i]==num) return 1;
if(grid[i][col]==num) return 2;
}
for(i=0;i<3;i++){
for(j=0;j<3;j++){
if(grid[i+srow][j+scol]==num) return 3;
}
}
return 0;
}
int main(){
int i;
for(i=0;i<9;i++){
scanf("%d %d %d %d %d %d %d %d %d",&grid[i][0],&grid[i][1],&grid[i][2],
&grid[i][3],&grid[i][4],&grid[i][5],
&grid[i][6],&grid[i][7],&grid[i][8]);
}
check();
printf("\n\n");
printGrid();
}
输入是:
0 0 0 0 0 9 0 0 3
0 0 5 0 0 0 0 9 0
3 0 0 8 1 0 2 0 0
0 0 0 0 4 3 1 0 0
5 6 0 0 9 0 0 7 8
0 0 3 5 6 0 0 0 0
9 0 6 0 8 7 0 0 4
0 2 0 0 0 0 8 0 0
1 0 0 9 0 0 0 0 0
因此,当我尝试在 java 中编写确切的算法时,就会出现问题。由于 java 不允许原始类型的引用传递,而且我在查找下一个空单元格的无符号函数中使用了引用传递。我决定在java中使用一个包装类来克服这个障碍但是这个代码的java等价物不能正常工作这里是代码。
public class intObj {
public int value;
}
public class Grid {
int grid[][] = new int[9][9];
int r = 0;
int c = 0;
public Grid(int grid[][]) {
this.grid = grid;
}
void printGrid() {
int row;
int col;
System.out.println("");
for (row = 0; row < 9; row++) {
for (col = 0; col < 9; col++) {
System.out.printf("%2d", grid[row][col]);
}
System.out.println("");
}
}
int conflict(int num, int srow, int scol, int row, int col) {
int i, j;
for (i = 0; i < 9; i++) {
if (grid[row][i] == num) {
return 1;
}
if (grid[i][col] == num) {
return 2;
}
}
for (i = 0; i < 3; i++) {
for (j = 0; j < 3; j++) {
if (grid[i + srow][j + scol] == num) {
return 3;
}
}
}
return 0;
}
int Unsigned(intObj row, intObj col) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (grid[i][j] == 0) {
row.value = i;
col.value = j;
return 1;
}
}
}
return 0;
}
int check() {
intObj row = new intObj();
intObj col = new intObj();
if (Unsigned(row, col) == 0) {
return 1;
}
for (int i = 1; i <= 9; i++) {
if (conflict(i, (row.value) - (row.value) % 3,
(col.value) - (col.value) % 3, row.value, col.value) == 0) {
grid[row.value][col.value] = i;
if (check() == 1) {
return 1;
}
}
grid[row.value][col.value] = 0;
}
return 0;
}
}
主要类:
public class Main {
public static void main(String args[]) {
int grid[][] = {{0, 0, 0, 0, 0, 9, 0, 0, 3},
{0, 0, 5, 0, 0, 0, 0, 9, 3},
{3, 0, 0, 8, 1, 0, 2, 0, 0},
{0, 0, 0, 0, 4, 3, 1, 0, 0},
{5, 6, 0, 0, 9, 0, 0, 7, 8},
{0, 0, 3, 5, 6, 0, 0, 0, 0},
{9, 0, 6, 0, 8, 7, 0, 0, 4},
{0, 2, 0, 0, 0, 0, 8, 0, 0},
{1, 0, 0, 9, 0, 0, 0, 0, 0}};
Grid g = new Grid(grid);
g.check();
g.printGrid();
}
}
很抱歉,很长的帖子任何帮助将不胜感激。