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

16
2541

Bài viết hôm nay mình sẽ hướng dẫn các bạn cách giải bài toán mã đi tuần. Nào chúng ta cùng bắt đầu thôi !

Giới thiệu bài toán mã đi tuần

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

Mã đi tuần (hay hành trình của quân mã) là bài toán về việc di chuyển một quân mã trên bàn cờ vua (8 x 8). Quân mã được đặt ở một ô trên một bàn cờ trống nó phải di chuyển theo quy tắc của cờ vua để đi qua mỗi ô trên bàn cờ đúng một lần.

Nếu một quân mã đi hết 64 vị trí và tại vị trí cuối cùng có thể di chuyển đến vị trí bắt đầu thông qua một nước cờ thì đó gọi là một hành trình đóng

Có những hành trình, trong đó quân mã sau khi đi hết tất cả 64 ô của bàn cờ và từ ô cuối của hành trình không thể đi về ô xuất phát chỉ bằng một nước đi. Những hành trình như vậy được gọi là hành trình mở.

Ví dụ sau đây là một lời giải cho bài toán mã đi tuần trên bàn cờ 5×5 (hành trình mở).

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

Cách di chuyển của một quân mã

Nước đi của một quân mã giống hình chữ L và nó có thể di chuyển tất cả các hướng. Ở một vị trí thích hợp thì quân mã có thể di chuyển đến được 8 vị trí.

Cách mã di chuyển
Cách mã di chuyển

Hướng dẫn giải bài toán mã đi tuần

Xây dựng bước đi cho quân mã

Giọi x,y là độ dài bước đi trên các trục Oxy. Một bước đi hợp lệ của quân mã sẽ như sau: |x| + |y| = 3 ( Với x,y > 0).

Khi đó ở một vị trí bất kì quân mã có có 8 đường có thể di chuyển. Chưa xét đến bước đi đó có hợp lệ hay không.

Các bước đi đó là: ( -2, -1), ( -2, 1), ( -1, -2), ( -1, 2), ( 1, -2), ( 1, 2), ( 2, -1), ( 2, 1)

Để đơn giản ta sẽ tạo hay mảng X[], Y[] để chứa các giá trị trên. Với mỗi X[i], Y[i] sẽ là một cách di chuyển của quân mã(0 ≤i≤ 7 ).

Kiểm tra tính hợp lệ của bước đi

Ta sẽ dùng một mảng hai chiều A[n*n] để lưu vị trí của từng ô trong bàn cờ. Tất cả mảng đều khởi tạo giá trị là 0( quân mã chưa đi qua).

Giọi x,y là vị trí hiện tại của quân mã, thì vị trí tiếp theo mà quân mã đi sẽ có dạng x+X[i], y+Y[i]. Một vị trí được gọi là hợp lệ thì sẽ thỏa mãn tính chất sau:

  • 0 ≤ x+X[i]≤ n-1.
  • 0 ≤ x+X[i]≤ n-1.

Nếu bước đi đó là bước đi đúng thì ta sẽ lưu thứ tự của bước đi đó vào mảng A[ x+X[i], y+Y[i] ].

Giải bài toán mã đi tuần bằng đệ quy

Khởi tạo các giá trị ban đầu

Xây dựng hàm xuất mảng

Xây dựng hàm bước đi

Có lẽ hàm diChuyen() chính là hàm quan trọng nhất vì nó quyết định cách di chuyển của một quân mã. Ý tưởng của hàm là từ một vị trí ban đầu ta sẽ tìm một bước di chuyển hợp lệ và di chuyển đến vị trí đó. Tiếp tục tìm một bước đi và di chuyển tiếp đến khi không thể di chuyển được nữa (vào thế bí ) thì sẽ xóa bước đi đó. Chương trình chỉ dừng khi tìm được một hành trình hoặc đã thử di chuyển hết tất cả các bước đi nhưng vẫn không tìm thấy hành trình.

 

Nếu bạn muốn tìm một chu trình đóng thì các bạn cần lưu lại vị trí ban đầu. Ví dụ x_first, y_first sau đó kiểm tra như sau:

Bài viết của mình đến đây là kết thúc. Cám ơn các bạn đã theo dõi !

avatar
11 Comment threads
5 Thread replies
8 Followers
 
Most reacted comment
Hottest comment thread
12 Comment authors
GuestDũngnguyênZuvipZuvip Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Võ Nguyên
Member
Võ Nguyên

Logic khó quá, thật sự mà nói, người có logic cao , tư duy giỏi mới tìm ra quy luật đc. Em thì chịu

Vu
Guest
Vu

có 1 số test vd n=8, x=2, y=3 thì chạy rất lâu , không thể có cách nào cho chạy nhanh hơn được sao

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Bài này cài theo vét cạn nên chậm là đúng rồi bạn, bạn có đề xuất nào để cải thiện không ạ?

Ma Anh Hoang
Guest
Ma Anh Hoang

Có cách nào có thể đếm có bao nhiêu đường đi không?

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Bạn có thể tìm hiểu thêm về thuật toán tìm kiếm theo chiều rộng – BFS hoặc thuật toán tìm kiếm theo chiều sâu – DFS để tìm/đếm tất cả các đường có thể đi

Zuvip
Guest
Zuvip

dùng backtracking vẫn đếm được mà bạn, khi đến ô cuối cùng ta thêm vào sau điều kiện dừng cập nhật giá trị biến đếm số đường đi, và thay vì exit(0) thì ta return chương trình nhé.

Trần Văn Quắc
Guest
Trần Văn Quắc

ai giải thích giúp em chỗ mà : Mình chạy hết vòng for không tìm được ô tiếp theo để di chuyển nó sẽ thoát khỏi vòng for rồi –dem va a[x][y] = 0. Lúc đó hàm dichuyen nó kết thúc rồi, có gọi hàm dichuyen nữa đâu mà nó vẫn tiếp tục chạy ạ?

Vipxpert
Guest
Vipxpert

Mình nghĩ bạn nên để đánh dấu nước đi sau khi đã di chuyển thay vì đánh dấu trước ! :v

Nguyễn Văn Hiếu
Admin
Nguyễn Văn Hiếu

Cảm ơn góp ý của Vip expert!

Zuvip
Guest
Zuvip

dem = 1; void diChuyen(int x, int y) { A[x][y] = dem; if (dem == n * n) { cout << "Cac buoc di la: \n"; xuat(); exit(0); } for( int i=0; i= 0 && u = 0 && v < n&& A[u][v] == 0) { dem++; A[u][v] = 1; dichuyen(u,v); dem–; A[u][v] = 0; } } } // mình sửa 1 chút để cho mọi người dễ hiểu hơn nhé, vẫn là code của bạn ý.

nguyên
Guest
nguyên

cho em hỏi , đoạn quay lại, tại sao –dem;
A[x][y]=0; mà nó tự quay lại được anh, nó sẽ quay lại tất cả bước nó đi, hay là chỉ bước sau.. anh mong anh giải thích với cảm ơn anh

nguyên
Guest
nguyên

vì sao nó quay lại mà nó ko lặp lại bước cũ, bước cũ cũng thỏa mãn điều kiện mà

Dũng
Guest
Dũng

bro tự nghĩ bài này à , giỏi thế

Guest
Guest
Guest

Zuvip: Bạn có thể nói rõ hơn chỗ này không dùng “backtracking vẫn đếm được mà bạn, khi đến ô cuối cùng ta thêm vào sau điều kiện dừng cập nhật giá trị biến đếm số đường đi, và thay vì exit(0) thì ta return chương trình nhé.”

Guest
Guest
Guest

Zuvip: Bạn có thể nói rõ hơn chỗ này không dùng “backtracking vẫn đếm được mà bạn, khi đến ô cuối cùng ta thêm vào sau điều kiện dừng cập nhật giá trị biến đếm số đường đi, và thay vì exit(0) thì ta return chương trình nhé.”