一个很酷的算法来检查数独场？

Does anyone know a simple algorithm to check if a Sudoku-Configuration is valid? The simplest algorithm I came up with is (for a board of size n) in Pseudocode

有谁知道一个简单的算法来检查数独配置是否有效?我提出的最简单的算法是(对于一个大小为n的板)Pseudocode

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

But I'm quite sure there must be a better (in the sense of more elegant) solution. Efficiency is quite unimportant.

但我确信必须有更好的(更优雅的)解决方案。效率非常不重要。

Best Regards,

Michael

24 个解决方案

#1

You need to check for all the constraints of Sudoku :

您需要检查Sudoku的所有约束:

• check the sum on each row

检查每一行的总和

• check the sum on each column

检查每列的总和

• check for sum on each box

检查每个盒子的总和

• check for duplicate numbers on each row

检查每行的重复数字

• check for duplicate numbers on each column

检查每列上的重复数字

• check for duplicate numbers on each box

检查每个盒子上的重复数字

that't 6 checks altogether.. using a brute force approach. Some sort of mathematical optimization can be used if you know the size of the board (ie 3x3 or 9x9)

那不是6次检查......使用蛮力方法。如果您知道电路板的尺寸(即3x3或9x9),可以使用某种数学优化

Edit: explanation for the sum constraint: Checking for the sum first (and stoping if the sum is not 45) is much faster (and simpler) than checking for duplicates.It provides an easy way of discarding a wrong solution.

编辑:和约束的解释:首先检查总和(并且如果总和不是45则停止)比检查重复更快(和更简单)。它提供了一种丢弃错误解决方案的简单方法。

#2

Peter Norvig has a great article on solving sudoku puzzles (with python),

Peter Norvig有一篇关于解决数独难题的精彩文章(使用python),

http://norvig.com/sudoku.html

Maybe it's too much for what you want to do, but it's a great read anyway

也许这对你想要做的事情来说太过分了,但无论如何这都是一个很好的阅读

#3

Just a thought: don't you need to also check the numbers in each 3x3 square?

只是一个想法:你不需要检查每个3x3平方的数字吗?

I'm trying to figure out if it is possible to have the rows and columns conditions satisfied without having a correct sudoku

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

#4

Check each row, column and box such that it contains the numbers 1-9 each, with no duplicates. Most answers here already discuss this.

检查每一行,每列和每个框,使其包含数字1-9,不重复。这里的大多数答案已经讨论过了

But how to do that efficiently? Answer: Use a loop like

但如何有效地做到这一点?答:使用类似的循环

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

Each number will set one bit of the result. If all 9 numbers are unique, the lowest 9 bits will be set. So the "check for duplicates" test is just a check that all 9 bits are set, which is the same as testing result==511. You need to do 27 of these checks.. one for each row, column, and box.

每个数字将设置结果的一位。如果所有9个数字都是唯一的,则将设置最低的9位。所以“检查重复”测试只是检查所有9位是否设置,这与测试结果== 511相同。您需要执行其中的27项检查。每行,每列和每行一项。

#5

Create an array of booleans for every row, column, and square. The array's index represents the value that got placed into that row, column, or square. In other words, if you add a 5 to the second row, first column, you would set rows[2][5] to true, along with columns[1][5] and squares[4][5], to indicate that the row, column, and square now have a 5 value.

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

Regardless of how your original board is being represented, this can be a simple and very fast way to check it for completeness and correctness. Simply take the numbers in the order that they appear on the board, and begin building this data structure. As you place numbers in the board, it becomes a O(1) operation to determine whether any values are being duplicated in a given row, column, or square. (You'll also want to check that each value is a legitimate number: if they give you a blank or a too-high number, you know that the board is not complete.) When you get to the end of the board, you'll know that all the values are correct, and there is no more checking required.

无论您的原始电路板如何表示,这都是一种简单而快速的方法来检查它的完整性和正确性。只需按照它们在电路板上显示的顺序排列,然后开始构建此数据结构。当您在数字板中放置数字时,它将成为O(1)操作,以确定是否在给定的行,列或方形中复制任何值。 (您还需要检查每个值是否为合法数字:如果它们给您一个空白或太高的数字,您就知道该板未完成。)当您到达板的末尾时,会知道所有的值都是正确的,并且不再需要检查。

Someone also pointed out that you can use any form of Set to do this. Arrays arranged in this manner are just a particularly lightweight and performant form of a Set that works well for a small, consecutive, fixed set of numbers. If you know the size of your board, you could also choose to do bit-masking, but that's probably a little overly tedious considering that efficiency isn't that big a deal to you.

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

#6

This is my solution in Python, I'm glad to see it's the shortest one yet :)

这是我在Python中的解决方案,我很高兴看到它是最短的:)

The code:

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  

And the execution:

并执行:

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)        

#7

Create cell sets, where each set contains 9 cells, and create sets for vertical columns, horizontal rows, and 3x3 squares.

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

Then for each cell, simply identify the sets it's part of and analyze those.

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

#8

You could extract all values in a set (row, column, box) into a list, sort it, then compare to '(1, 2, 3, 4, 5, 6, 7, 8, 9)

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

#9

I did this once for a class project. I used a total of 27 sets to represent each row, column and box. I'd check the numbers as I added them to each set (each placement of a number causes the number to be added to 3 sets, a row, a column, and a box) to make sure the user only entered the digits 1-9. The only way a set could get filled is if it was properly filled with unique digits. If all 27 sets got filled, the puzzle was solved. Setting up the mappings from the user interface to the 27 sets was a bit tedious, but made the rest of the logic a breeze to implement.

我曾经为一个课程项目做了一次。我总共用了27套来代表每一行,一列和一行。我检查了数字,因为我将它们添加到每个集合中(每个数字的位置导致数字被添加到3组,一行,一列和一个框)以确保用户只输入数字1- 9。集合可以填充的唯一方法是它是否正确填充了唯一的数字。如果所有27套都被填满,拼图就解决了。设置从用户界面到27集的映射有点单调乏味,但使其余的逻辑变得轻而易举。

#10

if the sum and the multiplication of a row/col equals to the right number 45/362880

如果行/ col的总和乘以等于正确的数字45/362880

#11

It would be very interesting to check if:

检查是否:

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

this suffices the rules of a sudoku. Because that would allow for an algorithm of O(n^2), summing and multiplying the correct cells.

这足以满足数独的规则。因为这将允许O(n ^ 2)的算法,对正确的单元进行求和和相乘。

Looking at n = 9, the sums should be 45, the products 362880.

看n = 9,总和应为45,产品为362880。

You would do something like:

你会做的事情如下:

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;

#12

Some time ago, I wrote a sudoku checker that checks for duplicate number on each row, duplicate number on each column & duplicate number on each box. I would love it if someone could come up one with like a few lines of Linq code though.

前段时间,我写了一个数独检查器,检查每行上的重复数字,每列上的重复数字和每个框上的重复数字。如果有人可以用几行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
}

#13

First, you would need to make a boolean, "correct". Then, make a for loop, as previously stated. The code for the loop and everything afterwards (in java) is as stated, where field is a 2D array with equal sides, col is another one with the same dimensions, and l is a 1D one:

首先,你需要做一个布尔值,“正确”。然后,如前所述,进行for循环。循环的代码和之后的所有内容(在java中)如前所述,其中field是具有相等边的2D数组,col是具有相同尺寸的另一个,l是1D的:

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

I don't know the exact algorithim to check the 3x3 boxes, but you should check all the rows in field and col with "/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2)" (continues until you reach the length of a row) inside another for loop.

我不知道检查3x3盒子的确切算法,但你应该检查字段和col中的所有行“/ *数组名称在这里* / [i] .contains(1)&& / *数组名称在这里* / [i] .contains(2)“(继续到达一行的长度)在另一个for循环中。

#14

Here's a nice readable approach in Python:

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

Each 3x3 square is referred to as a block, and there are 9 of them in a 3x3 grid. It is assumed as the puzzle is input as a list of list, with each inner list being a row.

每个3x3方块称为块,其中9个在3x3网格中。假设拼图是作为列表列表输入的,每个内部列表是一行。

#15

Let's say int sudoku[0..8,0..8] is the sudoku field.

让我们说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;

}

#16

Let's assume that your board goes from 1 - n.

我们假设您的电路板从1 - n开始。

We'll create a verification array, fill it and then verify it.

我们将创建一个验证阵列,填充它然后验证它。

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. 

I think that will do the trick, although i'm sure i made a couple of stupid mistakes in there. I might even have missed the boat entirely.

我认为这样做会有所作为,虽然我确信我在那里犯了几个愚蠢的错误。我甚至可能完全错过了这条船。

#17

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

Without thoroughly checking, off the top of my head, this should work (with a bit of debugging) while only looping twice. O(n^2) instead of O(3(n^2))

如果没有彻底检查,那么这应该可以工作(通过一些调试),而只能循环两次。 O(n ^ 2)代替O(3(n ^ 2))

#18

Here is paper by math professor J.F. Crook: A Pencil-and-Paper Algorithm for Solving Sudoku Puzzles

以下是数学教授J.F. Crook撰写的论文:用于解决数独谜题的铅笔纸算法

This paper was published in April 2009 and it got lots of publicity as definite Sudoku solution (check google for "J.F.Crook Sudoku" ).

本文发表于2009年4月,它作为明确的数独解决方案获得了大量的宣传(请查看Google的“J.F.Crook Sudoku”)。

Besides algorithm, there is also a mathematical proof that algorithm works (professor admitted that he does not find Sudoku very interesting, so he threw some math in paper to make it more fun).

除了算法之外,还有一个算法有效的数学证明(教授承认他没有发现数独非常有趣,所以他把一些数学写在纸上以使其更有趣)。

#19

I'd write an interface that has functions that receive the sudoku field and returns true/false if it's a solution. Then implement the constraints as single validation classes per constraint.

我编写了一个接口,它具有接收数独字段的函数,如果它是一个解决方案,则返回true / false。然后将约束实现为每个约束的单个验证类。

To verify just iterate through all constraint classes and when all pass the sudoku is correct. To speedup put the ones that most likely fail to the front and stop in the first result that points to invalid field.

验证只是迭代所有约束类,并且当所有传递数据时都是正确的。加速将最有可能失败的那些放在前面并在第一个结果中停止指向无效字段。

Pretty generic pattern. ;-)

非常通用的模式。 ;-)

You can of course enhance this to provide hints which field is presumably wrong and so on.

您当然可以对此进行增强,以提供哪些字段可能是错误的提示等等。

First constraint, just check if all fields are filled out. (Simple loop) Second check if all numbers are in each block (nested loops) Third check for complete rows and columns (almost same procedure as above but different access scheme)

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

#20

Here is mine in C. Only pass each square once.

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

#21

Here is what I just did for this:

这就是我刚刚为此做的事情:

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

#22

You can check if sudoku is solved, in these two similar ways:

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

• Check if the number is unique in each row, column and block.

检查每行,每列和每个块的编号是否唯一。

A naive solution would be to iterate trough every square and check if the number is unique in the row, column block that number occupies.

一个天真的解决方案是迭代每个方块并检查该数字在该行中的唯一性,该数字占据的列块。

But there is a better way.

但还有更好的方法。

• Sudoku is solved if every row, column and block contains a permutation of the numbers (1 trough 9)

如果每个行,列和块都包含数字的排列(1槽9),则解决数独

This only requires to check every row, column and block, instead of doing that for every number. A simple implementation would be to have a bitfield of numbers 1 trough 9 and remove them when you iterate the columns, rows and blocks. If you try to remove a missing number or if the field isn't empty when you finish then sudoku isn't correctly solved.

这只需要检查每一行,每列和每个数字,而不是每个数字。一个简单的实现是将数字1的位域设置为9到9,并在迭代列,行和块时将其删除。如果您尝试删除丢失的数字,或者当您完成时该字段不为空,则数据未正确解决。

#23

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)

#24

Here's a very concise version in Swift, that only uses an array of Ints to track the groups of 9 numbers, and only iterates over the sudoku once.

这是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")
}