Violet
Dethi

Tin tức thư viện

Khắc phục hiện tượng không xuất hiện menu Bộ công cụ Violet trên PowerPoint và Word

12099162 Kính chào các thầy, cô. Khi cài đặt phần mềm , trên PowerPoint và Word sẽ mặc định xuất hiện menu Bộ công cụ Violet để thầy, cô có thể sử dụng các tính năng đặc biệt của phần mềm ngay trên PowerPoint và Word. Tuy nhiên sau khi cài đặt phần mềm , với nhiều máy tính sẽ...
Xem tiếp

Quảng cáo

Hỗ trợ kĩ thuật

Liên hệ quảng cáo

  • (024) 66 745 632
  • 096 181 2005
  • contact@bachkim.vn

Tìm kiếm Đề thi, Kiểm tra

Bài toán 8 quân Hậu trên bàn cờ Vua

Wait
  • Begin_button
  • Prev_button
  • Play_button
  • Stop_button
  • Next_button
  • End_button
  • 0 / 0
  • Loading_status
Nhấn vào đây để tải về
Báo tài liệu có sai sót
Nhắn tin cho tác giả
(Tài liệu chưa được thẩm định)
Nguồn: st
Người gửi: Phạm Huy Hoạt
Ngày gửi: 11h:19' 09-06-2012
Dung lượng: 207.4 KB
Số lượt tải: 128
Số lượt thích: 0 người
‎‎Bài toán tám quân hậu
1/Giới thiệu “Bài toán tám quân hậu”
Đây 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, theo quy tắc cờ vua.. Như vậy, 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).
Bài toán này cũng được ứng dụng trong trò chơi máy tính The 7th Gues vầo những năm 1990.
2/Lịch sử
Bài toán được đưa ra vào 1848 bởi kỳ thủ Max Bezzel, sau đó nhiều nhà toán học, trong đó có Gauss và Georg Cantor, đưa ra các công trình về bài toán này và tổng quát nó thành bài toán xếp hậu. Các lời giải đầu tiên được đưa ra bởi Franz Nauck năm 1850. Nauck cũng đã tổng quát bài toán thành bài toán n quân hậu. Năm 1874, S. Gunther đưa ra phương pháp tìm lời giải bằng cách sử dụng định thức, và J.W.L. Glaisher hoàn chỉnh phương pháp này.
.
3/Tính chất số học của lời giải
Ký hiệu quân hậu đứng ở ô nằm trên hàng thứ i của lời giải là Q[i, j]. Các chỉ số dòng cột đánh từ trên xuống dưới, trái sang phải theo cách đánh số trong ma trận). Trong một ma trân vuông:
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;
các phần tử nằm trên cùng một đường chéo song song với đường chéo chính có hiệu chỉ số hàng với chỉ số cột bằng nhau;
các phần tử nằm trên cùng một đường chéo song song với đường chéo phụ có tổng chỉ số hàng với chỉ số cột bằng nhau;
Vì thế ta gọi các đường chéo song song với đường chéo chính là đường chéo trừ (hay hiệu), các đường chéo song song với đường chéo phụ là đường chéo cộng (hay tổng).
Do đó, mỗi lời giải có thể được biểu diễn bởi dãy Q[1,i1],Q[2,i2],...,Q[n, in],thỏa mãn các điều kiện:
Các chỉ số cột i1, i2,..., in đôi một khác nhau, hay chúng lập thành một hoán vị của các số 1, 2,.., n.
Tổng chỉ số dòng và cột của các quân hậu 1+i1, 2+i2,..., n+in đôi một khác nhau;
Hiệu chỉ số dòng và cột của các quân hậu 1-i1, 2-i2,...,n-in đôi một khác nhau.
Chẳng hạn lời giải cho trong hình trên biểu diễn bới dãy ô (1 ,4),(2, 7), (3, 3), (4, 8), (5,2), (6,5), (7,1), (8,6). Ta có thể kiểm tra các điều kiện trên trong bảng:
i
1
2
3
4
5
6
7
8

j
4
7
3
8
2
5
1
6

i+j
5
9
6
12
7
11
8
14

i-j
-3
-5
0
-4
3
1
6
2

 4/ Xây dựng một lời giải
Có một giải thuật đơn giản tìm một lời giải cho bài toán n quân hậu với n = 1 hoặc n ≥ 4:
Chia n cho 12 lấy số dư r. (r= 8 với bài toán tám quân hậu).
Viết lần lượt các số chẵn từ 2 đến n.
Nếu số dư r là 3 hoặc 9, chuyển 2 xuống cuối danh sách.
Bổ sung lần lượt các số lẻ từ 1 đến n vào cuối danh sách, nhưng nếu r là 8, đổi chỗ từng cặp nghĩa là được 3, 1, 7, 5, 11, 9, ….
Nếu r = 2, đổi chỗ 1 và 3, sau đó chuyển 5 xuống cuối danh sách.
Nếu r = 3 hoặc 9, chuyển 1 và 3 xuống cuối danh sách.
Lấy danh sách trên làm danh sách chỉ số cột, ghép vào danh sách chỉ số dòng theo thứ tự tự nhiên ta được một lời giải của bài toán.
Sau đây là một số ví dụ
14 quân hậu (r = 2): 2, 4, 6, 8, 10, 12, 14, 3, 1, 7, 9, 11, 13, 5.
15 quân hậu (r = 3): 4, 6, 8, 10, 12, 14, 2, 5, 7, 9, 11, 13, 15
 
Gửi ý kiến

↓ CHÚ Ý: Bài giảng này được nén lại dưới dạng RAR và có thể chứa nhiều file. Hệ thống chỉ hiển thị 1 file trong số đó, đề nghị các thầy cô KIỂM TRA KỸ TRƯỚC KHI NHẬN XÉT  ↓