Cho bàn cờ 8×8. Mỗi ô là . nếu được phép đặt hậu hoặc * nếu bị cấm. Hãy đếm số cách đặt đúng tám quân hậu sao cho không có hai quân cùng hàng, cùng cột hoặc cùng đường chéo.
Ô bị cấm chỉ ngăn việc đặt hậu tại chính ô đó; nó không chặn đường tấn công giữa hai quân hậu.
Input
Gồm đúng 8 dòng, mỗi dòng có đúng 8 ký tự . hoặc *.
Output
In một số nguyên: số cách đặt hợp lệ.
Constraints
Bàn cờ luôn có kích thước 8×8.
Mỗi ký tự là . hoặc *.
Scoring
Subtask 1 (50%): Mỗi hàng có nhiều nhất 4 ô được phép.
Giải thích: Duyệt từng hàng, ta chỉ thử các cột chưa dùng, không trùng đường chéo và không phải ô *. Sau khi loại mọi nhánh vi phạm, còn đúng 50 cách đặt đủ tám quân hậu.
Lời giải tóm tắt
Ý tưởng: Xử lý các hàng từ trên xuống dưới và đặt đúng một hậu trong mỗi hàng. Trước khi đặt tại (row,column), kiểm tra ô không bị cấm, cột chưa dùng, đường chéo row-column+7 chưa dùng và đường chéo row+column chưa dùng.
Ý tưởng: Sau khi đánh dấu ba ràng buộc, đệ quy sang hàng tiếp theo rồi hoàn tác. Đạt hàng thứ tám nghĩa là đã tạo được một cấu hình hợp lệ.
Chứng minh tính đúng đắn: Mọi cấu hình hợp lệ có đúng một cột được chọn ở từng hàng. Khi thuật toán đi theo các cột của cấu hình đó, mỗi lựa chọn đều vượt qua kiểm tra vì cấu hình không dùng ô cấm và không có xung đột, nên cấu hình được sinh. Ngược lại, các mảng đánh dấu bảo đảm mọi lá có tám hậu khác cột và khác cả hai đường chéo; việc đệ quy theo hàng bảo đảm khác hàng. Dãy tám cột xác định duy nhất cấu hình, nên không có lần đếm trùng.
Độ phức tạp: Sau khi mỗi cột chỉ được dùng một lần, không gian tìm kiếm không vượt quá 8! hoán vị và còn được cắt sớm bởi đường chéo, nên thời gian O(8!); bộ nhớ phụ O(8) theo độ sâu đệ quy.