Finder Sudoku unique

19

Défi:

Étant donné une carte Sudoku sur l'entrée standard, trouvez le nombre minimum de numéros ajoutés pour rendre la carte unique.

Détails / règles:

  • L'entrée est formatée comme suit (tous les espaces sont significatifs)

    516|827|943
    278|394|615
    349|615|872
    ---+---+---
    98 |4 2|156
    465|189|237
    12 |5 6|489
    ---+---+---
    892|743|561
    634|951|728
    751|268|394
    
  • La sortie est formatée avec un nombre par ligne, formatée comme (x,y):z- x et y commencent par un en haut à gauche et augmentent vers le bas et la droite; z est le nombre à ajouter.

    • Dans ce cas , ceux - ci seraient tous sorties valides: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3et (5,6):7, comme l'un de ces permettrait au conseil d' administration à résoudre.
  • Si une carte Sudoku unique / résolue est entrée, le programme ne devrait rien imprimer, même une nouvelle ligne.
  • Le programme devrait fonctionner en moins d'une heure pour n'importe quelle carte (je suggère de tester en utilisant une carte entièrement vierge ou une carte avec un nombre aléatoire dessus).

Notation:

  • Prenez votre taille totale (golfée) de code en caractères, y compris tous les espaces ...

Bonus:

1/2 taille de code : si le programme imprime un seul point d'exclamation et s'arrête après avoir une carte sans aucune solution saisie

1/2 taille de code : si le programme imprime deux points d'exclamation et s'arrête après avoir entré une carte avec une contradiction interne (deux chiffres identiques sur la même ligne / colonne / carré).

Root Infinity
la source
3
Ennuyeux et probablement difficile :(
Oleh Prypin
6
Huer. «Ne rien imprimer, pas même une nouvelle ligne» exclut GolfScript.
Peter Taylor
1
un solveur sudoku qui n'a jamais besoin de revenir en arrière / deviner pour une solution complète est nécessaire pour cela, (et chaque fois qu'une "supposition" est nécessaire, sortez-le)
ratchet freak
3
Je ne vois pas la raison de rejeter cela. Beaucoup d'efforts ont été faits pour montrer un joli puzzle; il est très clair et correctement énoncé. C'est trop gros à mon goût, mais c'est trop subjectif pour une raison de voter, n'est-ce pas?
utilisateur inconnu

Réponses:

10

Brachylog , 245 octets / 2 = 122,5

@n:1a:"-"x:7fF:3a$\:3a@3:4a,Fc~bCh[0:0:0]gO,Co~c[V:O:T]h:F:6f:10ao:ba(h:11a;!);"!!"w!
h"-".|:"|"x:2f.
e(~m["0123456789":.]`;0<.<=9)
:ha#d.
:@3az:ca:5a.
:3a.
hs.:=a,?t:9ac:=fl1
:Im:8f:[[I]]z:ca.
:Jm:J.
:ha.
lg:?c.
b:+a[X:Y],?h:Y:Xr:"(~d,~d):~d
"w

(Notez que vous devez utiliser la version du langage à partir de ce commit . Ce code aurait besoin de quelques légères modifications pour qu'il fonctionne correctement dans les versions suivantes de Brachylog)

Cela s'imprime "!!"si la carte donnée présente des contradictions internes (cela prend cependant quelques secondes dans ce cas sur TIO, alors soyez patient).

Je ne suis pas sûr de bien comprendre le premier bonus donc je ne m'y attends pas.

Ce n'est évidemment pas compétitif car la langue est beaucoup plus récente que le challenge, mais comme il n'y a pas d'autres réponses, je ne suis pas sûr que cela compte beaucoup…

Explication

  • Prédicat principal:

    @n                Split the input on line breaks
    :1a:"-"x          Transform into a list of lists, each sublist contains a line's values
    :7fF              Transform so that cells are [Value:X:Y]
    :3a               All values on lines must be different
    $\:3a             All values on columns must be different (by transposition)
    @3:4a,            All 3*3 block values must be different
    Fc~bCh[0:0:0]gO,  Append a fake cell [0:0:0]
    Co~c[V:O:T]       Sort the board, the blank cells V will be those before O ([0:0:0])
    h:F:6f            Find all subsets of blank cells with specific values for which 
                          the board has only one solution
    :10ao             Sort the subsets by lengths
    :ba               Discard the lengths
    (                 
      h:11a             Print the first subset = an answer
    ;                 Or (board is already fully determined)
      !                 Terminate
    )          
    ;                 Or (Some values don't respect the constraints)
    "!!"w!            Print "!!" and terminate
    
  • Prédicat 1: supprimez tous les " |" sur les lignes, transformez-les ---+---+---en -pour les supprimer après

    h"-".    If the first char is "-", then Output is "-"
    |        Or
    :"|"x    Remove all occurences of "|" from the input
    :2f.     Output is the result of all outputs of predicate 2 on the filtered string
    
  • Prédicat 2: convertissez un caractère en entier ou, s'il est vide, en variable entre 1 et 9.

    e                      Take a char of the input string
    (
      ~m["0123456789":.]     Output is the index of the char in "0123456789"
      `                      Discard the choice point caused by the ;
    ;                      Or
      0<.<=9                 Output is an integer between 1 and 9
    )
    
  • Prédicat 3: Imposer que toutes les valeurs de la liste d'entrée de cellules doivent être distinctes

    :ha    Retrieve the head of each cell (i.e. the value) in the input 
    #d.    Apply a constraint of distinctness to those values
    
  • Prédicat 4: appliquer la contrainte de distinction aux valeurs dans des blocs 3 * 3

    :@3a            Split 3 lines of the board in 3 parts
        z           Zip them together
         :ca:5a.    Concatenate each element of the zip, apply predicate 5 to that
    
  • Prédicat 5:

    :3a.    Apply predicate 3 to each element of the input
    
  • Prédicat 6: Attribuez des valeurs satisfaisant les contraintes à un sous-ensemble des cellules vides, puis avec ces valeurs, il n'y a qu'une seule solution pour la carte.

    hs.       Output is a subset of the blank cells
    :=a,      Assign values to those cells
    ?t:9ac    Concatenate the values of all cells of the board
    :=f       Find all solved boards
    l1        There is only 1 such solved board
    
  • Prédicat 7: Transforme le tableau de telle sorte que chaque cellule est désormais [V:X:Y]au lieu de seulement V(la valeur).

    :Im       Take the Ith line of the board
    :8f       Transform all elements of the line using predicate 8
    :[[I]]z   Zip the result with [I]
    :ca.      Concatenate each element of the zip
    
  • Prédicat 8: Transforme une ligne telle que chaque cellule se trouve maintenant [V:X].

    :Jm    Take the Jth element of the line
    :J.    Output is [That element:J]
    
  • Prédicat 9: récupérer les valeurs des cellules

    :ha.   Take the head of each element of the input
    
  • Prédicat 10: ajouter la longueur d'un sous-ensemble au début de celui-ci

    lg     Put the length of the input in a list
    :?c.   Concatenate it with the input
    
  • Prédicat 11: imprimer une cellule

    b:+a[X:Y],        Increment coordinates by 1 to get X and Y
    ?h:Y:Xr:          Build the list [X:Y:Value]
    "(~d,~d):~d\n"w   Format that list as "('X','Y'):'Value'\n" to STDOUT
    
Fatalize
la source
2
Ne pouvez-vous pas simplement développer cela en une réponse Prolog? Ce serait alors en compétition! (Vous pouvez le poster séparément.) Je ne sais pas à quel point la correspondance entre Brachylog et Prolog est directe.
Lynn
@Lynn Oui, je pourrais, je pourrais même simplement publier le code Prolog qui est généré par le transpilateur de Brachylog (qui ne serait évidemment pas du tout golfé). Je ne le ferai pas car je suis sûr que l'affiche du défi ne reviendra jamais pour accepter une réponse de toute façon: p
Fatalize