Sudoku Solver
Updated
Problem statement
You are given a Sudoku puzzle as a 9 x 9 grid board. A cell holds a digit from '1' to '9', or '.' if it is empty.
Fill in every empty cell so that each row, each column and each of the nine 3 x 3 boxes contains every digit from 1 to 9 exactly once. The boxes are the nine blocks you get by cutting the grid after every third row and every third column. Digits that are already on the board must stay where they are.
Return the completed board. The puzzle always has exactly one solution.
Function
solveSudoku(board: char[][]) → char[][]Examples
Example 1
board = [["3","8",".",".",".","9",".","5","1"],["9",".","5","1","2","7",".","4","3"],[".",".",".","8","3",".",".",".","."],[".",".","4","9","8","6",".","7","."],[".","2","6","7","4",".","9","1","."],["8","9","7",".",".",".","4","3","."],["6",".",".",".",".",".","1","2","."],[".",".",".",".",".","8",".",".","7"],["7","1",".","6","9",".","5",".","4"]]return = [["3","8","2","4","6","9","7","5","1"],["9","6","5","1","2","7","8","4","3"],["4","7","1","8","3","5","6","9","2"],["1","3","4","9","8","6","2","7","5"],["5","2","6","7","4","3","9","1","8"],["8","9","7","2","5","1","4","3","6"],["6","5","8","3","7","4","1","2","9"],["2","4","9","5","1","8","3","6","7"],["7","1","3","6","9","2","5","8","4"]]Rows are counted from 1 at the top and columns from 1 at the left. Row 2 is missing only 6 and 8, and its empty cells are in columns 2 and 7. Column 2 already has an 8 (in row 1), so row 2, column 2 must be 6, and row 2, column 7 gets 8.
Working through the other empty cells the same way, with some trial and error, gives the board shown. Every row, column and box of it holds 1 to 9 once, and every given digit is kept.
Example 2
board = [[".","7","1","3","2","5","8","6","9"],["2","9","6","1","8","4","7","3","5"],["5","3","8","6","9","7","1","4","2"],["8","5","7","2","1","6","3","9","4"],["3","1","9","4",".","8","6","2","7"],["6","2","4","7","3","9","5","1","8"],["1","8","5","9","4","3","2","7","6"],["7","4","3","8","6","2","9","5","1"],["9","6","2","5","7","1","4","8","."]]return = [["4","7","1","3","2","5","8","6","9"],["2","9","6","1","8","4","7","3","5"],["5","3","8","6","9","7","1","4","2"],["8","5","7","2","1","6","3","9","4"],["3","1","9","4","5","8","6","2","7"],["6","2","4","7","3","9","5","1","8"],["1","8","5","9","4","3","2","7","6"],["7","4","3","8","6","2","9","5","1"],["9","6","2","5","7","1","4","8","3"]]Only three cells are empty. Row 1 is missing only 4, row 5 is missing only 5, and row 9 is missing only 3. Each empty cell gets the one digit its row is missing.
Example 3
board = [["5","9","8","3","4","2","7","6","1"],["6","4","2","7","8","1","9","3","5"],["3","7","1","9","6","5","2","8","4"],["4","6","7","8","5","3","1","2","9"],[".",".",".",".",".",".",".",".","."],["1","5","9","2","7","6","8","4","3"],["2","1","6","5","3","8","4","9","7"],["9","3","4","1","2","7","6","5","8"],["7","8","5","6","9","4","3","1","2"]]return = [["5","9","8","3","4","2","7","6","1"],["6","4","2","7","8","1","9","3","5"],["3","7","1","9","6","5","2","8","4"],["4","6","7","8","5","3","1","2","9"],["8","2","3","4","1","9","5","7","6"],["1","5","9","2","7","6","8","4","3"],["2","1","6","5","3","8","4","9","7"],["9","3","4","1","2","7","6","5","8"],["7","8","5","6","9","4","3","1","2"]]All of row 5 is empty. Every column already has eight digits, so each cell in row 5 gets the one digit its column is missing. For example, column 1 has 5, 6, 3, 4, 1, 2, 9, 7, so row 5, column 1 is 8. Doing this for all nine columns gives row 5 as 8, 2, 3, 4, 1, 9, 5, 7, 6.
Constraints
board.length == 9board[i].length == 9- Each
board[i][j]is a digit from'1'to'9', or'.'for an empty cell. - The given digits never repeat in a row, column or box, and the puzzle has exactly one solution.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Distance Sums to Special Nodes in a Weighted TreeONSITE INTERVIEW · Seen Aug 2021
Similar questions at other companies
- Sudoku Puzzle SolverConfluent · PHONE SCREEN · ONSITE INTERVIEWConfluent interview questions
- Solve a Sudoku BoardZipRecruiter · ONSITE INTERVIEWZipRecruiter interview questions
- Sudoku SolverInMobi · PHONE SCREENInMobi interview questions
- Word SearchBloomberg LP · OA · PHONE SCREEN · ONSITE INTERVIEWBloomberg LP interview questions
- Rectangle Point Coverage CountsOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Word SearchAmazon · ONSITE INTERVIEW
- Validate Rectangular Game PiecesGoogle · ONSITE INTERVIEWGoogle interview questions
- Set Matrix ZeroesMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Enumerate Character Paths to a MarkerTesla · ONSITE INTERVIEWTesla interview questions
- Enumerate Right-and-Down Matrix PathsOracle · ONSITE INTERVIEWOracle interview questions