Giải bài toán xếp hậu bằng đệ quy dùng code C/C++

4
3607

Bài toán xếp xếp hậu là bài toán đặt tám quân hậu trên bàn cờ vua kích thước 8×8 sao cho không có quân hậu nào có thể “ăn” được quân hậu khác, hay nói khác đi không quân hậu nào có để di chuyển theo quy tắc cờ vua.

Giới thiệu bài toán xếp hậu

Lời giải của bài toán là một cách xếp tám quân hậu trên bàn cờ sao cho không có hai quân nào đứng trên cùng hàng, hoặc cùng cột hoặc cùng đường chéo. Bài toán tám quân hậu có thể tổng quát hóa thành bài toán đặt n quân hậu trên bàn cờ n×n(n ≥ 4).

bai-toan-xep-hau
Bài toán xếp hậu

Hình ảnh ở trên mô tả một lời giải của bài toán xếp 11 quân hậu trên một bàn cờ vua 11*11. Vậy chúng ta cùng bắt tay vào tìm lời giải cho bài toán này.

Giải bài toán xếp hậu bằng đệ quy trong C/C++

  • Để tiện trình bày ta dùng biến i để đánh dấu các hàng từ trên xuống ( 1 đến n). Dùng biến j để đánh dấu các cột từ trái sang phải ( 1 đến n );
  • Các phần tử nằm trên cùng hàng có chỉ số hàng bằng nhau;
  • Các phần tử nằm trên cùng cột có chỉ số cột bằng nhau;
  • Để tiện cho việc in kết quả ra thì ta chỉ in ra chỉ số các cột tuần tự theo các hàng từ trên xuống.
  • Điều kiện để đặt một quân hậu đúng chỗ là không có 2 trên cùng một cột ( chỉ số cột khác nhau). Không có 2 quân hậu nào cùng ở trên một đường chéo.

Ý tưởng:

  • Đầu tiên ta đặt quân hậu thứ nhất vào các cột trên hàng 1 ( có n cách đặt ).
  • Thử đặt quân hậu 2 vào từng cột ở hàng 2 sao cho không bị quân hậu 1 khống chế. Với mỗi vị trí của quân hậu này ta lại thử đặt quân hậu thứ ba vào các cột sao cho không bị các quân hậu trước khống chế.
  • Sau khi đặt xong quân hậu thứ tám thì in ra một cách đặt.

Code C

Mình xin 5 phút quảng cáo nha =))

 

Sau khi chạy thì sẽ ra các kết quả ( mình chỉ copy một ít kết quả thôi )

Mình giải thích một ít câu lệnh trong chương trình trên

  • ( x2, y2) là vị trí mà quân hậu sẽ đặt vào. Như vậy chúng ta chúng ta đã đặt xong x2-1 quân hậu rồi.
  • Để kiểm tra quân hậu này có bị các quân hậu trước khống chế hay không. Ta sẽ kiểm tra lần lượt các quân hậu ở trước với quân hậu vừa mới đặt vào.
  • Chỉ cần bị một quân hậu khác khống chế thì vị trí này không thể đặt vào ( return false).
  • a[i] == y2 dùng để kiểm tra xem quân hậu này có nằm cùng một cột với các quân hậu trước đó.
  • abs(i - x2) == abs( a[i] - y2 ) dùng để kiểm tra xem quân hậu này có nằm trên đường chéo của các quân hậu trước đó hay không. Các bạn có thể vẽ hình ra và tự chứng minh nhé !

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

avatar
2 Comment threads
2 Thread replies
3 Followers
 
Most reacted comment
Hottest comment thread
3 Comment authors
Nguyễn Văn HiếuMinh BuiKem Lee Recent comment authors
  Subscribe  
newest oldest most voted
Notify of
Kem Lee
Member
Kem Lee

mình chạy không ra kết quả

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

Bạn check trên online compiler này nhé. Mình chạy ok mà.

https://ideone.com/diySlZ

Minh Bui
Guest
Minh Bui

ai giải thích hộ mình ý nghĩa của đáp án với

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

Em chú ý đọc kỹ là hiểu mà: “Để tiện cho việc in kết quả ra thì ta chỉ in ra chỉ số các cột tuần tự theo các hàng từ trên xuống.”