Implémenter un solveur Sudoku non-devinant

27

Implémentez le solveur Sudoku le plus court.

Puzzle 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

Répondre:

 | 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

Règles:

  1. Supposons que tous les labyrinthes ne peuvent être résolus que par logique.
  2. Toutes les entrées comporteront 81 caractères. Les caractères manquants seront 0.
  3. Générez la solution sous forme de chaîne unique.
  4. La "grille" peut être stockée en interne comme vous le souhaitez.
  5. La solution doit utiliser une solution ne devinant pas. (voir Solveur Sudoku )

Exemple d'E / S:

>sudoku.py "030001000006000050500000983080006302000050000903800060714000009020000800000400030"
832591674496387251571264983185746392267953418943812765714638529329175846658429137
snmcdonald
la source
Vous devez vraiment ajouter un délai.
JPvdMerwe
1
@JPvdMerwe: Bon point, mais un délai serait difficile à standardiser.
snmcdonald
1
@gnibbler: Cela aurait pu être fait avant (mais pas sur codegolf.se). Je pense que ce sera toujours amusant à résoudre et à ajouter de la valeur à la communauté, surtout si on s'y prend honnêtement.
snmcdonald
2
J'aime celui la. J'ai hésité à essayer une véritable solution de golf et j'ai pensé à écrire un solveur Sudoku (cela semble être un exercice amusant). Je pense que c'est quelque chose que des gens comme moi, qui n'ont jamais joué au golf auparavant, pourraient utiliser comme point de départ. Et une fois que j'en aurai un, je pourrais alors le jouer au golf.
Andy
4
Les problèmes "résolubles uniquement par la logique" sont très vagues. Voulez-vous dire, peut-être, en utilisant uniquement les étapes de base de a) Écrire une valeur dans une cellule pour laquelle elle ne se trouve pas dans sa ligne, sa colonne et son bloc b) Identifier un nombre qui ne peut aller qu'à un seul endroit dans sa ligne, sa colonne , ou bloquer, et l'écrire là-bas?
xnor

Réponses:

4

RUBY ( 449 436 caractères)

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

Exemple:

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

explication rapide:
Board best un tableau de 81 tableaux contenant toutes les valeurs possibles pour chaque cellule. Le tableau de la troisième ligne contient [offset, start_index] pour chaque groupe (boîtes, lignes, colonnes). Trois tâches sont effectuées lors de l'itération à travers les groupes.

  1. La valeur de n'importe quelle cellule de taille 1 est supprimée du reste du groupe.
  2. Si une paire de cellules contient les mêmes 2 valeurs, ces valeurs sont supprimées du reste du groupe.
  3. Le nombre de chaque valeur est stocké dans d- s'il n'y a qu'une seule instance d'une valeur, nous définissons la cellule conteneur à cette valeur et marquons la cellule fixée dansf

Répétez jusqu'à ce que toutes les cellules soient fixes.

AShelly
la source
Vous pouvez omettre les crochets I=*(0..8), vous économiserez 2 caractères.
Dogbert
Je reçois sudokusolver.rb:8: unterminated string meets end of filesi je commence par ruby1.8 sudokusolver.rb 030.... Qu'est-ce que je fais mal?
utilisateur inconnu
On dirait qu'il y a un supplément sur la dernière ligne. Je ne sais pas comment cela a pu arriver ...
AShelly
2

Prolog - 493 caractères

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

Sortie:

Entrée: 000000000000003085001020000000507000004000100090000000500000073002010000000040009 Sorties: 987654321246173985351928746128537694634892157795461832519286473472319568863745219

Entrée: 030001000006000050500000983080006302000050000903800060714000009020000800000400030 Sorties: 832591674496387251571264983185746392267953418943812765714638529329175846658429137

MT0
la source