3
\$\begingroup\$

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 . 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
\$\endgroup\$
6
  • 4
    \$\begingroup\$ Welcome to Code Golf! This isn't currently on-topic. Challenges here require Objective Winning Criteria like code-golf (shortest code) or fastest-algorithm (lowest time complexity). Programming puzzles don't require OWCs, but this isn't one, it's just a challenge. \$\endgroup\$ Sep 15 at 15:48
  • \$\begingroup\$ How is the time complexity measured, given that the input is a constant size?? \$\endgroup\$
    – pxeger
    Sep 15 at 17:56
  • \$\begingroup\$ @pxeger Should I link testcase file as it would be hard for anyone to write down testcase. \$\endgroup\$
    – Arya Singh
    Sep 15 at 18:20
  • \$\begingroup\$ This is still missing an objective winning criterion. A code-challenge requires a way to compare answers still, which as far as I can tell is missing here. You probably want code-golf, since most of the other winning criteria require additional restrictions. \$\endgroup\$ Sep 15 at 20:18
  • \$\begingroup\$ Related: There is a fastest sodoku solver question. \$\endgroup\$
    – tsh
    Sep 16 at 9:44

3 Answers 3

2
\$\begingroup\$

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

\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$
3
  • \$\begingroup\$ Well your's solution clearly violates rule 1 according to which all diagonal flowing from top-left to bottom-right must have unique element. As I can see r2c6 and r4c8 are similar ,r1c4 and r4c7 are similar and many others are similar but they don't have to be. \$\endgroup\$
    – Arya Singh
    Sep 17 at 8:04
  • \$\begingroup\$ @AryaSingh Now fixed. I've edited your challenge to make it clearer that the constraint applies to all diagonals. (Feel free to rollback or edit further.) \$\endgroup\$
    – Arnauld
    Sep 17 at 9:32
  • \$\begingroup\$ Yeah that's cool! I thought someone will understand while reading problem but that doesn't happened that way pretty much. \$\endgroup\$
    – Arya Singh
    Sep 17 at 9:49

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.