Solve Sudoku by Cross-Hatching
InterviewTime limit1sMemory limit128 MB
Simulate repeated Sudoku cross-hatching (single-candidate-per-box scan) on a given grid, filling cells until no more moves apply, and detect rule violations or contradictions.
- Level
Medium4 of 10
- Topics
- Simulation, Matrix, Implementation
- Solved
- No attempts yet
Problem
Sudoku is a puzzle played on a 9 by 9 grid. The digits from 1 to 9 must appear exactly once in every row, every column, and every 3 by 3 box.
For this problem, you may use only cross-hatching. In cross-hatching, choose one digit, then exclude every row, column, and 3 by 3 box where that digit already appears. If a 3 by 3 box has exactly one empty cell where the chosen digit can still go, fill that cell with the digit.
You are given a partially filled Sudoku puzzle. Repeatedly apply only cross-hatching until no more cells can be filled by this method, then print the resulting grid. You must not fill cells by any other method.
The input puzzle may already violate Sudoku rules, or it may contain a contradiction where some required digit has no legal cell in a row, column, or 3 by 3 box. These cases must also be detected.
Input
The input consists of 9 lines. Each line has 9 characters, and each character is either a digit from 1 to 9 or .. A period represents an empty cell.
Output
If the puzzle follows Sudoku rules and has no contradiction, print the grid after applying only cross-hatching, using the same 9-line format as the input. Otherwise, print ERROR.