Sudoku Cờ Vua
Đề bài
Mô tả
Khi rảnh rỗi, Chikapu thích chơi Sudoku, một trò chơi logic trên lưới được chia thành vùng kích thước . Người chơi phải điền vào mỗi ô một chữ số từ đến (tính cả hai đầu mút) sao cho mỗi hàng, mỗi cột và mỗi vùng trong chín vùng đều chứa đủ các chữ số từ đến .
Chikapu cũng thích cờ vua. Cô đã thiết kế một biến thể mới của Sudoku truyền thống và đặt tên là Sudoku Cờ Vua. Ngoài các luật Sudoku thông thường, một bảng Sudoku Cờ Vua hợp lệ còn phải thỏa mãn các yêu cầu sau:
- Nếu quân mã có thể đi từ ô tới ô trong một bước, hai chữ số trong hai ô này phải khác nhau.
- Tương tự, nếu quân vua có thể đi từ ô tới ô trong một bước, hai chữ số trong hai ô này cũng phải khác nhau.
Chikapu có một bảng Sudoku Cờ Vua, trên đó cô đã viết sẵn một số chữ số. Nhiệm vụ của bạn là điền vào các ô trống để được một bảng Sudoku Cờ Vua hợp lệ.
Một vài ví dụ về bảng Sudoku Cờ Vua không hợp lệ:
- Hai ô và thuộc cùng một vùng nhưng chứa cùng một chữ số.
- Quân mã có thể đi từ ô tới ô nhưng hai ô này chứa cùng một chữ số.
- Quân vua có thể đi từ ô tới ô nhưng hai ô này chứa cùng một chữ số.
Nhắc lại, gọi là ô ở hàng thứ và cột thứ :
- quân mã đi được từ ô tới ô trong một bước khi và chỉ khi ;
- quân vua đi được từ ô tới ô trong một bước khi và chỉ khi .
Dữ liệu vào
Gồm dòng, mỗi dòng chứa đúng chữ số, mô tả bảng Sudoku Cờ Vua đã cho. Ô trống được biểu diễn bằng chữ số . Có không quá chữ số khác , đó là các ô đã được điền sẵn.
Dữ liệu ra
Nếu không thể tạo được một bảng Sudoku Cờ Vua hợp lệ với các ô điền sẵn này, in ra một dòng duy nhất: NO SOLUTION.
Ngược lại, in ra đúng dòng, mỗi dòng gồm đúng chữ số, mô tả một bảng Sudoku Cờ Vua hợp lệ (giữ nguyên các ô điền sẵn). Nếu có nhiều lời giải, in ra lời giải bất kỳ.
Ràng buộc
- Bảng có kích thước , mỗi ô chứa một chữ số từ đến .
- Có không quá ô chứa chữ số khác .
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 100000000 100000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 |
NO SOLUTION | Hai ô điền sẵn cùng nằm trên một cột nhưng đều chứa chữ số , vi phạm luật Sudoku, nên không thể tạo được bảng hợp lệ. |
| 000000000 000000000 000000000 000600000 000000000 000006000 000000000 000000000 000000000 |
NO SOLUTION | Hai ô và cùng thuộc một vùng và đều chứa chữ số . |
| 000000000 000000000 000000000 000000000 000000000 000000000 000000700 000007000 000000000 |
NO SOLUTION | Quân vua đi được từ ô tới ô , mà hai ô này đều chứa chữ số . |
| 100000000 000000000 000000000 000000000 000000000 000000000 000000000 000000000 000000009 |
123456798 456798123 798123456 234567981 567981234 981234567 345679812 679812345 812345679 |
Ví dụ bổ sung. Đây là một bảng hợp lệ giữ nguyên hai ô điền sẵn; mọi bảng hợp lệ khác giữ nguyên hai ô đó cũng được chấp nhận. |
Bình luận