Wyzwanie:

Biorąc pod uwagę tablicę Sudoku na standardowym wejściu, znajdź minimalną liczbę liczb dodanych, aby tablica była wyjątkowa.

Szczegóły / zasady:

• Dane wejściowe są sformatowane w następujący sposób (wszystkie białe znaki są znaczące)

  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
  

• Dane wyjściowe są sformatowane za pomocą jednej liczby w wierszu, sformatowanej jak (x,y):z- xiy zaczynają się od jednej w lewym górnym rogu i zwiększają się w dół i w prawo; z to liczba do dodania.

  • W tym przypadku są to wszystko jest ważne wyjścia: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, i (5,6):7, jak każdy jeden z nich pozwoliłoby deska do rozwiązania.
• Jeśli zostanie wprowadzona unikalna / rozwiązana plansza Sudoku, program nie powinien drukować niczego, nawet nowej linii.
• Program powinien działać w ciągu mniej niż godziny dla dowolnej planszy (sugeruję testowanie przy użyciu całkowicie pustej planszy lub planszy z jedną losową liczbą ...).

Punktacja:

• Weź swój całkowity (golfowy) rozmiar kodu w znakach, w tym wszystkie białe znaki ...

Bonusy:

1/2 rozmiaru kodu : Jeśli program wydrukuje pojedynczy wykrzyknik i zatrzyma się po wprowadzeniu tablicy bez wprowadzonych rozwiązań.

1/2 rozmiaru kodu : Jeśli program wypisze dwa wykrzykniki i zatrzyma się po wprowadzeniu tablicy z wewnętrzną sprzecznością (dwie takie same liczby w tym samym rzędzie / kolumnie / kwadracie).

Brachylog , 245 bajtów / 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

(Zauważ, że musisz użyć wersji języka od tego zatwierdzenia . Ten kod wymagałby niewielkich zmian, aby działał poprawnie w następujących wersjach Brachylog)

Zostanie wydrukowane, "!!"jeśli dana tablica ma wewnętrzne sprzeczności (w takim przypadku zajmuje to jednak kilka sekund, ale bądź cierpliwy).

Nie jestem pewien, czy poprawnie rozumiem pierwszy bonus, więc nie rozwiązuję go.

Jest to oczywiście niekonkurencyjne, ponieważ język jest znacznie nowszy niż wyzwanie, jednak ponieważ nie ma innych odpowiedzi, nie jestem pewien, czy to ma duże znaczenie…

Wyjaśnienie

• Główny predykat:

  @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
  

• Predykat 1: Usuń wszystkie |linie z linii, przekształć ---+---+---w, -aby usunąć je później

  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
  

• Predykat 2: Konwertuj jeden znak na liczbę całkowitą lub, jeśli jest pusty, na zmienną między 1 a 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
  )
  

• Predykat 3: Załóżmy, że wszystkie wartości listy wejściowej komórek muszą być odrębne

  :ha    Retrieve the head of each cell (i.e. the value) in the input 
  #d.    Apply a constraint of distinctness to those values
  

• Predykat 4: Zastosuj ograniczenie odróżniające do wartości w blokach 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
  

• Predykat 5:

  :3a.    Apply predicate 3 to each element of the input
  

• Predykat 6: Przypisz wartości spełniające ograniczenia do podzbioru pustych komórek, a następnie przy tych wartościach istnieje tylko jedno rozwiązanie na planszy.

  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
  

• Predykat 7: Przekształca planszę tak, że każda komórka jest teraz [V:X:Y]zamiast tylko V(wartość).

  :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
  

• Predykat 8: Przekształca linię tak, aby każda komórka była teraz [V:X].

  :Jm    Take the Jth element of the line
  :J.    Output is [That element:J]
  

• Predykat 9: pobierz wartości komórek

  :ha.   Take the head of each element of the input
  

• Predykat 10: Dołącz długość podzestawu na początku

  lg     Put the length of the input in a list
  :?c.   Concatenate it with the input
  

• Predykat 11: wydrukuj jedną komórkę

  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