Loading...
Loading...
Loading...
Every Sunday, Ananya's newspaper prints a Sudoku. The 9 × 9 grid is split into nine 3 × 3 boxes, and some cells already hold digits. Fill every empty cell with a digit from 1 to 9 so that each row, each column and each 3 × 3 box holds every digit exactly once.
Every puzzle given has exactly one solution. Print the solved grid.
. for an empty cell.Example
Input
53..7.... 6..195... .98....6. 8...6...3 4..8.3..1 7...2...6 .6....28. ...419..5 ....8..79
Output
534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179
A typical newspaper puzzle with 30 given digits.
Try the problem first. Open one hint at a time.
Find an empty cell, try each digit 1 to 9 that does not break a rule, and solve the rest of the grid with that digit in place.
If no digit fits an empty cell, an earlier guess was wrong: clear the cell and go back.
Keep boolean tables rowHas[r][d], colHas[c][d] and boxHas[b][d], with box number b = (r / 3) * 3 + c / 3. Then each check is O(1).
Make the method return true when the grid is full, and stop at once when a call returns true, so the solution is not undone.
Write your Java code, run it on the examples and submit it to hidden tests.
Solve in the editor