Hướng dẫn giải của Sudoku Nhị Phân

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Sudoku Nhị Phân

Hướng tiếp cận

Quy hoạch động trên lưới $9 \times 9$ , duyệt từng ô theo thứ tự hàng-cột, theo dõi tính chẵn lẻ (parity) của các cột, ô $3 \times 3$ và hàng hiện tại.

Nhận xét quan trọng

Ràng buộc parity: mỗi hàng, cột, và ô $3 \times 3$ phải có số bit $1$ chẵn.
Lưới chỉ $9 \times 9$ nên trạng thái DP khả thi: parity 9 cột ( $2^{9} = 512$ ), parity 3 ô trong hàng ô hiện tại ( $2^{3} = 8$ ), parity hàng hiện tại ( $2^{1} = 2$ ).
Tổng trạng thái: $512 \times 8 \times 2 = 8192$ — rất nhỏ.

Thuật toán

Duyệt 81 ô theo thứ tự. Tại mỗi ô $(i, j)$ :

Thử giữ nguyên hoặc đảo bit (chi phí 0 hoặc 1).
Cập nhật parity cột $j$ , parity ô $3 \times 3$ chứa $(i, j)$ , và parity hàng $i$ .
Kiểm tra ràng buộc tại ranh giới:
- Cuối hàng ( $j = 8$ ): parity hàng phải bằng 0.
- Cuối hàng cuối của ô $3 \times 3$ ( $i mod 3 = 2$ , $j mod 3 = 2$ ): parity ô phải bằng 0.
- Ô cuối cùng ( $i = 8, j = 8$ ): tất cả parity cột phải bằng 0.

Kết quả: $d p [0] [0] [0]$ sau khi xử lý hết 81 ô.

Độ phức tạp

Thời gian: $O (81 \times 2^{9} \times 2^{3} \times 2 \times 2) = O (81 \times 16384) \approx 1.3 \times 10^{6}$
Bộ nhớ: $O (2^{9} \times 2^{3} \times 2) = O (8192)$

Bình luận

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