Phân tích: Minesweeper Master

Có nhiều cách để tạo ra một cấu hình mìn hợp lệ. Trong bài phân tích này, chúng tôi sẽ cố gắng liệt kê tất cả các trường hợp có thể xảy ra và tạo cấu hình hợp lệ cho từng trường hợp (nếu tồn tại). Sau đó, sau khi có cái nhìn sâu sắc hơn, chúng tôi sẽ cung cấp một thuật toán dễ cài đặt hơn để tạo cấu hình mìn hợp lệ.

Liệt kê tất cả các trường hợp có thể xảy ra

Chúng ta bắt đầu bằng cách kiểm tra các trường hợp tầm thường:

• Nếu chỉ có một ô trống, chúng ta có thể lấp đầy tất cả các ô bằng mìn ngoại trừ ô mà bạn nhấp vào.
• Nếu \(R = 1\) hoặc \(C = 1\), các quả mìn có thể được đặt từ trái sang phải hoặc từ trên xuống dưới tương ứng, và nhấp vào ô ở tận cùng bên phải hoặc tận cùng bên dưới.

Nếu bảng không nằm trong hai trường hợp tầm thường trên, điều đó có nghĩa là bảng có kích thước ít nhất \(2 \times 2\). Khi đó, chúng ta có thể kiểm tra thủ công rằng:

• Nếu số lượng ô trống là 2 hoặc 3, thì "Impossible" (không thể) có cấu hình hợp lệ.
• Nếu \(R = 2\) hoặc \(C = 2\), cấu hình hợp lệ chỉ tồn tại nếu \(M\) là số chẵn. Ví dụ, nếu \(R = 2, C = 7\) và \(M = 5\), điều đó là không thể vì \(M\) là số lẻ (số ô trống cũng lẻ). Tuy nhiên, nếu \(M = 6\), chúng ta có thể đặt mìn ở phần bên trái của bảng và nhấp vào góc dưới bên phải, như thế này:

            ***....
            ***...c

Nếu bảng không nằm trong bất kỳ trường hợp nào ở trên, điều đó có nghĩa là bảng có kích thước ít nhất \(3 \times 3\). Trong trường hợp này, chúng ta luôn có thể tìm thấy một cấu hình mìn hợp lệ nếu số lượng ô trống lớn hơn hoặc bằng 9 (thực tế là \(\ge 8\) và không phải là 9). Đây là một cách để thực hiện:

• Nếu số lượng ô trống bằng hoặc lớn hơn \(3 \times C\), thì các quả mìn có thể được đặt theo từng hàng từ trên xuống dưới. Nếu số lượng mìn còn lại có thể lấp đầy toàn bộ hàng hoặc ít hơn \(C - 2\) thì đặt mìn từ trái sang phải trong hàng đó. Ngược lại, nếu số lượng mìn còn lại chính xác là \(C - 1\), hãy đặt quả mìn cuối cùng ở hàng tiếp theo. Ví dụ:

            ******        ******
            *****.        ****..
            ......   ->   *.....
            ......        ......
            .....c        .....c

• Nếu số lượng ô trống ít hơn \(3 \times C\) nhưng ít nhất là 9, trước tiên chúng ta lấp đầy tất cả các hàng bằng mìn ngoại trừ 3 hàng cuối cùng. Đối với 3 hàng cuối cùng, chúng ta điền các quả mìn còn lại theo từng cột từ cột ngoài cùng bên trái. Nếu số mìn còn lại ở cột cuối cùng là 2, thì quả mìn cuối cùng phải được đặt ở cột tiếp theo. Ví dụ:

            ******        ******
            **....   ->   ***...
            **....        *.....
            *....c        *....c

Bây giờ, chúng ta còn lại tối đa 9 ô trống nằm trong hình vuông \(3 \times 3\) ở góc dưới bên phải. Trong trường hợp này, chúng ta có thể kiểm tra bằng tay rằng nếu số lượng ô trống là 5 hoặc 7, thì không thể có cấu hình mìn hợp lệ. Ngược lại, chúng ta có thể viết mã cứng (hard-code) một cấu hình hợp lệ cho mỗi số lượng ô trống trong hình vuông \(3 \times 3\) đó.

Phù... có quá nhiều trường hợp cần bao phủ! Làm thế nào để chúng ta tự tin rằng khi lập trình, chúng ta không bỏ sót bất kỳ trường hợp đặc biệt nào?

Cách tiếp cận Duyệt (Brute-force)

Đối với Small dataset, kích thước bảng tối đa là \(5 \times 5\). Chúng ta có thể kiểm tra tất cả \(\binom{25}{M}\) cấu hình mìn có thể và tìm một cấu hình hợp lệ (tức là nhấp vào một ô trống trong cấu hình đó sẽ mở ra tất cả các ô trống khác). Để kiểm tra xem một cấu hình mìn có hợp lệ hay không, chúng ta có thể chạy thuật toán loang (flood-fill) hoặc tìm kiếm theo chiều rộng (BFS) đơn giản từ ô trống được nhấp và xác minh rằng tất cả các ô trống khác đều có thể tiếp cận được. Lưu ý rằng chúng ta cũng nên kiểm tra tất cả các vị trí nhấp chuột có thể. Cách tiếp cận duyệt này đủ nhanh cho Small dataset.

Cách tiếp cận duyệt có thể được sử dụng để kiểm tra (với các giá trị \(R, C, M\) nhỏ) xem có lỗi "false-negative" nào trong chiến lược liệt kê của chúng ta ở trên hay không. Một lỗi false-negative được tìm thấy khi tồn tại một cấu hình mìn hợp lệ, nhưng chiến lược liệt kê lại trả về "Impossible". Khi chúng ta tin tin rằng chiến lược liệt kê của mình không tạo ra bất kỳ lỗi false-negative nào, chúng ta có thể sử dụng nó để giải quyết Large dataset.

Cách tiếp cận dễ cài đặt hơn

Sau khi thử nghiệm với một vài cấu hình mìn hợp lệ bằng chiến lược liệt kê ở trên, bạn có thể nhận thấy một quy luật: trong một cấu hình mìn hợp lệ, số lượng mìn trong một hàng cụ thể luôn lớn hơn hoặc bằng số lượng mìn của các hàng bên dưới nó và tất cả các quả mìn đều được căn lề trái trong một hàng. Với hiểu biết này, chúng ta có thể cài đặt một thuật toán quay lui (backtracking) đơn giản để đặt mìn theo từng hàng từ trên xuống dưới với số lượng mìn không tăng khi chúng ta tiến hành điền vào hàng tiếp theo, và cắt tỉa nếu cấu hình cho hàng hiện tại không hợp lệ (có thể kiểm tra bằng cách nhấp vào ô dưới cùng bên phải). Thuật toán quay lui có cắt tỉa này có thể xử lý bảng kích thước lên đến \(50 \times 50\) trong thời gian hợp lý và dễ cài đặt hơn (tức là không cần liệt kê các trường hợp đặc biệt/tricky).

Nếu thời gian thi đấu ngắn hơn, chúng ta có thể không có đủ thời gian để liệt kê tất cả các trường hợp có thể. Trong trường hợp này, đặt cược vào thuật toán quay lui (hoặc bất kỳ thuật toán nào khác dễ cài đặt hơn) có thể là một ý tưởng hay. Tìm kiếm những thuật toán như vậy là một nghệ thuật :).

Dựa trên phân tích chính thức của Google Code Jam.