Solve a Sudoku Grid
A Sudoku puzzle is given as board, an array of 9 strings of 9 characters each. Digits 1-9 are given clues and . marks an empty cell.
Fill every empty cell so that each row, each column and each of the nine 3x3 boxes contains every digit 1-9 exactly once. Every puzzle in the tests has exactly one solution. Return the solved board in the same format.
Plain backtracking can be slow on sparse puzzles; filling the cell with the fewest possible digits first keeps the search small.
Example 1
Input: board = ["27..1.5.3",".3.92.6..","1...4....","7..2.6...","...1.5479","3.147....","51.3.4...",".2.8..39.","943...85."] Output: ["279618543","435927618","186543927","794286135","862135479","351479286","518394762","627851394","943762851"]
Example 2
Input: board = [".48.5....","71.......","2..7.34..","437...6..",".62......","..91.23.7","6....1...","8.4.9..31","32.....6."] Output: ["948256173","713948526","256713498","437589612","162437859","589162347","695321784","874695231","321874965"]
Constraints
- board.length == 9
- board[i].length == 9
- Each puzzle has exactly one solution.
Hint 1
Track the digits used in every row, column and box as bit masks.
Hint 2
At each step choose the empty cell with the fewest candidate digits, try each candidate, and undo it if the search fails.
Discussion 0
Join free to post in the discussion.
Good practice for: Game Developer, Frontend Developer, Mobile App Developer, AI Engineer (LLM & Generative AI), Automation Test Engineer
Run checks your code on 2 sample tests. Submit runs all 7 tests, including hidden ones, and earns points. Use console.log to debug. Python's first run can take a few seconds while it starts.