algorithm - tips - ¿Un algoritmo genial para verificar un campo de Sudoku?
tips sudoku (25)
¿Alguien sabe un algoritmo simple para verificar si una Sudoku-Configuración es válida? El algoritmo más simple que se me ocurrió es (para una placa de tamaño n) en Pseudocódigo
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
Pero estoy bastante seguro de que debe haber una mejor solución (en el sentido de más elegante). La eficiencia no tiene importancia.
Atentamente,
Miguel
Esta es mi solución en Python, me alegra ver que es la más corta hasta el momento :)
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.
Digamos que sudoku int [0..8.0..8] es el campo 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;
}
Peter Norvig tiene un gran artículo sobre cómo resolver acertijos sudoku (con python),
Tal vez es demasiado para lo que quieres hacer, pero de todos modos es una gran lectura
Puede extraer todos los valores de un conjunto (fila, columna, recuadro) en una lista, ordenarlos y luego compararlos con ''(1, 2, 3, 4, 5, 6, 7, 8, 9)
Sería muy interesante verificar 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 es suficiente con las reglas de un sudoku. Porque eso permitiría un algoritmo de O (n ^ 2), sumando y multiplicando las celdas correctas.
En cuanto a n = 9, las sumas deben ser 45, los productos 362880.
Harías 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;
Solo un pensamiento: ¿no es necesario que también verifique los números en cada cuadrado de 3x3?
Estoy tratando de averiguar si es posible tener satisfechas las condiciones de filas y columnas sin tener un sudoku correcto
Supongamos que su tablero va de 1 - n.
Crearemos un conjunto de verificación, lo completaremos y luego lo 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 hará el truco, aunque estoy seguro de que cometí un par de errores estúpidos allí. Incluso podría haber perdido el bote 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 completamente, fuera de mi cabeza, esto debería funcionar (con un poco de depuración) mientras solo buclea dos veces. O (n ^ 2) en lugar de O (3 (n ^ 2))
Hice esto una vez para un proyecto de clase. Usé un total de 27 juegos para representar cada fila, columna y caja. Comprobaba los números cuando los añadí a cada conjunto (cada ubicació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 ingresó los dígitos 1. 9. La única forma de que un conjunto se complete es si se llenó correctamente con dígitos únicos. Si se llenaron los 27 sets, el acertijo fue resuelto. Configurar las asignaciones desde la interfaz de usuario a los 27 sets fue un poco tedioso, pero hizo que el resto de la lógica fuera fácil de implementar.
Aquí está el artículo del profesor de matemáticas JF Crook: un algoritmo de lápiz y papel para resolver acertijos de sudoku
Este documento fue publicado en abril de 2009 y recibió mucha publicidad como solución definitiva de Sudoku (consulte google para "JFCrook 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, así que arrojó algunas matemáticas en papel para hacerlo más divertido).
Compruebe cada fila, columna y cuadro de manera que contenga los números del 1 al 9, sin duplicados. La mayoría de las respuestas aquí ya hablan de esto.
Pero, ¿cómo hacer eso de manera eficiente? Respuesta: Use un bucle como
result=0;
for each entry:
result |= 1<<(value-1)
return (result==511);
Cada número establecerá un bit del resultado. Si los 9 números son únicos, se establecerán los 9 bits más bajos. Entonces, la prueba de "verificar duplicados" es solo una comprobación de que se han establecido los 9 bits, que es lo mismo que el resultado de la prueba == 511. Debe hacer 27 de estos controles ... uno por cada fila, columna y casillero.
Escribiría una interfaz que tiene funciones que reciben el campo sudoku y devuelve verdadero / falso si es una solución. Luego implemente las restricciones como clases de validación individuales por restricción.
Para verificar simplemente iterar a través de todas las clases de restricciones y cuando todas pasan el sudoku es correcto. Para acelerar, coloque los que probablemente fallan al frente y deténgalos en el primer resultado que apunte al 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 completos. (Bucle simple) En segundo lugar, compruebe si todos los números están en cada bloque (bucles anidados) Tercer control de filas y columnas completas (casi el mismo procedimiento que el anterior pero diferente esquema de acceso)
Hace algún tiempo, escribí un comprobador de sudoku que busca un número duplicado en cada fila, un número duplicado en cada columna y un número duplicado en cada casilla. Sin embargo, me encantaría que alguien apareciera con algunas líneas de código 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
}
Si necesita un solucionador, también, puede encontrar un algoritmo "genial" (en 3 líneas) aquí:
http://www.ecclestoad.co.uk/blog/2005/06/02/sudoku_solver_in_three_lines_explained.html
Crea 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 las filas [2] [5] en verdadero, junto con las columnas [1] [5] y los cuadrados [4] [5], para indicar que la fila, la columna y el cuadrado ahora tienen un valor de 5 .
Independientemente de cómo se represente a su junta original, esta puede ser una manera simple y muy rápida de verificar que esté completa y correcta. Simplemente tome los números en el orden en que aparecen en la pizarra 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 los valores en una fila, columna o casilla determinada. (También querrá verificar que cada valor sea un número legítimo: si le dan un número en blanco o un número demasiado alto, sabe que el tablero no está completo.) Cuando llega al final del tablero, Sabrá que todos los valores son correctos y no se requiere más verificación.
Alguien también señaló que puede usar cualquier forma de Set para hacer esto. Las matrices dispuestas de esta manera son solo una forma particularmente ligera y de rendimiento de un conjunto que funciona bien para un pequeño conjunto de números fijo y consecutivo. Si conoce el tamaño de su tablero, también puede optar por hacer enmascaramiento de bits, pero eso es probablemente demasiado tedioso, considerando que la eficiencia no es tan importante para usted.
si la suma y la multiplicación de una fila / col es igual al número correcto 45/362880
Necesitas verificar todas las restricciones de Sudoku:
- verifica la suma en cada fila
- verifique la suma en cada columna
- verificar la suma en cada caja
- verifique si hay números duplicados en cada fila
- verificar los números duplicados en cada columna
- verificar los números duplicados en cada caja
eso 6 cheques en total ... usando un enfoque de fuerza bruta. Algún tipo de optimización matemática se puede usar si conoce el tamaño de la placa (es decir, 3x3 o 9x9)
Editar : explicación de la restricción de suma: Verificar primero la suma (y detener si la suma no es 45) es mucho más rápido (y más simple) que buscar duplicados. Proporciona una manera fácil de descartar una solución incorrecta.
Aquí está el mío en C. Solo pasa una plaza 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;
}
Primero, necesitarías hacer un booleano, "correcto". Luego, haz un ciclo for, como se dijo previamente. El código para el ciclo y todo después (en java) es como se indicó, donde campo es un conjunto 2D con lados iguales, col es otro con las mismas dimensiones, y l es un 1D uno:
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 verificar las casillas de 3x3, pero debes verificar todas las filas en el campo y col con " /*array name goes here*/[i].contains(1)&&/*array name goes here*/[i].contains(2) "(continúa hasta llegar a la longitud de una fila) dentro de otro ciclo for .
Puedes verificar 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 ese número.
Pero hay una mejor manera.
- Sudoku se resuelve si cada fila, columna y bloque contiene una permutación de los números (1 a 9)
Esto solo requiere verificar 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 los números 1 a 9 y eliminarlos cuando itere las columnas, filas y bloques. Si intentas eliminar un número faltante o si el campo no está vacío cuando terminas, sudoku no está resuelto 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 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 asume que el rompecabezas se ingresa como una lista de listas, con cada lista interna como una fila.
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")
}