Sudoku Nhị Phân

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

1. Ràng buộc parity: mỗi hàng, cột, và ô $3\times 3$ phải có số bit $1$ chẵn.
2. 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$).
3. 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$ ($imod3=2$, $jmod3=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ả: $dp[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)$