私は最近、数独を解き、再帰とバックトラッキングを使用する単純でわかりやすい 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はプリミティブ型の参照渡しを許可していないため、次の空のセルを探すUnsigned関数で参照渡しを使用したためです。この障害を克服するために 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();
}
}
長い投稿で申し訳ありませんが、どんな助けでも大歓迎です。