#include <stdio.h>
int isAvailable(int puzzle[][9], int row, int col, int num)
{
int rowStart = (row/3) * 3;
int colStart = (col/3) * 3;
int i, j;
for(i=0; i<9; ++i)
{
if (puzzle[row][i] == num) return 0;
if (puzzle[i][col] == num) return 0;
if (puzzle[rowStart + (i%3)][colStart + (i/3)] == num) return 0;
}
return 1;
}
int fillSudoku(int puzzle[][9], int row, int col)
{
int i;
if(row<9 && col<9)
{
if(puzzle[row][col] != 0)
{
if((col+1)<9) return fillSudoku(puzzle, row, col+1);
else if((row+1)<9) return fillSudoku(puzzle, row+1, 0);
else return 1;
}
else
{
for(i=0; i<9; ++i)
{
if(isAvailable(puzzle, row, col, i+1))
{
puzzle[row][col] = i+1;
if((col+1)<9)
{
if(fillSudoku(puzzle, row, col +1)) return 1;
else puzzle[row][col] = 0;
}
else if((row+1)<9)
{
if(fillSudoku(puzzle, row+1, 0)) return 1;
else puzzle[row][col] = 0;
}
else return 1;
}
}
}
return 0;
}
else return 1;
}
int main()
{
int i, j;
int puzzle[9][9]={{0, 0, 0, 0, 0, 0, 0, 9, 0},
{1, 9, 0, 4, 7, 0, 6, 0, 8},
{0, 5, 2, 8, 1, 9, 4, 0, 7},
{2, 0, 0, 0, 4, 8, 0, 0, 0},
{0, 0, 9, 0, 0, 0, 5, 0, 0},
{0, 0, 0, 7, 5, 0, 0, 0, 9},
{9, 0, 7, 3, 6, 4, 1, 8, 0},
{5, 0, 6, 0, 8, 1, 0, 7, 4},
{0, 8, 0, 0, 0, 0, 0, 0, 0}};
if(fillSudoku(puzzle, 0, 0))
{
printf("\n+-----+-----+-----+\n");
for(i=1; i<10; ++i)
{
for(j=1; j<10; ++j) printf("|%d", puzzle[i-1][j-1]);
printf("|\n");
if (i%3 == 0) printf("+-----+-----+-----+\n");
}
}
else printf("\n\nNO SOLUTION\n\n");
return 0;
}
测试运行: br />
#1 楼
您的解决方案简短而有趣。希望我的答案也可以,因为rolfl涵盖了我所看到的大部分内容。 :)solveSudoku
可能会更好地传达它正在解决难题的事实。 fillSudoku
听起来像一个函数,用于从文件或字符串或其他内容填充初始位置。您可以通过降低
!= 0
的最大C值来缩短“是否已填充单元格”检查: br /> if(puzzle[row][col])
您正在复制使
fillSudoku
中的单元格索引前进的代码:一次,如果该单元格已被填充,则在下一次猜测时再次出现。您可以删除后者,并只需传递相同的单元格索引,因为首先要设置单元格的值。if(isAvailable(puzzle, row, col, i+1))
{
puzzle[row][col] = i+1;
if(fillSudoku(puzzle, row, col) return 1;
else puzzle[row][col] = 0;
}
#2 楼
我很乐意浏览并发现此代码不能很好地完成的所有事情……但是,它简短,甜蜜并且可以正常工作,并且它本身在某种程度上说明了它的先进性。该解决方案在除CPU周期以外的所有资源上都是非常轻量级的,并且在堆栈上也不会占用太多资源。总而言之,它整洁且结构良好。一些小小的批评:在您的
isAvailable()
方法中,您声明了j
,但不要使用它。 用于检查块的奇特的模/除机制(
puzzle[rowStart + (i%3)][colStart + (i/3)] == num
)真是奇特...可能需要某种注释。我已经完成数学运算,可以看到它是正确的,但是那里的一些帮助还是有用的。避免重复而又不增加复杂性的好方法。根据我的计算,您要双重检查4个值,然后三重检查1个。这就是5/27个检查是多余的...但是,正如我所说,我认为避免这些检查会比冗余更昂贵。 >在您的isAvailable()
方法中,您声明fillSudoku
并将其用作i
。由于在这种情况下,for(i=0; i<9; ++i)
实际上不是某个数组的索引或简单的循环限制器,但实际上是一个拼图数字,因此您应该做两件事:将其重命名为类似
i
将循环更改为:
digit
,然后可以删除在循环内执行的所有冗余for(digit=1; digit<=9; ++digit)
操作(例如+1
)