# Retrieve all possible marks that can be placed in a Sudoku puzzle [closed]

Given a Sudoku puzzle, find all possible marks that can be filled into each empty cell.

## Test case

Input:

[
[
// Top left:
[
0, 0, 0,
3, 4, 0,
0, 0, 2
],
// Top middle:
[
7, 4, 0,
0, 0, 0,
0, 0, 3
],
// Top right:
[
8, 0, 0,
1, 7, 0,
0, 0, 0
]
],
[
// Middle left:
[
9, 0, 4,
7, 0, 0,
1, 0, 3
],
// Center:
[
0, 5, 0,
0, 0, 0,
0, 7, 0
],
// Middle right:
[
0, 0, 0,
6, 4, 0,
0, 0, 0
]
],
[
// Bottom left:
[
0, 0, 7,
6, 3, 0,
0, 0, 0
],
// Bottom middle:
[
0, 0, 5,
0, 0, 0,
9, 1, 0
],
// Bottom right:
[
0, 0, 0,
5, 2, 0,
7, 0, 0
]
]
]


Output:

[
[
// Top left:
[
[5], [1, 5, 6, 9], [1, 5, 6, 9],
[], [], [5, 6, 8, 9],
[5, 8], [1, 5, 6, 7, 8, 9], []
],
// Top middle:
[
[], [], [1, 2, 6, 9],
[2, 5, 6, 8], [2, 6, 8, 9], [2, 6, 8, 9],
[1, 5, 6, 8], [6, 8, 9], []
],
// Top right:
[
[], [3, 5, 6, 9], [2, 3, 5, 6, 9],
[], [], [2, 5, 6, 9],
[4, 9], [5, 6, 9], [4, 5, 6, 9]
]
],
[
// Middle left:
[
[], [2, 6, 8], [],
[], [2, 5, 8], [5, 8],
[], [2, 5, 6, 8], []
],
// Center:
[
[1, 2, 3, 6, 8], [], [1, 2, 6, 8],
[1, 2, 3, 8], [2, 3, 8, 9], [1, 2, 8, 9],
[2, 4, 6, 8], [], [2, 4, 6, 8, 9]
],
// Middle right:
[
[2, 3], [1, 3, 8], [1, 2, 3, 7, 8],
[], [], [1, 2, 3, 5, 8, 9],
[2, 9], [5, 8, 9], [2, 5, 8, 9]
]
],
[
// Bottom left:
[
[2, 4, 8], [1, 2, 8, 9], [],
[], [], [1, 8, 9],
[2, 4, 5, 8], [2, 5, 8], [5, 8]
],
// Bottom middle:
[
[2, 3, 4, 6, 8], [2, 3, 6, 8], [],
[4, 8], [8], [4, 7, 8],
[], [], [2, 4, 6, 8]
],
// Bottom right:
[
[3, 4, 9], [1, 3, 6, 8, 9], [1, 3, 4, 6, 8, 9],
[], [], [1, 4, 8, 9],
[], [3, 6, 8], [3, 4, 6, 8]
]
]
]


Output visualisation; the small numbers:

## Rules

• This is a . The shortest answer in bytes (or equivalent) wins.
• Input can be in array or string format.
• Input must be in the order presented above (top-left, top-middle, top-right, etc...)
• Output can be in array or string format, as long as the output can logically represent the expected result.
• Output must be in the same order as the input (top-left, top-middle, top-right, etc...)
• Output does not need to be prettified.
• Code must be applicable to any valid incomplete Sudoku grid.
• Standard golfing rules apply.

You get additional fake internet points if your program or function uses the result to solve the Sudoku puzzle to the point where cell values can no longer be logically solved. For example, the very first cell in the test case can only ever possibly contain the number 5, so it should be considered when filling in the other values. This is just for fun and additional challenge, otherwise the shortest answer wins regardless of whether or not this criterion is met.

• How flexible is the input format? Could it be for instance an array of 9 strings? (such as ["000340002", "740000003", ...]) Commented Oct 4, 2016 at 16:30
• Is a single string going left-to-right, top-to-bottom allowed as input? Like this? And output in the same order?
– orlp
Commented Oct 4, 2016 at 17:07
• If we're not applying logic to work out which cells can and can't be solved, what is the question actually asking us to do? Commented Oct 4, 2016 at 21:02
• What is the distinction you're drawing between that and solving the puzzle? Commented Oct 4, 2016 at 21:14
• So under what circumstances can an incorrect value be placed in a cell? Stop repeating yourself and start defining your terms. Commented Oct 5, 2016 at 7:14

# C (gcc), 193 bytes

#define F(x)for(x=0;x<9;++x)
char s[99];main(k,r,c){gets(s);F(r)F(c){
int d[99]={};F(k)d[s[r*9+k]]=d[s[k*9+c]]=d[s[r/3*27+k/3*9+c/3*3+k%3]]=1;
F(k)s[r*9+c]<48&&!d[49+k]&&putchar(49+k);puts("");}}


Assumes input in the following format (same sudoku as above):

..74.8..34....17...2..3...9.4.5....7.....64.1.3.7......7..5...63....52....91.7..


And outputs in the following format:

5
1569
1569

1269

3569
23569

5689
etc


# Python 2, 178 bytes

lambda s,R=range(9):[[[(s[Y][X][i]<1)*[q+1for q in R if~-(q+1in sum([[s[j/3][X][j%3*3+i%3],s[Y][j/3][j%3+i/3*3]]for j in R],[])+s[Y][X])]for i in R]for X in R[:3]]for Y in R[:3]]


An anonymous function that takes a 3-dimensional array of ints and returns a 4-dimensional array of ints.

## JavaScript (ES6), 208196190188 186 bytes

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))


Input:
An array of 9 strings (one per box, from top-left to bottom-right).

Output:
An array of 9 arrays, where each item consists of either the original number at this position or an array of characters representing the possible digits.

### Formatted and commented

g => g.map((B, i) =>              // for each box B at position i in the grid:
[...B].map((s, x) =>            // for each cell s at position x in this box:
+s ||                         // if there already is a number at this position, use it
[..."123456789"].filter(n =>  // else, for each digit n in [1 .. 9]:
(t = i =>                   // t() = helper function that looks for the digit n inside
(k = g[i].search(n) % m)  // a given box i and returns a truthy value if its
< a | k > b               // position modulo m is not in the range [a .. b]
)(                          //
j = i % 3,                // test the top box in the current column, using:
m = 3,                    // modulo = 3 and
a = b = x % 3             // range = [x % 3 .. x % 3]
) &                         //
t(j + 3) &                  // test the middle box in the current column
t(j + 6) &                  // test the bottom box in the current column
t(                          //
j = i - j,                // test the left box in the current row, using:
m = 9,                    // modulo = 9 and
a = x - a, b = a + 2      // range = [floor(x / 3) .. floor(x / 3) + 2]
) &                         //
t(j + 1) &                  // test the middle box in the current row
t(j + 2) &                  // test the right box in the current row
t(i, a = 0, b = 8)          // finally test the current box, using:
)                             // modulo = 9 (unchanged) and
)                               // range = [0 .. 8] (thus testing the entire box)
)                                 //


### Demo

let f =

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))

console.log(f([
"000340002",
"740000003",
"800170000",
"904700103",
"050000070",
"000640000",
"007630000",
"005000910",
"000520700"
]));

(%)=mod
x!y=x-x%y
f a=[[j|j<-[1..9],and[a!!k/=j|k<-[i!3-i!9%27+p%3+p!3*3|p<-[0..8]]++[i!9..i!9+8]++[i%9,i%9+9..80]],a!!i<1]|i<-[0..80]]


Defines a function f from lists of 81 Ints to lists of lists of Ints;

IO is like orlp's answer, except it uses [0,1,2,3,4,5,6,7,8,9] instead of ".123456789".

dianne saved a couple of bytes.

## JavaScript (ES6), 185 bytes

a=>a.map((b,r)=>b.map((d,c)=>d.map((e,i)=>e.map((g,j)=>[1,2,3,4,5,6,7,8,9].filter(v=>a.every(b=>b[c].every(e=>e[j]-v))&b.every(d=>d[i].every(g=>g-v))&d.every(e=>e.every(g=>g-v))&!g)))))


Takes as input an array of three rows of an array of three columns of a three by three array of cells of integers, and returns a five-dimensional array where all the integers have been replaced by arrays.