8
1
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 code-golf. 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.
Additional Notes:
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.
driima
Posted 2016-10-04T16:16:41.400
Reputation: 451
How flexible is the input format? Could it be for instance an array of 9 strings? (such as
["000340002", "740000003", ...]) – Arnauld – 2016-10-04T16:30:58.517Input is flexible, refer to the changes I made in my question rules. – driima – 2016-10-04T16:36:25.783
Where you say "The result is to be in the form of a four-dimensional array containing the row, column, cell and possible numbers respectively" do you mean, "The result is to be in the form of a four-dimensional array containing the band, nonet, cell (ordered by row then column) and possible numbers respectively"? This seems to be what you have in your test case. – Jonathan Allan – 2016-10-04T16:57:11.810
1
Is a single string going left-to-right, top-to-bottom allowed as input? Like this? And output in the same order?
– orlp – 2016-10-04T17:07:56.553To expand on my suggestion, this is a fairly standard sudoku format supported by various software packages. – orlp – 2016-10-04T17:29:14.367
How are you determining which numbers are valid for each spot? The image and text output do not match, and the image is incorrect since it has 5 listed as a candidate where there is a 5 filled in (6th column from the left, 2nd row from the top) on the same column. – miles – 2016-10-04T19:28:27.360
The example output seems incorrect.
[1, 5, 6, 7, 8, 9]should be the output for x=1,y=2. (Or, do we have to consider the fact that the 7 can only be there?) – PurkkaKoodari – 2016-10-04T20:14:30.603@orlp Yes, I will allow that format.I will update my question with that. – driima – 2016-10-04T20:38:47.130
@miles Yes, the output and image do both appear to be incorrect. That's a mistake on my part. – driima – 2016-10-04T20:39:27.430
1If 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? – Peter Taylor – 2016-10-04T21:02:52.097
@PeterTaylor given a valid incomplete sudoku puzzle, retrieve all possible marks in all empty cells. – driima – 2016-10-04T21:08:04.640
1What is the distinction you're drawing between that and solving the puzzle? – Peter Taylor – 2016-10-04T21:14:00.127
@PeterTaylor Solving the puzzle means filling in the empty cells with the correct values, as opposed to retrieving all possible marks that can be placed within the empty cells. – driima – 2016-10-04T21:15:38.557
1So under what circumstances can an incorrect value be placed in a cell? Stop repeating yourself and start defining your terms. – Peter Taylor – 2016-10-05T07:14:23.683
@PeterTaylor Standard rules of Sudoku. A value is incorrect when the same value exists on the same cell row or column in the entire grid, or in any cell within the same 3x3 cells of the grid section. An incorrect value should never be placed in a cell, as was clearly mentioned in the question. – driima – 2016-10-05T07:33:48.397