Bài toán con mã đi tuần

[rollover79]

Giải trí 1 chút với bài toán con mã đi tuần. Ý nghĩa các nút trên bàn cờ như sau:
1. Reset: Xóa hết các nước con mã đã đi.
2. Random: Xóa hết các nước con mã đã đi và đặt ngẫu nhiên con mã vào 1 vị trí bất kỳ trên bàn cờ.
3. Run: Tìm đường đi cho con mã lần lượt từ 1 cho đến 63 và điền số thứ tự bước đi vào các ô trên bàn cờ.

Chúc các bạn vui vẻ!

 

[Po_Pikachu]

Bác có thể chỉ quy luật và giải đáp lệnh trong nút Run được không? Em nhìn hoài sao không hiểu gì hết? Thân

 

[rollover79]

Thuật toán của bài này thì có nhiều, nhưng đây có lẽ là thuật toán nhanh nhất vì không phải quay lui hoặc vét cạn. Quy luật của nó là tại 1 ô, tìm ô đi tiếp theo của con mã là 1 trong 8 ô mà con mã có thể đi, nhưng tìm ra ô nào có số bước đi tiếp theo là nhỏ nhất. Trong cái hàm Run là tôi lần lượt tìm ra 63 nước đi tiếp theo của con mã, cứ tại 1 ô thì tìm đến 8 ô con mã có thể đi tiếp theo, trong số 8 ô đó, ô nào có số nước đi tiếp theo là nhỏ nhất thì đó sẽ là ô cần đi, sau khi đi đến đấy rồi lại xét tiếp.

 

[chibi]

Hay. Đây là lần đầu tiên mình biết đến thuật toán này dùng để giải bài "Mã đi tuần". Có rất nhiều diễn đàn nói về bài toán này và đã đưa ra thuật toán để giải nó.

 

[Po_Pikachu]

File của bác thật sự rất hay! Nhưng em thấy hình như có lỗi thì phải! Bác thử bấm vào nút Run hai hoặc ba lần xem sẽ có 1 vài số không được hiện ra hoặc không đúng chu kỳ. Em đã bổ sung thêm tính năng phát hiện ô trống. Nhưng điều lạ là khi bấm vào Radom/Run tiếp thì không phát hiện ra hiện tượng trên => chỉ có lệnh Run lần đầu là thoả điều kiện thôi! Không biết tại sao nhỉ? Bác xem file nha!

 

[rollover79]

File của bác thật sự rất hay!
Nhưng em thấy hình như có lỗi thì phải! Bác thử bấm vào nút Run hai hoặc ba lần xem sẽ có 1 vài số không được hiện ra hoặc không đúng chu kỳ. Em đã bổ sung thêm tính năng phát hiện ô trống. Nhưng điều lạ là khi bấm vào Radom/Run tiếp thì không phát hiện ra hiện tượng trên => chỉ có lệnh Run lần đầu là thoả điều kiện thôi! Không biết tại sao nhỉ?
Bác xem file nha!

Cảm ơn bạn, đúng là code có một lỗi nghiêm trọng , đó là hàm Run 2 tham số iRow và iCol phải là tham trị chứ không phải tham biến, code hiện tại tôi không khai báo tường minh mà để mặc định, và VBA hiểu mặc định là tham biến, do đó sau mỗi lần Run thì 2 biến iCurrentRow và iCurrentCol đã bị thay đổi không còn đúng vị trí con mã đang đứng nữa, dẫn tới kết quả không chính xác. Vậy code này xin sửa lại phần tham số của hàm Run, khai báo lại là tham trị

Sub Run([COLOR=Red]ByVal [/COLOR]iRow As Integer, [COLOR=Red]ByVal [/COLOR]iCol As Integer)

Ngoài ra code tại hàm Run cũng còn 1 điểm chưa được chính xác, đó là phép so sánh tìm ô tiếp theo có số đường đi nhỏ nhất, hiện tại tôi đang để phép so sánh nhỏ hơn(<), xin sửa lại thành nhỏ hơn hoặc bằng (<=) thì mới chính xác như sau.

If GetWay(iRowTemp, iColTemp) <[COLOR=Red]=[/COLOR] iWay Then

Xin gửi lại file sau khi đã sửa.

 

[Po_Pikachu]

Mình gửi file đã sữa đúng rồi nè! Bạn gửi nhầm file rồi! Thân.

 

[chibi]

...Quy luật của nó là tại 1 ô, tìm ô đi tiếp theo của con mã là 1 trong 8 ô mà con mã có thể đi, nhưng tìm ra ô nào có số bước đi tiếp theo là nhỏ nhất. ....

roll có thể giải thích rõ thêm được không?

 

[rollover79]

roll có thể giải thích rõ thêm được không?

Tức là thuật toán của nó là thế này, tại 1 thời điểm con mã có thể đi được 8 nước đi quanh nó, quy luật bước đi của con mã thì chắc bạn rõ rồi. Giả sử 8 ô mà con mã có thể đi tới lần lượt là X1, X2, ... X8(dĩ nhiên ta chỉ xét tới những ô hợp lên trong bàn cờ, và những ô mà con mã chưa đi), thì khi đó ta sẽ xét lần lượt trong 8 ô đó, ô nào mà con mã có thể đi tiếp được ít nước nhất thì ô đó là ô mà con mã phải đi tới. Có thể đi tiếp ở đây tức là tại ô Xn con mã có thể đi được những nước nào(trong bàn cờ và con mã chưa đi qua).

 

[chibi]

Ý mình hỏi trong phần chữ màu đỏ ở trên. Tại sao lại là ô có số nước đi tiếp theo ít nhất ?

 

[rollover79]

Ý mình hỏi trong phần chữ màu đỏ ở trên. Tại sao lại là ô có số nước đi tiếp theo ít nhất ?

Cái này là dựa trên thuật toán heuristic, bạn tìm hiểu thêm về thuật toán này sẽ rõ nhé.

 

[phuongtam81]

Mình chẳng hiểu gì cả.