Implemente un solucionador de sudoku sin adivinanzas

27

Implemente el solucionador de Sudoku más corto.

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:

  1. Suponga que todos los laberintos se pueden resolver solo por lógica.
  2. Toda entrada tendrá 81 caracteres de longitud. Los caracteres que faltan serán 0.
  3. Salida de la solución como una sola cadena.
  4. La "cuadrícula" puede almacenarse internamente como lo desee.
  5. La solución debe usar una solución sin adivinanzas. (ver Solucionador de Sudoku )

Ejemplo de E / S:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
fuente
Realmente deberías agregar un límite de tiempo.
JPvdMerwe
1
@JPvdMerwe: Buen punto, pero un límite de tiempo sería difícil de estandarizar.
snmcdonald 02 de
1
@gnibbler: Podría haberse hecho antes (pero no en codegolf.se). Creo que será divertido resolverlo y agregarle valor a la comunidad, especialmente si uno lo hace con honestidad.
snmcdonald 02 de
2
Me gusta este. He dudado en probar una solución de golf real, y he estado pensando en escribir un solucionador de Sudoku (parece un ejercicio divertido). Creo que es algo que la gente como yo, que nunca antes había jugado golf, podría usar como punto de partida. Y una vez que se me ocurra uno, podría jugarlo.
Andy
44
Los problemas "solucionables solo por lógica" son muy vagos. ¿Te refieres, quizás, a usar solo los pasos básicos de a) Escribir un valor en una celda para la cual su valor no está en su fila, columna y bloque b) Identificar un número que solo puede ir en un lugar en su fila, columna , o bloquear, y escribirlo allí?
xnor

Respuestas:

4

RUBY ( 449 436 caracteres)

I=*(0..8)
b=$*[0].split('').map{|v|v<'1'?I.map{|d|d+1}:[v.to_i]};f=b.map{|c|!c[1]}
[[z=I.map{|v|v%3+v/3*9},z.map{|v|v*3}],[x=I.map{|v|v*9},I],[I,x]
].map{|s,t|t.map{|i|d=[a=0]*10;s.map{|j|c=b[i+j];c.map{|v|d[v]+=1if !f[i+j]}
v,r=*c;s.map{|k|b[i+k].delete(v)if j!=k}if !r 
s[(a+=1)..8].map{|k|s.map{|l|b[i+l]-=c if l!=k&&l!=j}if c.size==2&&c==b[i+k]}}
v=d.index 1;f[i+k=s.find{|j|b[i+j].index v}]=b[i+k]=[v]if v}}while f.index(!1)
p b*''

Ejemplo:

C:\golf>soduku2.rb 030001000006000050500000983080006302000050000903800060714000009020000800000400030
"832591674496387251571264983185746392267953418943812765714638529329175846658429137"

explicación rápida:
Board bes una matriz de 81 matrices que contienen todos los valores posibles para cada celda. La matriz en la línea tres contiene [offset, start_index] para cada grupo (cuadros, filas, columnas). Se realizan tres tareas mientras se itera por los grupos.

  1. El valor de cualquier celda de tamaño 1 se elimina del resto del grupo.
  2. Si algún par de celdas contiene los mismos 2 valores, estos valores se eliminan del resto del grupo.
  3. El recuento de cada valor se almacena en d: si solo hay 1 instancia de un valor, configuramos la celda que contiene ese valor y marcamos la celda fija enf

Repita hasta que todas las celdas estén arregladas.

AShelly
fuente
Puede omitir los corchetes I=*(0..8), ahorrará 2 caracteres.
Dogbert
Me sale sudokusolver.rb:8: unterminated string meets end of filesi empiezo con ruby1.8 sudokusolver.rb 030.... ¿Qué estoy haciendo mal?
usuario desconocido
Parece que hay un 'extra en la última línea. No estoy seguro de cómo llegó eso ...
AShelly 05 de
2

Prólogo - 493 Personajes

:-use_module(library(clpfd)).
a(X):-all_distinct(X).
b([],[],[]).
b([A,B,C|X],[D,E,F|Y],[G,H,I|Z]):-a([A,B,C,D,E,F,G,H,I]),b(X,Y,Z).
c([A,B,C,D,E,F,G,H,I|X])-->[[A,B,C,D,E,F,G,H,I]],c(X).
c([])-->[].
l(X,Y):-length(X,Y).
m(X,Y):-maplist(X,Y).
n(L,M):-l(M,L).
o(48,_).
o(I,O):-O is I-48.
:-l(L,81),see(user),m(get,L),seen,maplist(o,L,M),phrase(c(M),R),l(R,9),m(n(9),R),append(R,V),V ins 1..9,m(a,R),transpose(R,X),m(a,X),R=[A,B,C,D,E,F,G,H,I],b(A,B,C),b(D,E,F),b(G,H,I),flatten(R,O),m(write,O).

Salida:

Entrada: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Salidas: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Entrada: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Salidas: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

MT0
fuente