Einzigartiger Sudoku Finder

19

Herausforderung:

Bestimmen Sie bei einem Sudoku-Board mit Standardeingabe die Mindestanzahl der hinzugefügten Nummern, um das Board eindeutig zu machen.

Besonderheiten / Regeln:

  • Die Eingabe ist wie folgt formatiert (alle Leerzeichen sind signifikant)

    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
    
  • Die Ausgabe wird mit einer Zahl pro Zeile formatiert, die wie folgt formatiert ist: (x,y):z- x und y beginnen links oben bei eins und erhöhen sich nach unten und rechts; z ist die Zahl, die hinzugefügt werden soll.

    • In diesem Fall wird diese alle gültigen Ausgaben würde: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, und (5,6):7, als einer dieser das Board zu lösende erlauben würde.
  • Wenn eine eindeutige / gelöste Sudoku-Tafel eingegeben wird, sollte das Programm nichts drucken, auch keine neue Zeile.
  • Das Programm sollte für jedes Board in weniger als einer Stunde ausgeführt werden (ich empfehle, ein vollständig leeres Board oder ein Board mit einer Zufallszahl zu verwenden ...).

Wertung:

  • Geben Sie die Gesamtgröße Ihres Codes (Golf) in Zeichen an, einschließlich Leerzeichen ...

Boni:

1/2 Codegröße : Wenn das Programm ein einzelnes Ausrufezeichen druckt und eine Tafel ohne eingegebene Lösungen nicht mehr anzeigt.

1/2 Codegröße : Wenn das Programm zwei Ausrufezeichen druckt und eine Tafel mit einem internen Widerspruch nicht mehr eingibt (zwei gleiche Zahlen in derselben Zeile / Spalte / Quadrat).

Wurzel Unendlichkeit
quelle
3
Langweilig und wahrscheinlich schwierig :(
Oleh Prypin
6
Boo. 'Nichts drucken, auch kein Zeilenumbruch' schließt GolfScript aus.
Peter Taylor
1
Sudoku ein Solver , dass nie mehr zurückverfolgen / Vermutung für eine vollständige Lösung hierfür erforderlich ist, (und jedes Mal , wenn eine „Vermutung“ ausgegeben es erforderlich)
Ratsche Freak
3
Ich sehe keinen Grund, dies abzulehnen. Es wurden große Anstrengungen unternommen, um ein hübsches Puzzle zu zeigen. es ist sehr klar und richtig angegeben. Es ist zu groß für meinen Geschmack, aber das ist zu subjektiv für einen Grund für eine Ablehnung, nicht wahr?
Benutzer unbekannt

Antworten:

10

Brachylog , 245 Bytes / 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

(Beachten Sie, dass Sie bei diesem Commit die Version der Sprache verwenden müssen . Für diesen Code sind einige geringfügige Änderungen erforderlich, damit er in den folgenden Versionen von Brachylog ordnungsgemäß funktioniert.)

Dies wird gedruckt, "!!"wenn das angegebene Board interne Widersprüche aufweist (dies dauert in diesem Fall einige Sekunden, jedoch bei TIO, also haben Sie etwas Geduld).

Ich bin mir nicht sicher, ob ich den ersten Bonus richtig verstehe, also gehe ich nicht darauf ein.

Dies ist offensichtlich nicht konkurrierend, da die Sprache viel jünger ist als die Herausforderung. Da es jedoch keine anderen Antworten gibt, bin ich mir nicht sicher, ob dies eine große Rolle spielt.

Erläuterung

  • Hauptprädikat:

    @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ädikat 1: Entferne alle " |" Zeilen in, transformiere die ---+---+---in -, um sie danach zu entfernen

    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ädikat 2: Konvertieren Sie ein Zeichen in eine Ganzzahl oder, falls leer, in eine Variable zwischen 1 und 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ädikat 3: Legen Sie fest, dass alle Werte der Eingabeliste von Zellen unterschiedlich sein müssen

    :ha    Retrieve the head of each cell (i.e. the value) in the input 
    #d.    Apply a constraint of distinctness to those values
    
  • Prädikat 4: Wenden Sie die Unterscheidungsbedingung auf Werte in 3 * 3-Blöcken an

    :@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ädikat 5:

    :3a.    Apply predicate 3 to each element of the input
    
  • Prädikat 6: Weisen Sie einer Teilmenge der leeren Zellen Werte zu, die die Einschränkungen erfüllen. Mit diesen Werten gibt es dann nur eine Lösung für die Karte.

    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ädikat 7: Transformiert die Karte so, dass jetzt jede Zelle [V:X:Y]statt nur V(der Wert) ist.

    :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ädikat 8: Transformiert eine Linie so, dass sich jede Zelle jetzt befindet [V:X].

    :Jm    Take the Jth element of the line
    :J.    Output is [That element:J]
    
  • Prädikat 9: Ruft die Werte von Zellen ab

    :ha.   Take the head of each element of the input
    
  • Prädikat 10: Hängen Sie die Länge einer Teilmenge am Anfang an

    lg     Put the length of the input in a list
    :?c.   Concatenate it with the input
    
  • Prädikat 11: Eine Zelle drucken

    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
    
Tödlich
quelle
2
Kannst du das nicht einfach zu einer Prolog-Antwort erweitern? Dann würde es konkurrieren! (Du könntest es separat posten.) Ich bin mir nicht sicher, wie direkt die Zuordnung zwischen Brachylog und Prolog ist.
Lynn
@Lynn Ja, ich könnte, ich könnte sogar einfach den Prolog-Code posten, der vom Brachylog-Transpiler generiert wird (der natürlich sehr ungolfed wäre). Ich werde es jedoch nicht tun, da ich mir ziemlich sicher bin, dass das Poster der Herausforderung ohnehin nie wieder eine Antwort annehmen wird: p
Fatalize