12
\$\begingroup\$

Introduction:

I'm old-fashioned and still read a physical newspaper in the morning while eating my breakfast. Although I don't like Sudoku that much, I do solve the Light-complexity ones, which are extremely easy. With these, I always try to solve all the numbers using only the Hidden Single technique†, in increasing order from 1 to 9. If I can fill in the current digit in all nine of it cells, I write it down at the top.

Thus far, I've only been able to complete the entire Sudoku in increasing order once††. Usually, a digit has two paired cells where they can go in either combination, so I'll skip them, and fill them in at the end.

† Naked Single and Hidden Single solving techniques are the basic Sudoku solving strategies that won't require any hint numbers to be used. When I solve the Light-complexity Sudoku in my newspaper, and therefore also in this challenge, I only use the Hidden Single solving technique. Here the relevant quote from my Puzzling SE post:

2. Hidden Single

Again, a pretty easy one that everyone knows: When there is only one place in a particular row, column or block for a specific number to go, we can just fill it in. For example:

enter image description here

Here there is only one place for the 2 to go in the center 3x3 box, and that is the marked cell.

Challenge:

Given a Sudoku, output the set of digits which you were able to fill in all nine occurrences of while solving the Sudoku with only Hidden Single techniques, when going in increasing order from 1 to 9.

Example:

Input:

[[3,7,0,  0,0,0,  1,0,4],
 [0,1,8,  2,4,0,  0,0,3],
 [0,0,0,  1,7,0,  8,0,0],
 
 [0,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,0,0,  0,6,1],
 [0,0,0,  0,1,9,  0,0,0],
 
 [8,0,4,  0,0,2,  0,0,0],
 [0,0,0,  0,8,0,  2,0,9],
 [0,3,1,  0,9,6,  5,4,0]]

We first try to fill in all the 1s using Hidden Single techniques:

[[3,7,0,  0,0,0,  1,0,4],
 [0,1,8,  2,4,0,  0,0,3],
 [0,0,0,  1,7,0,  8,0,0],
 
 [1,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,0,0,  0,6,1],
 [0,0,0,  0,1,9,  0,0,0],
 
 [8,0,4,  0,0,2,  0,1,0],
 [0,0,0,  0,8,1,  2,0,9],
 [0,3,1,  0,9,6,  5,4,0]]

Since we were able to fill in all 1s, we add the 1 to the result-set.
Next up are the 2s:

[[3,7,0,  0,0,0,  1,2,4],
 [0,1,8,  2,4,0,  0,0,3],
 [0,2,0,  1,7,0,  8,0,0],
 
 [1,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,2,0,  0,6,1],
 [0,0,0,  0,1,9,  0,0,2],
 
 [8,0,4,  0,0,2,  0,1,0],
 [0,0,0,  0,8,1,  2,0,9],
 [2,3,1,  0,9,6,  5,4,0]]

We were again able to fill in all digits, so we add the 2 to the result-set.
Next up are the 3s:

[[3,7,0,  0,0,0,  1,2,4],
 [0,1,8,  2,4,0,  0,0,3],
 [0,2,0,  1,7,3,  8,0,0],
 
 [1,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,2,0,  0,6,1],
 [0,0,3,  0,1,9,  0,0,2],
 
 [8,0,4,  0,0,2,  0,1,0],
 [0,0,0,  0,8,1,  2,0,9],
 [2,3,1,  0,9,6,  5,4,0]]

We were only able to fill in two 3s, with four 3s still left to fill in. So we won't add it to the result-set, and continue with the 4s:

[[3,7,0,  0,0,0,  1,2,4],
 [0,1,8,  2,4,0,  0,0,3],
 [4,2,0,  1,7,3,  8,0,0],
 
 [1,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,2,4,  0,6,1],
 [0,4,3,  0,1,9,  0,0,2],
 
 [8,0,4,  0,0,2,  0,1,0],
 [0,0,0,  4,8,1,  2,0,9],
 [2,3,1,  0,9,6,  5,4,0]]

These we were able to fill all in, so 4 will be added to the result-set.
Next up are the 5s:

[[3,7,0,  0,0,0,  1,2,4],
 [0,1,8,  2,4,0,  0,0,3],
 [4,2,0,  1,7,3,  8,0,0],
 
 [1,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,2,4,  0,6,1],
 [5,4,3,  0,1,9,  0,0,2],
 
 [8,0,4,  0,5,2,  0,1,0],
 [0,0,0,  4,8,1,  2,0,9],
 [2,3,1,  0,9,6,  5,4,0]]

We were able to fill in two 5s, with four 5s still left to fill in. So we won't add it to the result-set, and continue again.
Etc. for 6s (not added); 7s (not added); 8s (added); and 9s (added). The Sudoku after all the digits looks like this:

[[3,7,0,  9,6,8,  1,2,4],
 [0,1,8,  2,4,0,  9,0,3],
 [4,2,9,  1,7,3,  8,0,0],
 
 [1,6,2,  8,0,7,  4,9,5],
 [9,8,7,  5,2,4,  0,6,1],
 [5,4,3,  6,1,9,  0,8,2],
 
 [8,9,4,  0,5,2,  0,1,0],
 [7,0,0,  4,8,1,  2,0,9],
 [2,3,1,  0,9,6,  5,4,8]]

You don't have to solve the Sudoku any further. You can simply output the final result-set, which is [1,2,4,8,9] for this Sudoku.

Challenge Rules:

  • Although we solve the Sudoku from 1 to 9, the result-set doesn't necessarily have to be ordered.
  • The input-Sudoku can be in any reasonable format. Can be a matrix of integers with 0 or -1 for empty cells; a flattened list of integers; a string with spaces for empty cells; or even an image file for all I care. Please specify your input-format in your answer.
  • Likewise, the output can be in any reasonable format as well. Can be a list of digits; a string of digits; printed on separated lines to STDOUT; a 1-based indexed binary-list of size 9 for which digits were truthy; etc.

General Rules:

  • This is , so the shortest answer in bytes wins.
    Don't let code-golf languages discourage you from posting answers with non-codegolfing languages. Try to come up with an as short as possible answer for 'any' programming language.
  • Standard rules apply for your answer with default I/O rules, so you are allowed to use STDIN/STDOUT, functions/method with the proper parameters and return-type, full programs. Your call.
  • Default Loopholes are forbidden.
  • If possible, please add a link with a test for your code (e.g. TIO).
  • Also, adding an explanation for your answer is highly recommended.

Test Cases:

(Using a matrix input and list output.)

Input:
[[3,7,0,  0,0,0,  1,0,4],
 [0,1,8,  2,4,0,  0,0,3],
 [0,0,0,  1,7,0,  8,0,0],
 
 [0,6,2,  0,0,7,  4,0,5],
 [9,0,7,  5,0,0,  0,6,1],
 [0,0,0,  0,1,9,  0,0,0],
 
 [8,0,4,  0,0,2,  0,0,0],
 [0,0,0,  0,8,0,  2,0,9],
 [0,3,1,  0,9,6,  5,4,0]]
Output:
[1,2,4,8,9]

††Input:
[[0,0,0,  0,6,0,  0,7,0],
 [4,8,0,  7,0,0,  0,0,6],
 [2,7,0,  4,5,0,  1,0,3],
 
 [8,0,0,  1,0,0,  6,3,0],
 [0,0,2,  0,0,5,  9,1,0],
 [0,6,9,  0,8,2,  0,0,0],
 
 [7,0,0,  0,0,0,  0,2,1],
 [0,0,4,  9,0,8,  0,5,0],
 [0,3,1,  0,4,7,  8,0,0]]
Output:
[1,2,3,4,5,6,7,8,9]

Input:
[[0,0,9,  4,0,0,  7,1,0],
 [0,1,2,  0,7,0,  0,0,9],
 [0,4,0,  2,1,0,  5,0,0],
 
 [0,2,6,  0,0,0,  0,5,4],
 [0,0,0,  1,8,0,  6,0,7],
 [7,0,8,  6,5,0,  0,0,0],
 
 [9,0,0,  0,0,3,  0,6,0],
 [6,0,4,  0,2,8,  1,0,0],
 [0,8,0,  7,0,0,  0,9,5]]
Output:
[1,4,6,7,8,9]

Input (actually a High-complexity Sudoku from my newspaper):
[[0,0,0,  2,4,0,  5,0,0],
 [9,0,0,  0,0,8,  0,0,0],
 [0,0,0,  0,0,0,  0,0,8],
 
 [0,0,0,  0,2,0,  7,0,4],
 [0,0,7,  0,0,0,  3,0,0],
 [0,4,9,  5,0,0,  1,6,0],
 
 [3,9,0,  0,8,5,  0,2,0],
 [1,0,8,  0,3,0,  4,0,0],
 [0,0,0,  1,0,0,  0,0,0]]
Output:
[]
\$\endgroup\$
5
  • \$\begingroup\$ I I find naked singles really difficult to spot, so I do all the hidden singles from 1 to 9 in order first, and then look for naked singles in rows/columns/squares with three or fewer empty cells. After that the Sudoku in my current newspaper is usually fairly easy to finish off, although I always try to end with a 9 if I can. \$\endgroup\$
    – Neil
    Aug 30 at 18:59
  • 1
    \$\begingroup\$ @Arnauld I've edited the challenge. Again, I'm so sorry for incorrectly adding naked single even though only hidden single was relevant (and thanks for catching my mistake!) \$\endgroup\$ Aug 30 at 20:26
  • \$\begingroup\$ Looking for hidden singles in boxes only is enough for all your test cases. I guess there are some cases where looking for hidden singles in columns and rows is required (and I've updated my solution accordingly). But I'm actually not 100% sure about that. \$\endgroup\$
    – Arnauld
    Aug 31 at 7:12
  • \$\begingroup\$ Can we take input as a 3x3 matrix of 3x3 matrices? \$\endgroup\$
    – Steffan
    Sep 3 at 18:19
  • \$\begingroup\$ @Steffan Sure. As I mentioned in the rules, and input format is flexible. \$\endgroup\$ Sep 3 at 19:23

2 Answers 2

5
\$\begingroup\$

JavaScript (ES6), 239 bytes

Returns a string of digits, or undefined if no set at all was completed.

m=>(i=1,g=o=>i>9?o:g([u=M=0,1,2,n=9].map(N=p=>m.map((r,y)=>r.map((v,x)=>(A=[x,y+9,b=x/3-~(y/3+5)*3|0],k=v==i,q=1<<x|1<<y+9|1<<b,M|=k*q,v|=M&q,p^9?p^2?p*v&&A.map(j=>N[j]=-~N[j]):v|A.every(j=>N[j]^8)?0:r[x]=u=i:n-=k))))|n|u?o:[o]+i,i+=!u))()

Try it online!

How?

We use a recursive function \$g\$ starting with \$i=1\$ and making its way to \$i=10\$, at which point it immediately stops. The value of \$i\$ is the digit that we're currently processing in the grid.

Each iteration is divided into 4 passes. During each pass, we walk through each cell of value \$v\$ at position \$(x,y)\$.

The following variables are always computed, no matter which pass is processed:

k = v == i                        // is the current cell set to i?
b = x / 3 - ~(y / 3 + 5) * 3 | 0  // box number in [18 .. 26]
A = [x, y + 9, b]                 // [ column, row, box ]
q = 1 << x | 1 << y + 9 | 1 << b  // column/row/box bit mask
  1. We set up a 27-bit mask \$M\$ telling in which columns, rows and boxes \$i\$ appears.

    M |= k * q
    
  2. For each column, row and box, we figure out the number of cells \$N[j],\:j\in\{x,y+9,b\}\$ where \$i\$ can't possibly appear.

    v |= M & q
    v && A.map(j => N[j] = -~N[j])
    
  3. If a column, row or box has exactly 8 cells where \$i\$ cannot appear, we set the remaining cell to \$i\$ and set the flag \$u\$. This is the actual implementation of the hidden single rule.

    v | A.every(j => N[j] ^ 8) ? 0 : r[x] = u = i
    
  4. During the last pass, we decrement \$n\$ (which is initialized to 9) whenever a cell of value \$i\$ is found in the updated grid.

    n -= k
    

If \$u\$ was set, it means that the grid was updated and we do a recursive call with \$i\$ unchanged. Otherwise, we do a recursive call with \$i+1\$ and append \$i\$ to the final output string if \$n=0\$.

g(n | u ? o : [o] + i, i += !u)
\$\endgroup\$
4
+500
\$\begingroup\$

Python3, 677 bytes:

R=range
E=enumerate
r=R(0,9,3)
K=lambda b:[(B:=[[(x,y)for y,k in E(j)]for x,j in E(b)]),[*zip(*B)],[[t for X in B[x:x+3]for t in X[y:y+3]]for x in r for y in r]]
S=lambda x:type(x)==int
Q=R(1,10)
def U(b,I):
 b=eval(str(b))
 for x,j in E(b):
  for y,k in E(j):
   if k==0:b[x][y]={*Q}-{b[X][Y]for i in K(b)for T in i for X,Y in T if((x,y)in T)&S(b[X][Y])}
 for x,j in E(b):
  for y,k in E(j):
   if 1-S(k)and{I}==k-{L for X,Y in{*[i for i in K(b)[-1]if(x,y)in i][0]}-{(x,y)}for L in[b[X][Y],[]][S(b[X][Y])]}:b[x][y]=I
 return[[[0,i][S(i)]for i in J]for J in b]
def f(b):
 for i in Q:
  while b!=(b:=U(b,i)):1
  if all(any(i==b[x][y]for x,y in T)for O in K(b)for T in O):yield i

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ I see your test cases are all correct. But as mentioned by Arnauld in the comment section: the naked single section of the challenge was incorrect, and only hidden single techniques are used. Not sure what your program does, but maybe something can be golfed because of that? \$\endgroup\$ Aug 30 at 20:25
  • 1
    \$\begingroup\$ @KevinCruijssen Thanks for the update. This only implements hidden single. I, too, had Arnauld's problem, but eventually landed on this. In any case, great challenge as always! \$\endgroup\$
    – Ajax1234
    Aug 30 at 20:29
  • \$\begingroup\$ 693 bytes (footer stripped because link got too long) \$\endgroup\$
    – Steffan
    Aug 30 at 22:47
  • \$\begingroup\$ In addition to Steffan's golfs, k==0 can be k<1. \$\endgroup\$ Aug 31 at 7:20
  • \$\begingroup\$ @Steffan Thanks, updated \$\endgroup\$
    – Ajax1234
    Aug 31 at 16:10

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.