Implementar um solucionador de sudoku que não adivinhe

27

Implemente o menor solucionador de Sudoku.

Quebra-cabeça Sudoku:

 | 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

Responda:

 | 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

Regras:

  1. Suponha que todos os labirintos sejam solucionáveis ​​apenas pela lógica.
  2. Todas as entradas terão 81 caracteres. Os caracteres ausentes serão 0.
  3. Saída da solução como uma única sequência.
  4. A "grade" pode ser armazenada internamente da maneira que desejar.
  5. A solução deve usar uma solução não adivinhadora. (consulte Sudoku Solver )

Exemplo de E / S:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
fonte
Você realmente deve adicionar um limite de tempo.
JPvdMerwe 02/02
1
@JPvdMerwe: Bom ponto, mas seria difícil padronizar um prazo.
Snmcdonald
1
@gnibbler: Isso pode ter sido feito antes (mas não no codegolf.se). Eu acho que ainda será divertido resolver, além de agregar algum valor à comunidade, especialmente se formos honestos.
21911 snmcdonald
2
Eu gosto deste. Eu hesitei em tentar uma solução de golfe real e pensei em escrever um solucionador de Sudoku (parece um exercício divertido). Eu acho que é algo que pessoas como eu, que nunca jogaram golfe antes, poderiam usar como ponto de partida. E uma vez que eu invente um, eu poderia jogar golfe.
Andy
4
Problemas "solucionáveis ​​apenas pela lógica" são muito vagos. Você quer dizer, talvez, usar apenas as etapas básicas de a) Escrever um valor em uma célula cujo valor não esteja em sua linha, coluna e bloco b) Identificar um número que só pode ir em um lugar em sua linha, coluna , ou bloco, e escrevê-lo lá?
Xnor 17/05

Respostas:

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*''

Exemplo:

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

explicação rápida:
Board bé uma matriz de 81 matrizes que contém todos os valores possíveis para cada célula. A matriz na linha três mantém [deslocamento, índice_inicial] para cada grupo (caixas, linhas, colunas). Três tarefas são executadas durante a iteração nos grupos.

  1. O valor de qualquer célula do tamanho 1 é removido do restante do grupo.
  2. Se qualquer par de células contiver os mesmos 2 valores, esses valores serão removidos do restante do grupo.
  3. A contagem de cada valor é armazenada d- se houver apenas 1 instância de um valor, definimos a célula que contém esse valor e marcamos a célula como fixaf

Repita até que todas as células estejam corrigidas.

AShelly
fonte
Você pode omitir os colchetes I=*(0..8), economizará 2 caracteres.
314 Dogbert
Eu recebo sudokusolver.rb:8: unterminated string meets end of filese eu começar com isso ruby1.8 sudokusolver.rb 030.... O que estou fazendo errado?
usuário desconhecido
Parece que há um extra na última linha. Não sei como isso chegou lá ...
AShelly
2

Prolog - 493 caracteres

:-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).

Saída:

Entrada: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Saídas: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Entrada: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Saídas: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

MT0
fonte