Sudoku Solver Diagonal Constraint

Question

This is the follow up question to standard Sudoku solver.

You are given a Sudoku grid where . represents an empty cell and the other cells are filled with numbers 0-8 (inclusive).

Rules:

• All the numbers in Sudoku must appear exactly once in all left-top to right-bottom diagonals.
• All the numbers in Sudoku must appear exactly once in all right-top to left-bottom diagonals.
• All the numbers in Sudoku must appear exactly once in all squares (3*3).

However numbers can repeat in rows or columns.

This is code-golf. Please post your shortest code in any language that solves this problem. Winner will be the shortest solution by byte count.

Input:

. 3 7 . 4 2 . 2 .
5 . 6 1 . . . . 7
. . 2 . . . 5 0 . 
2 8 3 . . . . . .
. 5 . . 7 1 2 . 7
. . . 3 . . . . 3
7 . . . . 6 . 5 0
. 2 3 . 3 . 7 4 2
0 5 . . 8 . . . . 

Output:

8 3 7 0 4 2 1 2 4
5 0 6 1 8 6 3 6 7 
4 1 2 7 3 5 5 0 8 
2 8 3 5 4 8 6 0 5 
6 5 0 0 7 1 2 1 7 
1 4 7 3 2 6 8 4 3 
7 8 1 4 1 6 3 5 0 
6 2 3 7 3 5 7 4 2 
0 5 4 2 8 0 6 8 1

Answer 1

Prolog (SWI) + clpfd, 231 bytes

\R:-append(R,V),V ins 0..8,-R,R-Q,maplist(reverse,R,W),W-Y,+Y,+Q,maplist(label,R).
-[[A,B,C|D],[E,F,G|H],[I,J,K|L]|Q]:- +[A,B,C,E,F,G,I,J,K],-[D,H,L],-Q.
-_.
[]-[].
[[E|_]|S]-[E|D]:-maplist(*,S,Q),Q-D.
[_|Q]*Q.
+Q:-all_distinct(Q).

Try it online!

This will produce as many choicepoints as solutions there are - Try it online! As you can see, there are plenty :P

Answer 2

05AB1E, 50 bytes

8ÝI'.¢ãε'.s.;¶¡€#©3δô3ô€ø€€˜€`®Å\ª®Å/ªε{ā<Q}Pi®»,q

Try it online.

Brute-force, so very slow. The more dots the input contains, the slower it becomes. It therefore won't be able to complete the example test case of the challenge description, but it can with just a few dots.

Explanation:

8Ý            # Push a list in the range [0,8]
  I           # Push the input-string
   '.¢       '# Pop and count the amount of "."
      ã       # Cartesian product this count with the [0,1,2,3,4,5,6,7,8] list
ε             # Map over each list:
    .;        #  Replace every first
 '.          '#  character "."
              #  in the (implicit) input-string, one by one with
   s          #  the digits of the current list
 ¶¡           #  Split the string on newlines
   €#         #  Then split each inner string on spaces
     ©        #  Store this matrix in variable `®` (without popping)
  δ           #  Map over each row:
 3 ô          #   Split it into three triplets
    3ô        #  Then split the rows into three inner lists as well
      €       #  Map over each list of three rows:
       ø      #   Zip/transpose; swapping rows/columns, to group blocks together
        €€˜   #  Flatten each inner block
           €` #  Flatten one level to a list of lists
 ®            #  Push matrix `®` again
  Å\          #  Pop and push its main diagonal
    ª         #  Append it to the list
 ®Å/ª         #  Do the same for the main anti-diagonal
 ε            #  Map over each inner list:
  {           #   Sort it
   ā          #   Push a list in the range [1,length] (without popping)
    <         #   Decrease it to range [0,length], which will be [0,8] basically
     Q        #   Check if the two lists are equal
 }Pi          #  After the map: if all are truthy:
    ®         #   Push matrix `®` yet again
     »        #   Join each inner row by spaces, and then string by newlines
      ,       #   Pop and print it
       q      #   And then exit the program

Answer 3

JavaScript (ES6), 149 bytes

Expects a matrix of integers with \$0\$'s for empty cells and \$1\$ to \$9\$ for filled cells. Returns another matrix in the same format.

This is a brute-force approach which aborts as soon as the grid is inconsistent, making it reasonably fast -- at least for the unique test case (solved in ~6 seconds on TIO).

f=(m,X,R)=>m.every(q=(r,y)=>r.every((v,x)=>v?(g=k=>q[k]^(q[k]|=1<<v))(x-y)*g(x+y+9)*g(x/3|y/3+8<<2):(X=x,R=r)))?R?m.some(_=>f(m,R[X]++))?m:R[X]=0:m:0

Try it online!

Commented

// m[] = input matrix
// (X, R) = local variables to store the position of an empty cell
//          (more specifically: the last empty cell of the grid)
f = (m, X, R) =>
  // for each row r[] at position y in m[]
  // using q as an object for bit-mask storage
  m.every(q = (r, y) =>
    // for each value v at position x in r[]
    r.every((v, x) =>
      // is this cell empty?
      v ?
        // it's not: make sure its value is valid
        // g is a helper function testing whether q[k] is modified
        // when its v-th bit it set; if not, it means that we have
        // twice the same digit on a diagonal or a square
        (
          g = k => q[k] ^ (q[k] |= 1 << v)
        )(
          // invoke g for the current anti-diagonal,
          // with k in [-8..8]
          x - y
        ) *
        g(
          // invoke g for the current diagonal,
          // with k in [9..25]
          x + y + 9
        ) *
        g(
          // invoke g for the current square,
          // with k in [32..42]
          x / 3 | y / 3 + 8 << 2
        )
      :
        // this cell is empty: save its position in (X, R)
        // NB: this is guaranteed to be truthy (having empty
        // cells does not invalidate the grid)
        (X = x, R = r)
    )
  ) ?
    // the grid is valid so far
    R ?
      // there's an empty cell: attempt to set it to 1 .. 9 and
      // do recursive calls to see if it leads to a solution
      m.some(_ => f(m, R[X]++)) ?
        // if successful, return m[]
        m
      :
        // otherwise, reset the cell to 0 afterwards and abort
        R[X] = 0
    :
      // the grid is valid and there's no empty cell: return m[]
      m
  :
    // the grid is invalid: abort right away
    0