19
\$\begingroup\$

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).

\$\endgroup\$
  • 3
    \$\begingroup\$ Boring and probably difficult :( \$\endgroup\$ – Oleh Prypin Aug 28 '11 at 18:04
  • 6
    \$\begingroup\$ Boo. 'Not print anything, not even a newline' rules out GolfScript. \$\endgroup\$ – Peter Taylor Aug 28 '11 at 21:35
  • 1
    \$\begingroup\$ a sudoku solver that never needs to backtrack/guess for a full solution is needed for this, (and each time a "guess" is needed output it) \$\endgroup\$ – ratchet freak Aug 29 '11 at 1:30
  • 3
    \$\begingroup\$ I don't see the reason to downvote this. Much effort was made to show a pretty puzzle; it is very clear, and properly stated. It's too big for my taste, but that's too subjective for a reason to downvote, isn't it? \$\endgroup\$ – user unknown Aug 29 '11 at 10:43
10
\$\begingroup\$

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
    
\$\endgroup\$
  • 2
    \$\begingroup\$ Can’t you just expand this into a Prolog answer? Then it’d be competing! (You could post it separately.) I’m not sure how direct the mapping between Brachylog and Prolog is. \$\endgroup\$ – Lynn Jul 22 '16 at 17:30
  • \$\begingroup\$ @Lynn Yes I could, I could even just post the Prolog code that gets generated by Brachylog's transpiler (which would be highly ungolfed obviously). I won't do it though because I'm pretty sure the challenge's poster will never come back to accept an answer anyway :p \$\endgroup\$ – Fatalize Jul 22 '16 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.