Crear una solución de Sudoku CHEQUEADOR
Aquí hay montones de SOLDADORES de Sudoku, pero quiero que crees una solución CHECKER tan pequeña como sea humanamente posible (code-golf).
Una entrada válida podrá tomar una matriz de 9x9 como argumento (pasado por referencia, serializado en la línea de comando, o como quiera tomarlo) o aceptar un archivo de entrada que tenga nueve líneas de nueve números para la grilla final . Ver ejemplos de entrada a continuación.
La entrada válida debe ser números de base 10 (1-9)
Las posiciones faltantes, vacías, extra, no numéricas, o las posiciones con números fuera del 1-9 deben rechazarse como una entrada no válida al devolver un resultado distinto de cero, imprimir un error o ambos.
Su programa necesita probar si cada número aparece una vez por columna, una vez por línea y una vez por cada subcuadrícula 3x3. Si pasa, devuelve "0" y si no, devuelve un resultado distinto de cero.
Se debe evitar el uso de recursos externos (sitios web, etc.).
Si su solución es un programa independiente, salir con un estado de salida o imprimir "0" o distinto de cero para "Pasar" o "Fallar", respectivamente, está bien.
¡Que gane la respuesta más pequeña!
Ejemplos de entrada:
matriz c:
int input[9][9]={{1,2,3,4,5,6,7,8,9},
{4,5,6,7,8,9,1,2,3},
{7,8,9,1,2,3,4,5,6},
{2,3,1,5,6,4,8,9,7},
{5,6,4,8,9,7,2,3,1},
{8,9,7,2,3,1,5,6,4},
{3,1,2,6,4,5,9,7,8},
{6,4,5,9,7,8,3,1,2},
{9,7,8,3,1,2,6,4,5}
};
archivo:
123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645
Las 9 subrejillas:
+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+
fuente
1
o-1
Python, 103
Odio el sudoku.
Cómo funciona: cada fila, columna y bloque debe tener cada número del 1 al 9. Entonces, para cada
0 <= i, j < 9
celda, la celdai,j
está en bloque3*floor(i/3) + floor(j/3)
. Por lo tanto, hay 243 requisitos para satisfacer. Hago que cada requisito sea una tupla((item index,item type number),symbol)
dondeitem index
hay un número entre 0 y 8 (inclusive),item type number
es 0,1 o 2 para denotar fila, columna o bloque, respectivamente, ysymbol
es la entradab[i][j]
.Editar: por error no verifiqué las entradas válidas. Ahora lo hago.
fuente
0
si la solución pasa, noTrue
APL (46)
Esto toma una matriz de 9 por 9. El ejemplo uno se puede ingresar en TryAPL así:
Explicación:
↓⍉⍵
: obtener las columnas de⍵
,↓⍵
: obtener las filas de⍵
,3/3⌿3 3⍴Z←⍳9
: haga una matriz de 3 por 3 que contenga los números1
para9
, luego triplique cada número en ambas direcciones, dando una matriz de 9 por 9 con los números1
para9
indicar cada grupo,Z∘.=
: Para cada número1
a9
, hacer una máscara de bits para el grupo dado,/∘(,⍵)¨
: y enmascarar⍵
con cada uno, dando los grupos de⍵
.∊∘Z¨
: para cada submatriz, vea si contiene los números1
para9
,∧/,↑
: tome la lógicaand
de todos estos números juntos.fuente
↓9 9⍴1 3 2⍉3 3 9⍴⍵
es equivalente/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9
pero bastante más corto. Estoy seguro de que hay fórmulas aún más cortas.⍪
y realizar una sola división al final:↓(9 9⍴1 3 2⍉3 3 9⍴⍵)⍪⍵⍪⍉⍵
∊∘Z¨
está probando si cada sub-matriz (fila, columna o bloque) solo está hecha de los números 1 a 9. No está probando si todos los números están representados. Debe hacer algo comoZ∘.∊
qué pruebas de que cada número en Z está contenido en cada sub-matriz.∧/,↑
se puede acortar a∧/∊
. ¡Ya terminé, ya terminé! ;-)If it passes, return "0" and if not, return a non-zero result.
Java / C # -
183/180181/178173/170 bytes(Cambiar
boolean
abool
para C #)Formateado:
El método crea una matriz
u
con 27 máscaras de bits, que representan los dígitos encontrados en las nueve filas, columnas y cuadrados.Luego itera sobre todas las celdas, realizando la operación
1 << a[x][y]
para crear una máscara de bits que representa el dígito y OR con su columna, fila y máscara de bits cuadrada.Luego itera sobre las 27 máscaras de bits, asegurando que todas sumen 27594 (1022 * 9, 1022 es la máscara de bits para todos los dígitos 1-9 presentes). (Tenga en cuenta que
y
termina como 27603 debido a que ya contiene 9 después del doble bucle).Editar: accidentalmente dejado en un
%3
que ya no es necesario.Edición 2: inspirado en el comentario de Bryce Wagner, el código se ha comprimido un poco más.
fuente
pitón = 196
No es el más golfista, pero la idea está ahí. Los sets son bastante útiles.
Tablero:
Programa:
fuente
n={*range(1,10)}
, pero eso es más nuevo que el desafío. En su lugar, useset(range(1,10))
como dijo MatrixFrog.Java:
385306328252caracteresEditar: tontamente leí mal las instrucciones de que la respuesta tenía que ser un programa completo. Como puede ser solo una función válida, he reescrito y minimizado para ser una función, y reescribí la introducción de mi solución con eso en mente.
Entonces, como un desafío para mí, pensé que intentaría hacer el verificador de soluciones Java más pequeño.
Para lograr esto, supongo que el rompecabezas sudoku se pasará como una matriz multidimensional de Java, de esta manera:
Luego, tenemos el solucionador real, que devuelve "0" si la solución es válida, "1" si no.
Completamente golfizado:
Legible:
Entonces, ¿cómo funciona esto? Básicamente, creo mi propia base de números con una resolución suficiente en cada dígito que solo tengo que hacer tres comparaciones numéricas después de pasar por el rompecabezas una vez para saber si es válido. Elegí la base 49 para este problema, pero cualquier base mayor que 45 sería suficiente.
Un ejemplo (con suerte) claro: imagine que cada "fila" en el rompecabezas de sudoku es un solo dígito en un número de base 49. Representaremos cada dígito en el número de base 49 como un número de base 10 en un vector por simplicidad. Entonces, si todas las filas son "correctas", esperamos el siguiente número de base 49 (como un vector de base 10):
o convertido a un solo número de base 10:
1526637748041045
Siga una lógica similar para todas las columnas, y lo mismo para las "sub-cuadrículas". Cualquier valor encontrado en el análisis final que no sea igual a este "número ideal" significa que la solución del rompecabezas no es válida.
Edite para resolver la vulnerabilidad de todos los 5 y otros problemas relacionados: agrego un cuarto número de base 49, basado en la idea de que debería haber 9 de cada número en cada rompecabezas. Entonces, agrego 5 a cada dígito en el número de base 49 para cada aparición del número de base 10 que representa el índice del dígito. Un ejemplo, si hay 10 9 y 9 8, 9 7, 8 6 y 9 de todos los demás, obtendría un número de base 49 (como un vector de base 10 de tamaño 10 para tratar el desbordamiento):
Lo cual fallará en comparación con nuestro número "ideal" de base 49.
Mi solución aprovecha esta solución matemática para evitar la mayor cantidad posible de bucles y comparación. Simplemente uso un
long
valor para almacenar cada número de base 49 como un número de base 10 y utilizo una matriz de búsqueda para obtener los "factores" para cada dígito de base 49 durante el cálculo del valor de verificación de columna / fila / subcuadrícula.Como Java no está diseñado para ser conciso, tener cuidado en la construcción matemática fue la única forma en que pensé que podría construir un corrector conciso.
Déjame saber lo que piensas.
fuente
R 145
El código de golf (más o menos) se puede encontrar aquí /programming//a/21691541/1201032 .
fuente
Haskell (Lambdabot), 65 bytes
fuente
Perl, 193 bytes
La entrada se espera en forma de matriz:
El código de salida es 0, si
@a
es una solución, de lo contrario1
se devuelve.Versión sin golf:
Cada una de las 9 filas, 9 columnas y 9 sub matrices se colocan en una matriz ordenada y se comprueba si coincide con la matriz
(1..9)
. El número$r
se incrementa para cada coincidencia exitosa que debe sumar hasta 27 para una solución válida.fuente
J
5254Toma su argumento pegado en la línea de comando, terminó con a) como:
Devuelve 1 si se pasa, 0 si no.
Internamente, convierte la cuadrícula de 9x9 en una cuadrícula de 3x3x3x3 y realiza algunas permutaciones en los ejes para obtener la unidad deseada (filas, líneas y cuadros) en las últimas 2 dimensiones.
Después de hacer eso, se verifica que cada unidad tenga 9 valores únicos.
Probablemente lejos de ser perfecto, pero ya supera a la mayoría ;-)
fuente
Mathematica,
8479 caracteresEjemplos:
fuente
3
siempre indicativo de una entrada inválida, o es a veces una respuesta a una solución fallida?Javascript ES6, 150 caracteres
Toma la entrada como una cadena de 81 caracteres sin delimitadores.
La función regresa
null
como respuesta negativa y una matriz con una cadena original en el primer elemento como positiva. Puede cambiar a bool agregando!!
a la función de inicio.Prueba (ver desafío relacionado para más detalles):
fuente
R,
6350 bytesAsume que la entrada
m
es una matriz de números 9x9.Tenía razón en que era posible seguir jugando al golf.
Explicación:
Tome
m
, y para cada fila, aplique lamatch
función. Especificamos un argumento adicionalx=1:9
para pasarmatch
.x
es el argumento predeterminado de la primera posición y, por lo tanto, cada fila se coloca en la segunda posición del argumento, que estable
. La funciónmatch
busca instancias dex
intable
. En este caso, entonces, está buscando1:9
(los números del 1 al 9) en cada fila. Para cada uno1:9
, devolveráTRUE
(oFALSE
) si se encuentra ese número (o no).Entonces, esto produce una serie de 81 valores booleanos.
Repita lo anterior para cada columna de la entrada.
Finalmente,
all
verifica si cada elemento de la lista de booleanos esTRUE
. Este será el caso si y solo si la solución es correcta (es decir, cada número1:9
está presente solo una vez en cada columna y cada fila).Viejo enfoque:Toma cada fila, la ordena y luego la compara[1, 2, ... 9]
. Una fila correcta debe coincidir exactamente. Luego hace lo mismo para cada columna. En total, deberíamos tener 162 coincidencias exactas, que es lo que verifica la parte final. Es probable que haya algún margen para seguir jugando al golf aquí ...fuente
Haskell - 175
La función
v
es la que hay que llamar. Funciona obteniendo la diferencia de cada fila, columna y bloque contra la lista[1..9]
y sumando las longitudes de esas listas de diferencias.Demo usando el ejemplo Sudoku:
fuente
Javascript - 149 caracteres
Espera
a
que exista una matriz y crea una variableo
para la salida que tiene0
éxito y, de lo contrario, no es cero.Funciona comprobando que la suma de la posición en la que se produce cada valor para cada fila, columna y cuadrícula 3 * 3 es igual a 36 (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8).
Pruebas
Da 'o = 0'
(Últimos 2 dígitos intercambiados)
Da
o=-1
Da
o=-284
fuente
Haskell,
121130127 bytes (87 Lambdabot)usos:
Lambdabot carga Data.List y Data.List.Split de forma predeterminada (no creo que la solución de BlackCap marque las casillas).
Ideas de mejora bienvenidas
// Editar: me equivoqué :)
// Editar: 3 bytes guardados por BlackCap
fuente
(map sort)
con(sort<$>)
.c$(sort<$>)<$>
con$(sort<$>)=<<
05AB1E , 36 bytes | No N-Competir |
Pruébalo en línea!
1 es cierto, cualquier otra cosa es falsa.
fuente
Clojure, 151 bytes
Bastante largo, pero otros parecen serlo también. También es molesto que la unión de conjuntos requiera un
require
, así que usé un concat de vectores en su lugar.Itera sobre cada fila y columna y si el valor está entre 1 y 9, emite tres vectores, uno para fila, col y celda 3x3. Devuelve 0 en caso de éxito y
nil
, de lo contrario, con dos caracteres adicionales podría devolver 1 en caso de error. Maneja los números fuera del 1 al 9 al regresar,nil
pero se bloqueará en otras anomalías, como los valores no enteros. Los cocientes son 0 - 2, por lo que es seguro usar valores8
y9
diferenciar los valores de celda de filas y columnas.La entrada es un vector anidado de vectores (para que
nth
funcione):Sin golf:
fuente
PHP,
196190 bytesEl programa toma 9 argumentos de línea de comando separados (una cadena de dígitos para cada línea de la cuadrícula);
sale con
1
(error) para inválido,0
(ok) para válido.Corre con
php -nr '<code>' <row1> <row2> ...
.Descompostura
explicación
count_chars
cuenta los caracteres en una cadena y generalmente crea una matriz con códigos ascii como claves y los caracteres cuentan como valores; pero con3
como parámetro de modo, crea una cadena ordenada a partir de los caracteres; y eso se puede comparar fácilmente con el número con los dígitos deseados.La comparación no solo busca duplicados, sino que también incluye la verificación de caracteres no válidos. Y solo requiere
<
, no!=
, porque esta es una comparación numérica: PHP interpretará la cadena como un número en la medida de lo posible.123e56789
,0x3456789
o similar no puede aparecer, porque los caracteres están ordenados; y cualquier entero puro con un dígito faltante es más pequeño que123456789
... y.23456789
también, por supuesto.$a=$argv
ahorra un byte,$d=123456789
salva nueve y$u=count_chars
salva 13.fuente
C # -
306298288 caracteresEl siguiente programa de consola se usó para llamar a la función de verificación;
Todo lo que hace es inicializar la matriz y pasarla a la función de verificación P.
La función de verificación es la siguiente (en forma de Golf);
O en forma completamente establecida;
Esto utiliza la idea de que todas las columnas, filas y subcuadrículas deben sumar 45. Funciona a través de la matriz de entrada y resta el valor de cada posición de su fila, columna y subcuadrícula. Una vez completado, verifica que ninguna de las filas, columnas o subcuadrículas aún tenga un valor.
Según lo solicitado, devuelve un 0 si la matriz es una solución de Sudoku válida y no es cero (1) donde no lo es.
fuente
private static int P(int[,]i){int[]r=new int[9],c=new int[9],g=new int[9];
lugar. (Tenga en cuenta la eliminación del espacio después del corchete cerrado]
). Además, no estoy seguro, pero creo que puede deshacerse de élprivate static
.for(int p=0;p<9;p++)if(r[p]>0|c[p]>0|g[p]>0)return 1;return 0;}
, es decir , no estoy seguro si funciona en C #. (En realidad no sé C #)