Edit - Code Golf Stack Exchange

You are not logged in. Your edit will be placed in a queue until it is peer reviewed.

We welcome edits that make the post easier to understand and more valuable for readers. Because community members review edits, please try to make the post substantially better than how you found it, for example, by fixing grammar or adding additional resources and hyperlinks.

Required fields*

Rev

Required fields*

Solving an easy Sudoku in increasing digit order

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 code-golf, 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:
[]

Answer*

# Python3, 677 bytes:

```lang-py
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!](https://tio.run/##lVXJbtswEL3rK9hLQbo0oN2SAF4C5JAFCLIUSEDwIMFyo9hRDFVppRr@dmdIURTtpodeNJr9vZmxvO3b57c6SLbN4XDHmrz@UTrnrKzfX8smb0unYXfYpSkNiHPFNvlrscxRkXF8ljHOcUd7snprUE/XqKrROX4hQuodfRn0gghC@exPtcWzMyIo5y2SAY/Sfca7rPsWqIxWGh55n/VgGGpIS6Oie/UqhHM/Quiytt@WuCOMVXXr3AJKj3oucZblCn3HBb0gmYMKVv7KN/hn2wAQ4qATaBCBTtBLE6pWaM2YmxW8E7wXbDe73c93BX8U/ElBq2T4FVSQyoNUqoEVfZIKWFZYzUYq5Os91rlk/z8YvPk9XpO8Xu4u9oyt57trq8luxoeeBgufewL66raV4K4A1Erfy8BrCOQaCOVC8AmW2BuuFw5qyva9qTnnLq1kVEUm0pfq9VK@FkINezWQMBG3Ev7v52pTouILw0XG5DoqQjLPUbTyzQbndY8rxnTTYSRqyQ9qpDd/zfeGZH1VbpaoOhRvebP0EEOcB3RBXYqQS10lPXiGgjoIoHs0AYtPQxMRaM8YO@QmUpce5Yupr6MXIGVupLJSbYl0toz0jurJjumIRdeTtUNt822flZUo6cMz1Z4AKklPCj1kR0ABp69o@4xbqbGWC1001MUWJgJilMfXZEMamUEFFsjRJmUMACaQI@wIZArARk@sySbHxMBndx@kb40qVHVctRxZ1T0hHaoxD0vRpAOkWad6JQPHCYunMUzHMI4y1MP1lIyOVu2r8U4oI3M64zwSPQ@orDwLjTvWU7RZpxbrYNyOyorNEfgq27OO4HRfKZybZh1aqx6v2BA4apf847KsCEN6WsnYeCK9sLICq16oBh@ZscSGdEBTc8XRWFdleQZXoA/vFJ9n4wTS2wY@5JjP4HuifuDwx3Fq8z@xBZ/YQrAdPgA)

If this is an answer to a challenge…

…Be sure to follow the challenge specification. However, please refrain from exploiting obvious loopholes. Answers abusing any of the standard loopholes are considered invalid. If you think a specification is unclear or underspecified, comment on the question instead.
…Try to optimize your score. For instance, answers to code-golf challenges should attempt to be as short as possible. You can always include a readable version of the code in addition to the competitive one. Explanations of your answer make it more interesting to read and are very much encouraged.
…Include a short header which indicates the language(s) of your code and its score, as defined by the challenge.

More generally…

…Please make sure to answer the question and provide sufficient detail.
…Avoid asking for help, clarification or responding to other answers (use comments instead).

Draft saved

Draft discarded

Edit Summary*

Cancel

\$\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\$

Kevin Cruijssen
– Kevin Cruijssen

2022年08月30日 20:25:53 +00:00
Commented Aug 30, 2022 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
– Ajax1234

2022年08月30日 20:29:23 +00:00
Commented Aug 30, 2022 at 20:29
\$\begingroup\$ 693 bytes (footer stripped because link got too long) \$\endgroup\$

naffetS
– naffetS

2022年08月30日 22:47:47 +00:00
Commented Aug 30, 2022 at 22:47
\$\begingroup\$ In addition to Steffan's golfs, k==0 can be k<1. \$\endgroup\$

Kevin Cruijssen
– Kevin Cruijssen

2022年08月31日 07:20:30 +00:00
Commented Aug 31, 2022 at 7:20
\$\begingroup\$ @Steffan Thanks, updated \$\endgroup\$

Ajax1234
– Ajax1234

2022年08月31日 16:10:39 +00:00
Commented Aug 31, 2022 at 16:10

| Show 1 more comment

How to Edit

Correct minor typos or mistakes
Clarify meaning without changing it
Add related resources or links
Always respect the author’s intent
Don’t use edits to reply to the author

How to Format

create code fences with backticks ` or tildes ~
```
like so
```
add language identifier to highlight code
```python
def function(foo):
print(foo)
```
put returns between paragraphs
for linebreak add 2 spaces at end
_italic_ or **bold**
indent code by 4 spaces
backtick escapes `like _so_`
quote by placing > at start of line
to make links (use https whenever possible)

<https://example.com>

[example](https://example.com)

<a href="https://example.com">example</a>
MathJax equations \$\sin^2 \theta\$

formatting help »
answering help »

MathJax help »

How to Tag

A tag is a keyword or label that categorizes your question with other, similar questions. Choose one or more (up to 5) tags that will help answerers to find and interpret your question.

complete the sentence: my question is about...
use tags that describe things or concepts that are essential, not incidental to your question
favor using existing popular tags
read the descriptions that appear below the tag

If your question is primarily about a topic for which you can't find a tag:

combine multiple words into single-words with hyphens (e.g. code-golf), up to a maximum of 35 characters
creating new tags is a privilege; if you can't yet create a tag you need, then post this question without it, then ask the community to create it for you

popular tags »