Sudoku thường bao gồm $n$ ô vuông con kích thước $\sqrt{n} \times \sqrt{n}$ trong một lưới $n \times n$.
Mỗi hàng và mỗi cột phải chứa các số từ $1$ đến $n$, không được thiếu và không được lặp lại. Mỗi ô vuông con (vùng được bao quanh bởi đường kẻ đậm, thường là kích thước $\sqrt{n} \times \sqrt{n}$) cũng phải chứa các số từ $1$ đến $n$, không được thiếu và không được lặp lại. Một lời giải hoàn chỉnh phải thỏa mãn đồng thời cả ba điều kiện này.
Hình minh họa một ví dụ về Sudoku $n=9$.
Cho một đề bài Sudoku chưa hoàn chỉnh, yêu cầu điền thêm một số lượng tùy ý các con số sao cho sau khi điền, Sudoku đó chính xác có hai lời giải, tức là có duy nhất hai lời giải; đồng thời trong tất cả các cách điền như vậy, sự khác biệt giữa hai lời giải là lớn nhất. Ở đây, sự khác biệt được định nghĩa là số lượng các ô có giá trị khác nhau khi so sánh hai lời giải.
Đồng thời, với bất kỳ hai vị trí nào trong Sudoku, gọi $x_1, x_2$ là giá trị tại vị trí thứ nhất trong hai lời giải, $y_1, y_2$ là giá trị tại vị trí thứ hai trong hai lời giải, thì không đồng thời thỏa mãn $x_1 \neq x_2, y_1 \neq y_2, x_1 \neq y_2, x_1 \neq y_1$.
Dữ liệu vào
Dòng đầu tiên chứa một số $n$ biểu thị kích thước của Sudoku.
$n$ dòng tiếp theo, mỗi dòng chứa $n$ số $a_{i,j}$, biểu thị một đề bài Sudoku chưa hoàn chỉnh, vị trí có số $0$ nghĩa là ô đó chưa được điền số.
Dữ liệu ra
Xuất ra $n$ dòng, mỗi dòng $n$ số, biểu thị bảng đã được điền số. Nếu có nhiều cách điền thỏa mãn sự khác biệt giữa hai lời giải là lớn nhất, bạn có thể xuất ra bất kỳ cách nào.
Dữ liệu phạm vi
| :---: | :---: | :---: | :---: | :---: |
|---|---|---|---|---|
| 子任务编号 | 数据点编号 | 分值 | 数据范围 | 额外限制 |
| 1 | 1 | 8 | $n=4$ | 无 |
| 1 | 11 | 8 | $n=4$ | 无 |
| 1 | 12 | 8 | $n=4$ | 无 |
| 1 | 13 | 8 | $n=4$ | 无 |
| 2 | 2 | 6 | $n=9$ | 初始给定数字数量为 $0$ |
| 2 | 3 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 4 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 5 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 6 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 7 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 8 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 9 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 2 | 10 | 6 | $n=9$ | 保证盘面至多给出 $11$ 个不为 $0$ 的数 |
| 3 | 14 | 7 | $n=16$ | 初始给定数字数量为 $0$ |
| 4 | 15 | 7 | $n=16$ | 保证盘面至多给出 $20$ 个不为 $0$ 的数 |
Trong đó, Subtask 1 có giới hạn thời gian là 2s. Các Subtask khác có giới hạn thời gian là 30s.
Với mọi dữ liệu: $a_{i,j} \in [0, n]$, đảm bảo đề bài Sudoku chưa hoàn chỉnh đã cho có ít nhất một cách điền để tạo ra đúng hai lời giải.
Lưu ý: Bảng trên có thể hiển thị không rõ ràng trong chế độ nền tối (dark mode), bạn có thể chuyển sang chế độ nền sáng nếu cần.
Ví dụ
Dữ liệu vào 1
4 3 0 0 0 0 0 0 0 0 3 0 0 0 0 0 3
Dữ liệu ra 1
3 0 0 0 0 0 0 2 0 3 0 0 2 0 0 3
Ghi chú
Hai lời giải tương ứng với kết quả ví dụ trên là:
3 2 1 4 1 4 3 2 4 3 2 1 2 1 4 3
và:
3 2 4 1 4 1 3 2 1 3 2 4 2 4 1 3
So sánh từng ô, ta thấy sự khác biệt là $8$. Có thể chứng minh đây là một trong những cách đạt được giá trị khác biệt lớn nhất là $8$.
Dữ liệu vào 2
16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Dữ liệu vào 3
16 0 0 10 0 0 0 0 1 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 16 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 7 0 0 7 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 15 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 13 0 0 0 0 0 0 0 0 0 8 0 0 0 12 11