有谁知道一个简单的算法来检查数独配置是否有效？我想出的最简单的算法是伪代码中的（对于大小为 n 的板）
for each row
for each number k in 1..n
if k is not in the row (using another for-loop)
return not-a-solution
..do the same for each column
但我很确定一定有更好的（在更优雅的意义上）解决方案。效率是相当不重要的。
问问题
71296 次
25 回答
25
您需要检查数独的所有约束：
- 检查每一行的总和
- 检查每一列的总和
- 检查每个框的总和
- 检查每一行的重复数字
- 检查每列上的重复数字
- 检查每个盒子上的重复数字
这总共是 6 次检查.. 使用蛮力方法。
如果您知道棋盘的大小（即 3x3 或 9x9），可以使用某种数学优化
编辑：总和约束的解释：首先检查总和（如果总和不是 45，则停止）比检查重复项要快得多（也更简单）。它提供了一种丢弃错误解决方案的简单方法。
于 2008-11-14T09:26:52.300 回答
24
Peter Norvig 有一篇关于解决数独谜题（使用 python）的精彩文章，
https://norvig.com/sudoku.html
也许对于你想做的事情来说太多了，但无论如何它都是一本很棒的书
于 2008-11-14T10:33:33.210 回答
9
检查每一行、每一列和每一个方框，使其包含数字 1-9，并且没有重复。这里的大多数答案已经讨论过了。
但是如何有效地做到这一点？答案：使用类似的循环
result=0;
for each entry:
result |= 1<<(value-1)
return (result==511);
每个数字将设置结果的一位。如果所有 9 个数字都是唯一的，则将设置最低 9 位。所以“检查重复”测试只是检查所有9位是否设置，与测试结果==511相同。您需要进行 27 项检查……每行、每列和每一个框都要检查一次。
于 2009-04-29T12:22:39.750 回答
7
只是一个想法：你不需要检查每个 3x3 方块中的数字吗？
我试图弄清楚是否有可能在没有正确数独的情况下满足行和列条件
于 2008-11-14T09:07:01.093 回答
5
这是我在 Python 中的解决方案，我很高兴看到它是迄今为止最短的解决方案 :)
编码：
def check(sud):
zippedsud = zip(*sud)
boxedsud=[]
for li,line in enumerate(sud):
for box in range(3):
if not li % 3: boxedsud.append([]) # build a new box every 3 lines
boxedsud[box + li/3*3].extend(line[box*3:box*3+3])
for li in range(9):
if [x for x in [set(sud[li]), set(zippedsud[li]), set(boxedsud[li])] if x != set(range(1,10))]:
return False
return True
和执行：
sudoku=[
[7, 5, 1, 8, 4, 3, 9, 2, 6],
[8, 9, 3, 6, 2, 5, 1, 7, 4],
[6, 4, 2, 1, 7, 9, 5, 8, 3],
[4, 2, 5, 3, 1, 6, 7, 9, 8],
[1, 7, 6, 9, 8, 2, 3, 4, 5],
[9, 3, 8, 7, 5, 4, 6, 1, 2],
[3, 6, 4, 2, 9, 7, 8, 5, 1],
[2, 8, 9, 5, 3, 1, 4, 6, 7],
[5, 1, 7, 4, 6, 8, 2, 3, 9]]
print check(sudoku)
于 2011-04-04T11:58:45.657 回答
4
为每一行、每一列和每一方格创建一个布尔数组。数组的索引表示放入该行、列或正方形的值。换句话说，如果将 5 添加到第二行第一列，则将 rows[2][5] 以及 columns[1][5] 和 squares[4][5] 设置为 true，以表示行、列和方格现在有了5值。
无论您的原始电路板是如何表示的，这都是一种简单且非常快速的方法来检查它的完整性和正确性。只需按照它们在板上出现的顺序获取数字，然后开始构建此数据结构。当您在板上放置数字时，它变成了一个 O(1) 操作来确定是否有任何值在给定的行、列或正方形中重复。（您还需要检查每个值是否是合法数字：如果他们给您一个空白或过高的数字，您就知道该板不完整。）当您到达板的尽头时，您'会知道所有的值都是正确的，并且不需要更多的检查。
也有人指出，你可以使用任何形式的 Set 来做到这一点。以这种方式排列的数组只是 Set 的一种特别轻量级和高性能的形式，适用于小的、连续的、固定的数字集。如果您知道电路板的大小，您也可以选择进行位掩码，但考虑到效率对您来说没什么大不了的，这可能有点过于乏味了。
于 2009-10-13T18:42:19.030 回答
2
创建单元格集，其中每个集包含 9 个单元格，并为垂直列、水平行和 3x3 正方形创建集。
然后对于每个单元格，只需识别它所属的集合并分析它们。
于 2008-11-14T10:36:30.147 回答
2
您可以将集合（行、列、框）中的所有值提取到列表中，对其进行排序，然后与 '(1, 2, 3, 4, 5, 6, 7, 8, 9) 进行比较
于 2008-11-14T11:10:32.747 回答
2
我为一个班级项目做过一次。我一共使用了 27 个集合来表示每一行、每一列和每一框。我会在将数字添加到每个集合时检查数字（数字的每个位置都会将数字添加到 3 个集合、一行、一列和一个框），以确保用户只输入数字 1- 9. 填充集合的唯一方法是正确填充唯一数字。如果所有 27 组都被填满，那么这个谜题就解决了。设置从用户界面到 27 个集合的映射有点乏味，但其余的逻辑很容易实现。
于 2008-11-15T02:59:36.357 回答
1
检查是否：
when the sum of each row/column/box equals n*(n+1)/2
and the product equals n!
with n = number of rows or columns
这足以满足数独的规则。因为这将允许 O(n^2) 的算法，对正确的单元格求和和相乘。
看 n = 9，总和应该是 45，乘积 362880。
你会做这样的事情：
for i = 0 to n-1 do
boxsum[i] := 0;
colsum[i] := 0;
rowsum[i] := 0;
boxprod[i] := 1;
colprod[i] := 1;
rowprod[i] := 1;
end;
for i = 0 to n-1 do
for j = 0 to n-1 do
box := (i div n^1/2) + (j div n^1/2)*n^1/2;
boxsum[box] := boxsum[box] + cell[i,j];
boxprod[box] := boxprod[box] * cell[i,j];
colsum[i] := colsum[i] + cell[i,j];
colprod[i] := colprod[i] * cell[i,j];
rowsum[j] := colsum[j] + cell[i,j];
rowprod[j] := colprod[j] * cell[i,j];
end;
end;
for i = 0 to n-1 do
if boxsum[i] <> 45
or colsum[i] <> 45
or rowsum[i] <> 45
or boxprod[i] <> 362880
or colprod[i] <> 362880
or rowprod[i] <> 362880
return false;
于 2008-11-14T09:58:42.190 回答
1
前段时间，我写了一个数独检查器，它检查每一行上的重复数字、每列上的重复数字和每个盒子上的重复数字。不过，如果有人能想出几行 Linq 代码，我会很高兴的。
char VerifySudoku(char grid[81])
{
for (char r = 0; r < 9; ++r)
{
unsigned int bigFlags = 0;
for (char c = 0; c < 9; ++c)
{
unsigned short buffer = r/3*3+c/3;
// check horizontally
bitFlags |= 1 << (27-grid[(r<<3)+r+c])
// check vertically
| 1 << (18-grid[(c<<3)+c+r])
// check subgrids
| 1 << (9-grid[(buffer<<3)+buffer+r%3*3+c%3]);
}
if (bitFlags != 0x7ffffff)
return 0; // invalid
}
return 1; // valid
}
于 2009-04-29T11:27:16.873 回答
1
如果行/列的总和和乘积等于正确的数字 45/362880
于 2009-10-13T17:56:56.207 回答
1
首先，您需要创建一个布尔值，“正确”。然后，如前所述，创建一个 for 循环。循环的代码和之后的所有内容（在 java 中）如所述，其中 field 是具有相等边的二维数组， col 是另一个具有相同尺寸的数组，而 l 是一维数组：
for(int i=0; i<field.length(); i++){
for(int j=0; j<field[i].length; j++){
if(field[i][j]>9||field[i][j]<1){
checking=false;
break;
}
else{
col[field[i].length()-j][i]=field[i][j];
}
}
}
我不知道检查 3x3 框的确切算法，但是您应该在另一个for循环中使用“ /*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2)”检查字段和 col 中的所有行（继续直到达到行的长度） 。
于 2013-05-27T15:36:38.530 回答
1
这是 Python 中一个很好的可读方法：
from itertools import chain
def valid(puzzle):
def get_block(x,y):
return chain(*[puzzle[i][3*x:3*x+3] for i in range(3*y, 3*y+3)])
rows = [set(row) for row in puzzle]
columns = [set(column) for column in zip(*puzzle)]
blocks = [set(get_block(x,y)) for x in range(0,3) for y in range(0,3)]
return all(map(lambda s: s == set([1,2,3,4,5,6,7,8,9]), rows + columns + blocks))
每个 3x3 方格称为一个块，其中 9 个在 3x3 网格中。假设拼图作为列表列表输入，每个内部列表为一行。
于 2013-10-12T06:18:38.673 回答
1
def解决方案（板）：
我在船上：
如果总和（i）！= 45：
返回“不正确”
对于范围内的 i (9)：
温度2 = []
对于范围内的 x (9)：
temp2.append(板[i][x])
如果总和（temp2）！= 45：
返回“不正确”
返回“正确”
板= []
对于范围内的 i (9)：
inp = raw_input()
temp = [int(i) for i in inp]
board.append（临时）
打印解决方案（板）
于 2016-10-14T18:52:00.690 回答
0
假设 int sudoku[0..8,0..8] 是数独字段。
bool CheckSudoku(int[,] sudoku)
{
int flag = 0;
// Check rows
for(int row = 0; row < 9; row++)
{
flag = 0;
for (int col = 0; col < 9; col++)
{
// edited : check range step (see comments)
if ((sudoku[row, col] < 1)||(sudoku[row, col] > 9))
{
return false;
}
// if n-th bit is set.. but you can use a bool array for readability
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
// set the n-th bit
flag |= (1 << sudoku[row, col]);
}
}
// Check columns
for(int col= 0; col < 9; col++)
{
flag = 0;
for (int row = 0; row < 9; row++)
{
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
// Check 3x3 boxes
for(int box= 0; box < 9; box++)
{
flag = 0;
for (int ofs = 0; ofs < 9; ofs++)
{
int col = (box % 3) * 3;
int row = ((int)(box / 3)) * 3;
if ((flag & (1 << sudoku[row, col])) != 0)
{
return false;
}
flag |= (1 << sudoku[row, col]);
}
}
return true;
}
于 2008-11-14T10:02:56.753 回答
0
假设您的电路板从 1 - n 开始。
我们将创建一个验证数组，填充它然后验证它。
grid [0-(n-1)][0-(n-1)]; //this is the input grid
//each verification takes n^2 bits, so three verifications gives us 3n^2
boolean VArray (3*n*n) //make sure this is initialized to false
for i = 0 to n
for j = 0 to n
/*
each coordinate consists of three parts
row/col/box start pos, index offset, val offset
*/
//to validate rows
VArray( (0) + (j*n) + (grid[i][j]-1) ) = 1
//to validate cols
VArray( (n*n) + (i*n) + (grid[i][j]-1) ) = 1
//to validate boxes
VArray( (2*n*n) + (3*(floor (i/3)*n)+ floor(j/3)*n) + (grid[i][j]-1) ) = 1
next
next
if every array value is true then the solution is correct.
我认为这可以解决问题，尽管我确信我在那里犯了几个愚蠢的错误。我什至可能完全错过了这条船。
于 2008-11-14T10:45:48.163 回答
0
array = [1,2,3,4,5,6,7,8,9]
sudoku = int [][]
puzzle = 9 #9x9
columns = map []
units = map [] # box
unit_l = 3 # box width/height
check_puzzle()
def strike_numbers(line, line_num, columns, units, unit_l):
count = 0
for n in line:
# check which unit we're in
unit = ceil(n / unit_l) + ceil(line_num / unit_l) # this line is wrong - rushed
if units[unit].contains(n): #is n in unit already?
return columns, units, 1
units[unit].add(n)
if columns[count].contains(n): #is n in column already?
return columns, units, 1
columns[count].add(n)
line.remove(n) #remove num from temp row
return columns, units, line.length # was a number not eliminated?
def check_puzzle(columns, sudoku, puzzle, array, units):
for (i=0;i< puzzle;i++):
columns, units, left_over = strike_numbers(sudoku[i], i, columns, units) # iterate through rows
if (left_over > 0): return false
在没有彻底检查的情况下，在我的脑海中，这应该可以工作（进行一些调试），同时只循环两次。O(n^2) 而不是 O(3(n^2))
于 2008-11-14T12:10:18.353 回答
0
这是数学教授 JF Crook 的论文：A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles
这篇论文发表于 2009 年 4 月，它作为确定的数独解决方案得到了很多宣传（查看谷歌的“JFCrook Sudoku”）。
除了算法之外，还有一个算法有效的数学证明（教授承认他不觉得数独很有趣，所以他在纸上扔了一些数学以使其更有趣）。
于 2009-04-29T12:16:02.717 回答
0
我会编写一个接口，该接口具有接收数独字段并返回真/假（如果它是一个解决方案）的函数。然后将约束实现为每个约束的单个验证类。
要验证只需遍历所有约束类，并且当所有约束类都通过时，数独是正确的。为了加快速度，将最有可能失败的那些放在前面，并在指向无效字段的第一个结果中停止。
很一般的模式。;-)
当然，您可以增强它以提供提示，哪个字段可能是错误的等等。
第一个约束，只需检查所有字段是否都已填写。（简单循环）第二次检查每个块中是否所有数字（嵌套循环）第三次检查完整的行和列（与上面的过程几乎相同，但访问方案不同）
于 2009-04-29T12:29:09.220 回答
0
这是我在 C 中的。每个方格只通过一次。
int checkSudoku(int board[]) {
int i;
int check[13] = { 0 };
for (i = 0; i < 81; i++) {
if (i % 9 == 0) {
check[9] = 0;
if (i % 27 == 0) {
check[10] = 0;
check[11] = 0;
check[12] = 0;
}
}
if (check[i % 9] & (1 << board[i])) {
return 0;
}
check[i % 9] |= (1 << board[i]);
if (check[9] & (1 << board[i])) {
return 0;
}
check[9] |= (1 << board[i]);
if (i % 9 < 3) {
if (check[10] & (1 << board[i])) {
return 0;
}
check[10] |= (1 << board[i]);
} else if (i % 9 < 6) {
if (check[11] & (1 << board[i])) {
return 0;
}
check[11] |= (1 << board[i]);
} else {
if (check[12] & (1 << board[i])) {
return 0;
}
check[12] |= (1 << board[i]);
}
}
}
于 2012-06-15T17:39:18.530 回答
0
这是我刚刚为此所做的：
boolean checkers=true;
String checking="";
if(a.length/3==1){}
else{
for(int l=1; l<a.length/3; l++){
for(int n=0;n<3*l;n++){
for(int lm=1; lm<a[n].length/3; lm++){
for(int m=0;m<3*l;m++){
System.out.print(" "+a[n][m]);
if(a[n][m]<=0){
System.out.print(" (Values must be positive!) ");
}
if(n==0){
if(m!=0){
checking+=", "+a[n][m];
}
else{
checking+=a[n][m];
}
}
else{
checking+=", "+a[n][m];
}
}
}
System.out.print(" "+checking);
System.out.println();
}
}
for (int i=1;i<=a.length*a[1].length;i++){
if(checking.contains(Integer.toString(i))){
}
else{
checkers=false;
}
}
}
checkers=checkCol(a);
if(checking.contains("-")&&!checking.contains("--")){
checkers=false;
}
System.out.println();
if(checkers==true){
System.out.println("This is correct! YAY!");
}
else{
System.out.println("Sorry, it's not right. :-(");
}
}
private static boolean checkCol(int[][]a){
boolean checkers=true;
int[][]col=new int[][]{{0,0,0},{0,0,0},{0,0,0}};
for(int i=0; i<a.length; i++){
for(int j=0; j<a[i].length; j++){
if(a[i][j]>9||a[i][j]<1){
checkers=false;
break;
}
else{
col[a[i].length-j][i]=a[i][j];
}
}
}
String alia="";
for(int i=0; i<col.length; i++){
for(int j=1; j<=col[i].length; j++){
alia=a[i].toString();
if(alia.contains(""+j)){
alia=col[i].toString();
if(alia.contains(""+j)){}
else{
checkers=false;
}
}
else{
checkers=false;
}
}
}
return checkers;
}
于 2013-05-27T23:20:29.287 回答
0
您可以通过以下两种类似的方式检查数独是否已解决：
- 检查数字在每一行、每一列和每一块中是否唯一。
一个天真的解决方案是遍历每个正方形并检查该数字在该数字占用的行、列块中是否唯一。
但是有一个更好的方法。
- 如果每一行、每一列和每一块都包含数字的排列（从 1 到 9），数独就可以解决
这只需要检查每一行、每一列和每一块，而不是对每个数字都这样做。一个简单的实现是有一个数字 1 到 9 的位域，并在迭代列、行和块时删除它们。如果您尝试删除丢失的数字，或者完成后该字段不为空，则数独无法正确解决。
于 2014-04-15T10:45:12.680 回答
0
这是 Swift 中的一个非常简洁的版本，它只使用一个 Ints 数组来跟踪 9 个数字的组，并且只对数独进行一次迭代。
import UIKit
func check(_ sudoku:[[Int]]) -> Bool {
var groups = Array(repeating: 0, count: 27)
for x in 0...8 {
for y in 0...8 {
groups[x] += 1 << sudoku[x][y] // Column (group 0 - 8)
groups[y + 9] += 1 << sudoku[x][y] // Row (group 9 - 17)
groups[(x + y * 9) / 9 + 18] += 1 << sudoku[x][y] // Box (group 18 - 27)
}
}
return groups.filter{ $0 != 1022 }.count == 0
}
let sudoku = [
[7, 5, 1, 8, 4, 3, 9, 2, 6],
[8, 9, 3, 6, 2, 5, 1, 7, 4],
[6, 4, 2, 1, 7, 9, 5, 8, 3],
[4, 2, 5, 3, 1, 6, 7, 9, 8],
[1, 7, 6, 9, 8, 2, 3, 4, 5],
[9, 3, 8, 7, 5, 4, 6, 1, 2],
[3, 6, 4, 2, 9, 7, 8, 5, 1],
[2, 8, 9, 5, 3, 1, 4, 6, 7],
[5, 1, 7, 4, 6, 8, 2, 3, 9]
]
if check(sudoku) {
print("Pass")
} else {
print("Fail")
}
于 2017-09-13T00:09:46.740 回答
0
您可以进行的一个小优化是，您可以在 O(n) 时间而不是 O(n^2) 时间内检查行、列或框中的重复项：当您遍历一组数字时，将每个数字添加到一个哈希集。根据语言的不同，您实际上可能能够使用真正的哈希集，即恒定时间查找和插入；然后通过查看插入是否成功，可以在同一步骤中检查重复项。这是代码的一个小改进，但从 O(n^2) 到 O(n) 是一个重要的优化。
于 2018-12-12T15:38:52.030 回答