¿Un algoritmo genial para comprobar un campo de Sudoku?

Peter Norvig tiene un gran artículo sobre resolver rompecabezas de sudoku (con python),

Http://norvig.com/sudoku.html

Tal vez es demasiado para lo que quieres hacer, pero es una gran lectura de todos modos

Solo un pensamiento: ¿no necesita verificar también los números en cada cuadrado de 3x3?

Estoy tratando de averiguar si es posible tener las condiciones de filas y columnas satisfechas sin tener un sudoku correcto

Marque cada fila, columna y caja de manera que contenga los números 1-9 cada uno, sin duplicados. La mayoría de las respuestas aquí ya discuten esto.

Pero ¿cómo hacerlo eficientemente? Respuesta: Usa un bucle como

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

Cada número establecerá un bit del resultado. Si todos los 9 números son únicos, los 9 más bajos los bits se establece. Por lo tanto, la prueba "comprobar si hay duplicados" es solo una comprobación de que los 9 bits están configurados, que es lo mismo que el resultado de la prueba==511. Tienes que hacer 27 de estos controles.. uno para cada fila, columna y caja.

Cree una matriz de booleanos para cada fila, columna y cuadrado. El índice de la matriz representa el valor que se colocó en esa fila, columna o cuadrado. En otras palabras, si agrega un 5 a la segunda fila, primera columna, establecería filas[2][5] a verdadero, junto con columnas[1][5] y cuadrados[4][5], para indicar que la fila, columna y cuadrado ahora tienen un valor 5.

Independientemente de cómo se represente su tablero original, esta puede ser una manera simple y muy rápida de verificar esto por la exhaustividad y la corrección. Simplemente tome los números en el orden en que aparecen en el tablero y comience a construir esta estructura de datos. A medida que coloca números en el tablero, se convierte en una operación O(1) para determinar si se están duplicando valores en una fila, columna o cuadrado dados. (También querrás comprobar que cada valor es un número legítimo: si te dan un número en blanco o demasiado alto, sabes que el tablero no está completo.) Cuando llegues al final del tablero, usted sabrá que todos los valores son correctos, y no se requiere más comprobación.

Alguien también señaló que se puede utilizar cualquier forma de Conjunto para hacer esto. Las matrices dispuestas de esta manera son solo una forma particularmente liviana y de rendimiento de un Conjunto que funciona bien para un conjunto pequeño, consecutivo y fijo de números. Si sabes el tamaño de tu tabla, también podrías optar por hacer enmascaramiento de bits, pero probablemente sea un poco tedioso teniendo en cuenta que la eficiencia no es tan importante por ti.

Esta es mi solución en Python, me alegra ver que es la más corta hasta ahora:)

El código:

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  

Y la ejecución:

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)        

Cree conjuntos de celdas, donde cada conjunto contiene 9 celdas, y cree conjuntos para columnas verticales, filas horizontales y cuadrados de 3x3.

Luego, para cada celda, simplemente identifique los conjuntos de los que forma parte y analícelos.

Puede extraer todos los valores de un conjunto (fila, columna, caja) en una lista, ordenarlo y luego compararlo con '(1, 2, 3, 4, 5, 6, 7, 8, 9)

Hice esto una vez para un proyecto de clase. Utilicé un total de 27 conjuntos para representar cada fila, columna y caja. Revisaría los números a medida que los agregaba a cada conjunto (cada colocación de un número hace que el número se agregue a 3 conjuntos, una fila, una columna y un cuadro) para asegurarse de que el usuario solo ingresara los dígitos 1-9. La única forma en que un conjunto podría llenarse es si se llenó correctamente con dígitos únicos. Si todos los 27 conjuntos se llenaron, el rompecabezas se resolvió. Configuración de las asignaciones desde la interfaz de usuario para los 27 sets fueron un poco tediosos, pero hicieron que el resto de la lógica fuera muy fácil de implementar.

Si la suma y la multiplicación de una fila/col es igual al número derecho 45/362880

Sería muy interesante comprobar si:

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

Esto basta con las reglas de un sudoku. Porque eso permitiría un algoritmo de O (n^2), sumando y multiplicando las celdas correctas.

Mirando n = 9, las sumas deben ser 45, los productos 362880.

Usted haría algo como:

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;

Hace algún tiempo, escribí un comprobador de sudoku que comprueba el número duplicado en cada fila, el número duplicado en cada columna y el número duplicado en cada caja. Me encantaría si alguien pudiera llegar a uno con como unas pocas líneas de código Linq sin embargo.

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
}

Primero, necesitas hacer un booleano, "correcto". Luego, haga un bucle for, como se indicó anteriormente. El código para el bucle y todo lo posterior (en java) es como se indica, donde field es un array 2D con lados iguales, col es otro con las mismas dimensiones, y l es uno 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];
        }
    }
}

No conozco el algoritmo exacto para marcar las casillas 3x3, pero deberías marcar todas las filas en field y col con "/*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2) " (continúa hasta que alcances la longitud de una fila) dentro de otra para bucle.

Aquí hay un buen enfoque legible en 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))         

Cada cuadrado de 3x3 se conoce como un bloque, y hay 9 de ellos en una cuadrícula de 3x3. Se supone que el rompecabezas se introduce como una lista de lista, con cada lista interna siendo una fila.

Digamos que int sudoku[0..8,0..8] es el campo de sudoku.

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;

}

Supongamos que su tablero va desde 1 - n.

Crearemos una matriz de verificación, la llenaremos y luego la verificaremos.

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. 

Creo que eso hará el truco, aunque estoy seguro de que cometí un par de errores estúpidos allí. Incluso podría haber perdido el barco por completo.

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

Sin revisar a fondo, desde la parte superior de mi cabeza, esto debería funcionar (con un poco de depuración) mientras solo se repite dos veces. O(n^2) en lugar de O(3(n^2))

Aquí está el documento del profesor de matemáticas J. F. Crook: Un Algoritmo de Lápiz y Papel para resolver Rompecabezas de Sudoku

Este artículo fue publicado en abril de 2009 y obtuvo mucha publicidad como solución definitiva de Sudoku (consulte Google para "J. F. Crook Sudoku" ).

Además del algoritmo, también hay una prueba matemática de que el algoritmo funciona (el profesor admitió que no encuentra el Sudoku muy interesante, por lo que lanzó algunas matemáticas en papel para hacerlo más divertido).

Escribiría una interfaz que tiene funciones que reciben el campo sudoku y devuelve true/false si es una solución. A continuación, implemente las restricciones como clases de validación únicas por restricción.

Para verificar simplemente iterar a través de todas las clases de restricción y cuando todos pasan el sudoku es correcto. Para acelerar poner los que más probablemente fallan al frente y detener en el primer resultado que apunta a campo no válido.

Patrón bastante genérico. ;-)

Por supuesto, puede mejorar esto para proporcionar pistas sobre qué campo es presumiblemente incorrecto y así sucesivamente.

Primera restricción, simplemente verifique si todos los campos están completados. (Bucle Simple) Segunda comprobación si todos los números están en cada bloque (bucles anidados) Tercera comprobación de filas y columnas completas (casi el mismo procedimiento que el anterior, pero un esquema de acceso diferente)

Aquí está el mío en C. Solo pase cada cuadrado una vez.

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

Esto es lo que acabo de hacer para esto:

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

Puedes comprobar si el sudoku está resuelto, de estas dos formas similares:

• Compruebe si el número es único en cada fila, columna y bloque.

Una solución ingenua sería iterar a través de cada cuadrado y verificar si el número es único en la fila, bloque de columna que ocupa el número.

Pero hay una mejor manera.

• El sudoku se resuelve si cada fila, columna y bloque contiene una permutación de los números (1 canal 9)

Esto solo requiere compruebe cada fila, columna y bloque, en lugar de hacer eso para cada número. Una implementación simple sería tener un campo de bits de números 1 a través de 9 y eliminarlos cuando se itera las columnas, filas y bloques. Si intenta eliminar un número que falta o si el campo no está vacío cuando termine, sudoku no se resuelve correctamente.

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)

Aquí hay una versión muy concisa en Swift, que solo usa una matriz de Ints para rastrear los grupos de 9 números, y solo itera sobre el sudoku una vez.

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