Implemente el solucionador de Sudoku más corto usando adivinanzas. Como he recibido algunas solicitudes, he agregado esto como una pregunta alternativa para aquellos que desean implementar un solucionador de sudoku de fuerza bruta.
Sudoku Puzzle:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 3 | 1 |
B| 6 | | 5
C| 5 | | 9 8 3
-+-----------------------
D| 8 | 6 | 3 2
E| | 5 |
F| 9 3 | 8 | 6
-+-----------------------
G| 7 1 4 | | 9
H| 2 | | 8
I| | 4 | 3
Responder:
| 1 2 3 | 4 5 6 | 7 8 9
-+-----------------------
A| 8 3 2 | 5 9 1 | 6 7 4
B| 4 9 6 | 3 8 7 | 2 5 1
C| 5 7 1 | 2 6 4 | 9 8 3
-+-----------------------
D| 1 8 5 | 7 4 6 | 3 9 2
E| 2 6 7 | 9 5 3 | 4 1 8
F| 9 4 3 | 8 1 2 | 7 6 5
-+-----------------------
G| 7 1 4 | 6 3 8 | 5 2 9
H| 3 2 9 | 1 7 5 | 8 4 6
I| 6 5 8 | 4 2 9 | 1 3 7
Reglas:
- Suponga que todos los laberintos se pueden resolver solo por lógica.
- Toda entrada tendrá 81 caracteres de longitud. Los caracteres que faltan serán 0.
- Salida de la solución como una sola cadena.
- La "cuadrícula" puede almacenarse internamente como lo desee.
- La solución debe usar una solución de adivinación de fuerza bruta.
- Las soluciones deben resolverse dentro de un plazo razonable.
Ejemplo de E / S:
>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
code-golf
game
puzzle-solver
sudoku
snmcdonald
fuente
fuente
Respuestas:
k (72 bytes)
El crédito por esto va para Arthur Whitney, creador del lenguaje k.
fuente
Python, 188 bytes
Esta es una versión más corta de mi presentación ganadora para CodeSprint Sudoku , modificada para entrada de línea de comando en lugar de stdin (según el OP):
Si está utilizando Python 2,
'%d'%5**18
puede reemplazarse`5**18`
para ahorrar 3 bytes.Para que funcione más rápido, puede reemplazarlo
'%d'%5**18
con cualquier permutación'123456789'
a un costo de 1 byte.Si desea que acepte la entrada en stdin, puede reemplazar
import sys;f(sys.argv[1])
conf(raw_input())
, reduciéndolo a 177 bytes .EDITAR: Aquí hay un enlace a un tutorial más detallado.
fuente
Python, 197 caracteres
fuente
Respuesta en D:
Con la entrada de muestra, toma 0.033 s en mi Phenom II X6 1090T cuando se compila
dmd -w
(es decir, sin optimizaciones), y toma 0.011 s cuando se compiladmd -w -O -inline -release
(es decir, con optimizaciones).fuente
J, 103
tiempo de ejecución esperado: O (miles de millones de años)
fuente
Perl, 120 bytes
Ah, recuerdo jugar al golf en 2008 ... Y de hecho dejó de funcionar en Perl 5.12 ya que la configuración implícita de @_ por división se eliminó en ese momento. Así que solo prueba esto en un perl suficientemente viejo.
Ejecutar con la entrada en STDIN:
sudoku.pl
:fuente
Perl, 235 caracteres
Esta es una versión de golf de algo que publiqué hace muchos años en la lista de correo Fun With Perl : una expresión regular para resolver sudoku.
Básicamente, divide la entrada en 81 líneas, cada una de las cuales contiene todos los números que podrían aparecer en el cuadrado correspondiente. Luego construye una expresión regular para que coincida con un número de cada línea, utilizando referencias y afirmaciones negativas anticipadas para rechazar soluciones que violen las restricciones de fila, columna o región. Luego hace coincidir la cadena con la expresión regular, permitiendo que el motor de expresión regular de Perl haga el trabajo duro de prueba y retroceso.
Sorprendentemente, es posible crear una expresión regular única que funcione para cualquier entrada, como lo hace mi programa original. Desafortunadamente, es bastante lento, por lo que basé el código de golf aquí en la versión de datos codificados (que se encuentra más adelante en el hilo FWP ), que modifica la expresión regular para rechazar temprano cualquier solución que sepa que luego violará una restricción. Esto lo hace razonablemente rápido para sudokus de nivel fácil a moderado, aunque los particularmente difíciles aún pueden tardar bastante tiempo en resolverse.
Ejecute el código con
perl -M5.010
para habilitar la función Perl 5.10+say
. La entrada debe darse en la entrada estándar, y la solución se imprimirá en la salida estándar; ejemplo:fuente
Guión de café de 1 línea
solve = (s, c = 0) -> if c is 81 then s else if s[x = c/9|0][y = c%9] isnt 0 then solve s, c+1 else (([1..9].filter (g) -> ![0...9].some (i) -> g in [s[x][i], s[i][y], s[3*(x/3|0) + i/3|0][3*(y/3|0) + i%3]]).some (g) -> s[x][y] = g; solve s, c+1) or s[x][y] = 0
Aquí está la versión más grande con uso de muestra :
fuente
solve
, eliminando muchos espacios en blanco (sé que es significativo, pero en muchos lugares podría eliminarse), usando símbolos en lugar de palabras (como en!=
lugar deisnt
), usando sangría en lugar dethen
palabra clave, reemplazando[0...9]
con[0..8]
.Clojure - 480 bytes
El tamaño explotó, pero al menos es un número bonito. Creo que podría mejorarse mucho usando solo 1D-vector. De todos modos, el caso de prueba tarda un poco menos de cuatro segundos en mi computadora portátil. Pensé que sería apropiado definir una función, ya que es un lenguaje funcional después de todo.
Ejemplos:
Una versión ungolfing (y más bonita):
fuente
PowerShell ,
244242218215 bytesPruébalo en línea!
El script encuentra todas las soluciones para un sudoku.
Desenrollado:
Casos de prueba:
fuente
D (322 caracteres)
Para cada cuadrado sin resolver, crea una serie de opciones disponibles y luego recorre el mismo.
con espacios en blanco:
fuente
Perl (195 caracteres)
Todo el crédito va al creador aquí , y la explicación también se puede encontrar allí.
fuente
J 94 bytes
Funciona exactamente de la misma manera que la versión K, es decir, con un BFS (por lo que generará todas las soluciones). Imprime espacios entre los dígitos de salida, pero también lo hace el programa K. No estoy contando "s =:" ya que esto es solo nombrar la función (al igual que no contaría el nombre de archivo en otro idioma).
fuente