trang chủ / đề bài / icpc23_nat_c

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 9×9 được chia thành 9 vùng kích thước 3×3. Người chơi phải điền vào mỗi ô một chữ số từ 1 đến 9 (tính cả hai đầu mút) sao cho mỗi hàng, mỗi cột và mỗi vùng 3×3 trong chín vùng đều chứa đủ các chữ số từ 1 đến 9.

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ừ ô (xu,yu) tới ô (xv,yv) 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ừ ô (xu,yu) tới ô (xv,yv) 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 ô (1,1) và (3,3) thuộc cùng một vùng 3×3 nhưng chứa cùng một chữ số.
  • Quân mã có thể đi từ ô (1,4) tới ô (2,2) nhưng hai ô này chứa cùng một chữ số.
  • Quân vua có thể đi từ ô (3,3) tới ô (4,4) nhưng hai ô này chứa cùng một chữ số.

Nhắc lại, gọi (i,j) là ô ở hàng thứ i và cột thứ j:

  • quân mã đi được từ ô (xu,yu) tới ô (xv,yv) trong một bước khi và chỉ khi (xu−xv)2+(yu−yv)2=5;
  • quân vua đi được từ ô (xu,yu) tới ô (xv,yv) trong một bước khi và chỉ khi max((xu−xv)2,(yu−yv)2)=1.

Dữ liệu vào

Gồm 9 dòng, mỗi dòng chứa đúng 9 chữ số, mô tả bảng Sudoku Cờ Vua đã cho. Ô trống được biểu diễn bằng chữ số 0. Có không quá 2 chữ số khác 0, đó 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 9 dòng, mỗi dòng gồm đúng 9 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 9×9, mỗi ô chứa một chữ số từ 0 đến 9.
  • Có không quá 2 ô chứa chữ số khác 0.

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ố 1, 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 ô (4,4) và (6,6) cùng thuộc một vùng 3×3 và đều chứa chữ số 6.
000000000
000000000
000000000
000000000
000000000
000000000
000000700
000007000
000000000
NO SOLUTION Quân vua đi được từ ô (7,7) tới ô (8,6), mà hai ô này đều chứa chữ số 7.
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

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0