• Hướng giải dễ thấy của bài này là ta sẽ sử dụng đệ quy.

• Đề bài yêu cầu chúng ta cần phải chuyển n đĩa cọc sang cọc C. Giả sử bắt đầu xét đĩa to nhất (đĩa thứ n), ta sẽ cần phải chuyển đĩa này sang cọc C trước tiên, có 2 trường hợp xảy ra:

  • Đĩa đã nằm ở cọc C: ta sẽ không cần di chuyển đĩa này nữa và xét đến đĩa n - 1.

  • Đĩa không nằm ở cọc C: ta cần dồn tất cả (n - 1) đĩa còn lại sang cọc trung gian (ở đây nếu đĩa n nằm ở cọc A thì đĩa trung gian ở cọc B và ngược lại) để có thể chuyển được đĩa n sang cọc C. Sau đấy thì bắt đầu bước dồn n - 1 đĩa còn lại từ cọc trung gian sang cọc C.

• Từ đó, khi xét đến đĩa thứ x, ta cần quan tâm 2 điều: vị trí hiện tại của đĩa x và cột mục tiêu ta cần chuyển đĩa x sang.

• Đoạn code xử lí phần đệ quy:

void backtrack(int x, int row){
    // Ta đánh dấu cột A, B, C là 0, 1, 2 
    // a[x] là vị trí hiện tại của đĩa x
    if (a[x] == row){ // đĩa x đang ở đúng vị trí nó cần được chuyển sang
       backtrack(x - 1, row);
    }
    else{
       // chuyển x - 1 đĩa sang cọc trung gian
       backtrack(x - 1, 3 - row - a[x]);
       // thực hiện chuyển đĩa x sang cọc cần được chuyển sang
       a[x] = row
       // chuyển x - 1 đĩa sang cọc cần được chuyển sang
       backtrack(x - 1, row);
    }
}

Lưu ý: với bài này cần in ra các bước chuyển, nếu số bước chuyển cần chuyển lớn (do cách chuyển không tối ưu) có thể dẫn đến chạy quá thời gian.