Solution

• Trước khi vào phần giải thuật chính của bài toán ta cần phải có một số nhận xét ban đầu

  Các nhận xét

• Thay vì quan tâm trang thái của các domino, chúng ta sẽ quan tâm vào vị trí của ô trống

• Tạo một đồ thị vô hướng gồm các đỉnh tượng trưng cho vị trí của ông trống hiện tại, cạnh giữa các đỉnh chính là việc chuyển trạng thái từ trạng thái này sang trạng thái khác khi di chuyển domino.

• Nhận xét quan trọng nhất chính là đồ thị chuyển trạng thái của các ô trống chính là một cây!

  Chứng minh quan trọng

• "Đồ thị chuyển trạng thái ô trống không tồn tại chu trình đơn và cũng chính là cây có gốc là trạng thái ban đầu"

• Xem điểm X chính là ô trống ban đầu, OO là domino, giả sử không quan tâm các trạng thái của các ô xung quanh, chỉ quan trọng xây dưng chu trình đơn và cách ô trống di chuyển.
• Đặt domino vào bên cạnh ô X thì ô X di chuyển tiếp vào đến duôi của domino vùa được đặt vào
• 
• Đặt thêm một domino và ô X tiếp tục di chuyển theo đuôi của domino tiếp theo
• 
• Ta nhận thấy rằng: để ô X quay về vị trí ban đầu, tức là phải đặt một domino sao cho đuôi của domino đó trùng với X, vậy nên ngay từ đầu X không phải ô trống! Hai điều này đối lập với nhau, vì vậy không thể tồn tại một chu trình đơn giữa các trạng thái ô trống.

• Đồ thị chuyển trạng thái liên thông, nhưng không tồn tại chu trình đơn nên đồ thị này chính là cây

  Lời giải cuối cùng

• Đầu tiền, xây dưng cây chuyển trạng thái của ô trống (gốc là trạng thái đầu tiên), tỉa bớt các lá của cây không chứa kho báu (trừ gốc) vì không cần thăm các nút đó.

• Bài toán trở thành bài toán di chuyển toàn bộ nút trên cây với số lần di chuyển ít nhất nhưng không cần quay về gốc.
• Để di chuyển qua toàn bộ các nút và quay về gốc thì cần ~2 * (n - 1)~ với ~n~ là số đỉnh của cây.
• Tuy nhiên trong bài toán này không cần quay về gốc nên cách tốt nhất sẽ là tham lam nút lá sâu nhất và thăm nút lá đó sau cùng.
• Vậy đáp án thời gian ít nhất của bài toán là ~2 * (n - 1) - maxDepth~ với ~maxDepth~ là độ sâu lớn nhất của một lá.