Unique Sudoku Finder

Question

Challenge:

Given a Sudoku board on standard input, find the minimum number of numbers added to make the board unique.

Specifics/Rules:

• The input is formatted as follows (all whitespace is significant)

  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
  

• The output is formatted with one number per line, formatted like (x,y):z - x and y start from one at the top left and increase down and right; z is the number to be added.

  • In this case these would all be valid outputs: (3,4):3, (3,4):7, (5,4):3, (5,4):7, (3,6):3, (3,6):7, (5,6):3, and (5,6):7, as any one of these would allow the board to be solved.
• If a unique/solved Sudoku board is entered, the program should not print anything, even a newline.
• The program should run in less than an hour for any board (I suggest testing using a fully blank board, or a board with one random number on it...).

Scoring:

• Take your total (golfed) code size in characters, including all whitespace...

Bonuses:

1/2 code size: If the program prints a single exclamation point and stops upon having a board with no solutions entered.

1/2 code size: If the program prints two exclamation points and stops upon having a board with an internal contradiction entered (two numbers the same on the same row/column/square).

Answer 1

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

(Note that you have to use the version of the language as of this commit. This code would need some slight changes for it to work properly in the following versions of Brachylog)

This prints "!!" if the given board has internal contradictions (This takes a few seconds in that case however on TIO, so be patient).

I'm not sure I understand the first bonus correctly so I'm not addressing it.

This is obviously non-competing since the language is much more recent than the challenge, however since there are no other answers I'm not sure this matters a whole lot…

Explanation

• Main predicate:

  @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
  

• Predicate 1: Remove all "|" on lines, transform the ---+---+--- into - to remove them after

  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
  

• Predicate 2: Convert one char to an integer, or if blank to a variable between 1 and 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
  )
  

• Predicate 3: Impose that all values of the input list of cells must be distinct

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

• Predicate 4: Apply the distinctness constraint to values in 3*3 blocks

  :@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
  

• Predicate 5:

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

• Predicate 6: Assign values satisfying the constraints to a subset of the blank cells, then with those values there is only one solution to the board.

  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
  

• Predicate 7: Transforms the board such that each cell is now [V:X:Y] instead of only V (the value).

  :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
  

• Predicate 8: Transforms a line such that each cell is now [V:X].

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

• Predicate 9: Retrieve the values of cells

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

• Predicate 10: Append the length of a subset at the beginning of it

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

• Predicate 11: Print one cell

  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