检查数独字段的很酷的算法？

Question

有谁知道一个简单的算法来检查数独配置是否有效？ 我想出的最简单的算法是（对于大小为 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

但我很确定一定有更好的（在更优雅的意义上）解决方案。 效率其实并不重要。

Answer 1

您可以通过以下两种类似的方式检查数独是否已解决：

• 检查每个行、列和块中的数字是否唯一。

一个简单的解决方案是迭代每个方格，并检查该数字在该数字占据的行、列块中是否唯一。

但还有更好的方法。

• 如果每一行、每一列和每一块都包含数字的排列（1 到 9），那么数独就可以解决

。这只需要检查每一行、每一列和每一块，而不是对每个数字都这样做。 一个简单的实现是使用数字 1 到 9 的位字段，并在迭代列、行和块时删除它们。 如果您尝试删除缺失的数字，或者完成后该字段不为空，则数独无法正确解决。

Answer 2

这是 Swift 中的一个非常简洁的版本，仅使用 Int 数组来跟踪 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")
}

Answer 3

您可以进行的一个小优化是，您可以在 O(n) 时间内而不是 O(n^2) 时间内检查行、列或框中的重复项：当您迭代一组数字时，您可以将每个数字添加到一个哈希集。 根据语言的不同，您实际上可能能够使用真正的哈希集，即恒定时间查找和插入； 然后可以在同一步骤中通过查看插入是否成功来检查重复项。 这是代码中的一个小改进，但从 O(n^2) 到 O(n) 是一个重大的优化。

Answer 4

您需要检查数独的所有约束：

• 检查每行的总和
• 检查每列的总和
• 检查每个框的总和
• 检查每行的重复数字
• 检查每列的重复数字
• 检查每个框的重复数字

总共 6 次检查..使用暴力方法。

如果您知道棋盘的大小（即 3x3 或 9x9），则可以使用某种数学优化

编辑：总和约束的说明：首先检查总和（如果总和不满足则停止） 45）比检查重复项更快（也更简单）。 它提供了一种丢弃错误解决方案的简单方法。

Answer 5

Peter Norvig 有一篇关于解决数独谜题（使用 python）的精彩文章，

https://norvig.com/sudoku.html

也许这对于你想做的事情来说太多了，但无论如何它都是一本很棒的书

Answer 6

检查每一行、每一列和方框，确保其中包含数字 1-9，并且没有重复。 这里的大多数答案已经讨论过这一点。

但如何有效地做到这一点呢？ 循环

result=0;
for each entry:
  result |= 1<<(value-1)
return (result==511);

答案：使用像每个数字都会设置结果的一位的 。 如果所有 9 个数字都是唯一的，则最小的 9
位将被设置。
因此，“检查重复项”测试只是检查所有 9 位是否已设置，这与测试结果==511 相同。
您需要执行其中 27 项检查……每行、每列和每框一项。

Answer 7

想一想：您不需要检查每个 3x3 方格中的数字吗？

我试图弄清楚是否可以在没有正确数独的情况下满足行和列条件

Answer 8

这是我用 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)        

Answer 9

为每一行、每一列和正方形创建一个布尔值数组。 数组的索引表示放入该行、列或正方形的值。 换句话说，如果将 5 添加到第二行第一列，则将 rows[2][5] 设置为 true，同时将 columns[1][5] 和 squares[4][5] 设置为 true，以指示行、列和正方形现在具有 5 值。

无论您的原始董事会如何表示，这都可以是一种简单且非常快速的方法来检查其完整性和正确性。 只需按照数字在板上出现的顺序获取数字，然后开始构建此数据结构即可。 当您将数字放入棋盘中时，确定给定行、列或方格中是否有任何值重复的操作将变成 O(1)。 （您还需要检查每个值是否是合法数字：如果他们给您一个空白或一个太大的数字，您就知道该板不完整。）当您到达板的末尾时，您就会知道所有值都是正确的，并且不需要更多检查。

有人还指出，你可以使用任何形式的 Set 来做到这一点。 以这种方式排列的数组只是一种特别轻量级且高性能的 Set 形式，非常适合小型、连续、固定的数字集。 如果您知道电路板的大小，您也可以选择进行位屏蔽，但考虑到效率对您来说并不是那么重要，这可能有点过于乏味。

Answer 10

创建单元格集合，其中每个集合包含 9 个单元格，并为垂直列、水平行和 3x3 正方形创建集合。

然后，对于每个单元格，只需识别它所属的集合并对其进行分析即可。

Answer 11

您可以将集合（行、列、框）中的所有值提取到列表中，对其进行排序，然后与 '(1, 2, 3, 4, 5, 6, 7, 8, 9) 进行比较

Answer 12

我在一个班级项目中做过一次。 我总共用了 27 组来代表每一行、每一列和每一个方框。 当我将数字添加到每组时，我会检查数字（数字的每次放置都会导致数字被添加到 3 组，一行，一列和一个框），以确保用户只输入数字 1- 9. 填充集合的唯一方法是用唯一的数字正确填充它。 如果 27 组都填满，谜题就解决了。 设置从用户界面到 27 个集合的映射有点乏味，但使其余逻辑的实现变得轻而易举。

Answer 13

将是非常有趣的

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;

Answer 14

前段时间，我编写了一个数独检查器，用于检查每行上的重复数字、每列上的重复数字以及每行上的重复数字。 每个盒子上都有重复的号码。 如果有人能用几行 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
}

Answer 15

如果行/列的乘法和与等于正确的数字 45/362880

Answer 16

首先，您需要创建一个布尔值“正确”。 然后，如前所述，创建一个 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 框，但您应该使用“/*此处为数组名称*/[i].contains(1)&&/*此处为数组名称*/ 检查 field 和 col 中的所有行[i].contains(2)”（一直持续到达到一行的长度）在另一个 for 循环中。

Answer 17

def solution(board):
    for i in board:
        if sum(i) != 45:
            return "Incorrect"

    for i in range(9):
        temp2 = []
        for x in range(9):
            temp2.append(board[i][x])

        if sum(temp2) != 45:
            return "Incorrect"

    return "Correct"

board = []
for i in range(9):
    inp = raw_input()
    temp = [int(i) for i in inp]
    board.append(temp)

print solution(board)

Answer 18

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 的正方形称为一个块，3x3 的网格中有 9 个块。 假设谜题作为列表的列表输入，每个内部列表都是一行。

Answer 19

假设 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;

}

Answer 20

假设您的棋盘是从 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. 

我认为这会成功，尽管我确信我在那里犯了一些愚蠢的错误。 我什至可能完全错过了这趟船。

Answer 21

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))

Answer 22

以下是数学教授 JF Crook 的论文：解决数独谜题的纸笔算法

这篇论文发表于 2009 年 4 月，作为确定的数独解决方案得到了广泛的宣传（在 google 上查找“JFCrook Sudoku”）。

除了算法之外，还有算法有效的数学证明（教授承认他觉得数独不是很有趣，所以他在纸上扔了一些数学以使其更有趣）。

Answer 23

我会编写一个接口，其中包含接收数独字段的函数，并在它是解决方案时返回 true/false。
然后将约束实现为每个约束的单个验证类。

要验证，只需迭代所有约束类，当所有约束类都通过时，数独是正确的。 为了加速，将最有可能失败的结果放在前面，并停止在指向无效字段的第一个结果中。

非常通用的模式。 ;-)

您当然可以增强它以提供哪个字段可能是错误的提示等等。

第一个约束，只需检查所有字段是否已填写。 （简单循环）
第二次检查每个块中是否有所有数字（嵌套循环）
第三次检查完整的行和列（与上面的过程几乎相同，但访问方案不同）

Answer 24

这是我在 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]);
    }
  }
}

Answer 25

这是我刚刚为此所做的：

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;
}