SudokuTypo
SRM 806 · 2021-05-24 · by misof
Problem Statement
As you probably know, Sudoku is a pen-and-paper puzzle in which your goal is to fill the cells in a 9x9 square. In the end, each cell must contain one of the digits 1 to 9 in such a way that:
- in each row each of the digits appears exactly once
- in each column each of the digits appears exactly once
- in each of the nine large 3x3 squares (as shown below) each of the digits appears exactly once
Below is an example of a correctly solved Sudoku. You can verify that, for example, in the first row (861234957), in the second column (672513948) and in the bottom right 3x3 square (731825496) each of the digits 1-9 appears exactly once.
+---+---+---+ |861|234|957| |479|561|283| |325|978|164| +---+---+---+ |958|143|672| |712|856|349| |634|729|518| +---+---+---+ |596|482|731| |143|697|825| |287|315|496| +---+---+---+
Simon has just finished solving a Sudoku puzzle.
You are given the
Sadly, Simon got careless and made exactly one mistake: he wrote an incorrect digit into one of the cells. Find the mistake and return the correct digit he should have written instead of the incorrect one.
Constraints
- digits will contain exactly 81 elements.
- Each element of digits will be one of the digits 1 to 9.
- digits will be exactly one mistake away from a solved Sudoku.
{8,6,1,2,3,4,9,5,3,
4,7,9,5,6,1,2,8,3,
3,2,5,9,7,8,1,6,4,
9,5,8,1,4,3,6,7,2,
7,1,2,8,5,6,3,4,9,
6,3,4,7,2,9,5,1,8,
5,9,6,4,8,2,7,3,1,
1,4,3,6,9,7,8,2,5,
2,8,7,3,1,5,4,9,6}
Returns: 7
The example Sudoku from the problem statement. The typo is in the top right corner where Simon wrote a 3 instead of a 7. (E.g., we can see two 3s on top of each other in the last column.)
{8,6,1,2,3,4,9,5,7,
4,7,9,5,6,1,2,8,3,
3,2,5,9,7,8,1,6,4,
9,5,8,1,4,3,6,7,2,
7,1,2,8,1,6,3,4,9,
6,3,4,7,2,9,5,1,8,
5,9,6,4,8,2,7,3,1,
1,4,3,6,9,7,8,2,5,
2,8,7,3,1,5,4,9,6}
Returns: 5
This time the mistake is exactly in the middle of the grid: instead of the correct 5 Simon wrote a 1 there.
{5,3,4,6,7,8,9,1,2,
6,7,2,1,9,5,3,4,8,
1,9,8,3,4,2,5,6,7,
8,5,9,7,6,1,4,2,3,
4,2,6,8,5,3,7,9,1,
7,1,3,9,2,4,8,5,6,
9,6,1,5,3,7,2,8,4,
2,8,7,4,1,9,1,3,5,
3,4,5,2,8,6,1,7,9}
Returns: 6
The mistake here is in the second row from the bottom, third column from the right.
{5, 3, 8, 1, 2, 9, 7, 6, 7, 9, 6, 4, 5, 8, 7, 3, 1, 2, 1, 7, 2, 6, 3, 4, 8, 9, 5, 3, 4, 5, 7, 9, 8, 1, 2, 6, 6, 8, 9, 2, 1, 5, 4, 7, 3, 7, 2, 1, 4, 6, 3, 9, 5, 8, 8, 1, 3, 9, 5, 2, 6, 4, 7, 2, 9, 7, 3, 4, 6, 5, 8, 1, 4, 5, 6, 8, 7, 1, 2, 3, 9}
Returns: 4
{5, 3, 8, 1, 2, 9, 7, 6, 4, 9, 6, 4, 5, 8, 7, 3, 1, 2, 1, 7, 2, 6, 3, 4, 8, 9, 5, 3, 4, 5, 7, 9, 8, 1, 2, 6, 6, 8, 9, 2, 1, 5, 4, 7, 3, 7, 2, 1, 4, 6, 3, 9, 5, 8, 8, 1, 3, 9, 5, 2, 6, 4, 7, 2, 9, 7, 3, 4, 6, 5, 8, 1, 4, 6, 6, 8, 7, 1, 2, 3, 9}
Returns: 5
Submissions are judged against all 35 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class SudokuTypo with a public method int fix(vector<int> digits) · 35 test cases · 2 s / 256 MB per case