Unique Sudoku Finder 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).
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&lt;.&lt;=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&lt;.&lt;=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