n × n шатрын самбар дээр n бэрсийг бие биеэ идэхгүйгээр тавих бүх аргыг backtracking аргаар тоолно.

IntermediateХугацаа: O(n!)Санах ой: O(n)

Эхлээд жижиг бодлого

4×4 самбар дээр 4 бэрсийг бие биеэ идэхгүйгээр тавья. Мөр 0, 1, 2, 3 дээр харгалзан багана 1, 3, 0, 2-т бэрс тавибал болно.

Толин тусгал нь болох 2, 0, 3, 1 байрлал бас тохирно. Өөр шийд байхгүй тул хариу 2.

Энгийн аргаас санаа руу

Энгийн арга бол 16 нүднээс 4-ийг сонгох бүх аргыг шалгах. 1820 хослол байна, 8×8 самбарт 4 тэрбум гаруй болно.

Эхний сайжруулалт: нэг мөрөнд хоёр бэрс байж болохгүй. Тиймээс мөр бүрт яг нэг бэрс тавина. Хоёр дахь сайжруулалт: тавих бүрдээ шалгаад, идэгдэх нүд рүү огт ормооргүй. Гацвал өмнөх мөр рүү буцаж бэрсээ өөр нүдэнд шилжүүлнэ. Энэ бол backtracking.

Нэр томьёо ба тэмдэглэгээ

solve(r)
Мөр 0..r−1-д бэрс тавигдсан. Одоо мөр r дээр тавина.
col[c]
Багана c-д бэрс байгаа эсэх.
d1[r + c]
Баруун дээшээ чиглэсэн диагональ. Нэг диагональ дээр r + c ижил.
d2[r − c + n]
Баруун доошоо чиглэсэн диагональ. r − c ижил. n нэмдэг нь index сөрөг болохгүйн тулд.
cnt
Олдсон шийдийн тоо.
r\c01230
1
2
3
n = 4cnt = 0

4×4 шатрын самбар дээр 4 бэрсийг бие биеэ идэхгүйгээр хэдэн янзаар тавьж болох вэ? Мөр бүрт нэг бэрс тавьж үзье.

Алхам 1 / 36
Хурд
  • Бэрс ♛
  • Сая тавьсан бэрс
  • Идэгдэх нүд
  • Бэрсээ авсан нүд
  • Шийд
Слайд 1 / 7

Бэрсийн бодлого

Шатрын бэрс өөрийн мөр, багана, диагоналаар хэдэн ч нүд явж иддэг. 4×4 самбар дээр 4 бэрсийг бие биеэ идэхгүйгээр тавьж чадах уу?

n-queens.cpp
#include <bits/stdc++.h>
using namespace std;
int n, cnt;
bool col[10], d1[20], d2[20];
void solve(int r) {
if (r == n) {
cnt++;
return;
}
for (int c = 0; c < n; c++) {
if (col[c] || d1[r + c] || d2[r - c + n]) continue;
col[c] = d1[r + c] = d2[r - c + n] = true;
solve(r + 1);
col[c] = d1[r + c] = d2[r - c + n] = false;
}
}
int main() {
cin >> n;
solve(0);
cout << cnt << '\n';
return 0;
}

Юунд хэрэгтэй вэ?

Мөр бүрт нэг бэрс тавьж, гацвал буцах (backtracking) аргаар шийдийн тоог олно. Багана, диагоналийг array ашиглан хурдан шалгах санааг сурна.

Яаж ажилладаг вэ?

1. solve(r) нь мөр r дээр бэрс тавина. r == n бол бүх мөрөнд бэрс байна: cnt нэмэгдэнэ. 2. c багана бүрийг үзнэ. Тэр багана (col[c]) эсвэл хоёр диагональ (d1[r + c], d2[r − c + n]) аль хэдийн эзлэгдсэн бол алгасна. 3. Аюулгүй бол бэрс тавьж, гурван тэмдгийг true болгоод solve(r + 1)-ийг дуудна. 4. Буцаж ирээд тэмдгүүдийг false болгож бэрсээ авна. Дараа нь дараагийн баганыг оролдоно. Нэг чиглэлийн диагональ дээрх нүднүүдийн r + c ижил, нөгөө чиглэлийнхэд r − c ижил байдаг. Оролт: нэг тоо n.

Яагаад зөв, хэр хурдан бэ?

Бэрс тавих бүрт багана ба хоёр диагональ нь чөлөөтэй эсэхийг шалгадаг. Мөр нь өөр гэдэг нь мэдээж. Тиймээс r == n хүрсэн байрлал бүр зөв шийд. Нөгөө талаас идэгдэх нүдийг алгасахад ямар ч шийд алдагдахгүй. Тиймээс бүх шийдийг яг нэг удаа тоолно.

Хамгийн муудаа n! орчим байрлал шалгана, гэхдээ шалгалт нь ихэнх салаа мөчрийг эрт тасалдаг. n = 8 бол 2056 удаа бэрс тавиад 92 шийдийг олно. n = 13 хүртэл нэг секундэд багтана.

Түгээмэл алдаа

  • d2-ын index-ийг r - c гэж бичих. c > r үед сөрөг index гарна. r - c + n гэж бич.
  • d1, d2 array-г n хэмжээтэй зарлах. r + c нь 2n − 2 хүртэл хүрдэг тул 2n хэрэгтэй.
  • Буцахдаа гурван тэмдгийн аль нэгийг false болгохоо мартах. Дараагийн оролдлогод нүд эзлэгдсэн мэт харагдана.

Хязгаарын тохиолдол

  • n = 1: нэг нүд, нэг бэрс, хариу 1.
  • n = 2, n = 3: шийд байхгүй, хариу 0.
  • n = 6: ердөө 4 шийд. n = 5 бол 10, n = 8 бол 92.

Өөрийгөө шалга

  1. n = 5 бол хэдэн шийд бий вэ?

    Хариу харах

    10.

  2. (2, 3) ба (4, 1) нүд нэг диагональ дээр байна уу?

    Хариу харах

    Тийм. Хоёулангийнх нь r + c = 5.

  3. Яагаад мөрийг шалгах array хэрэггүй вэ?

    Хариу харах

    solve(r) мөр бүрт яг нэг бэрс тавьдаг тул нэг мөрөнд хоёр бэрс хэзээ ч орохгүй.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.n = 4 үед (0, 0) нүдэнд бэрс тавибал яагаад шийд олдохгүйг гараар шалга.

    Hint харах

    Мөр 1-д багана 2 эсвэл 3 л үлдэнэ. Хоёуланг нь оролдоод үз.

    Хариу ба тайлбар

    Багана 2 бол мөр 2-т аюулгүй нүд үлдэхгүй. Багана 3 бол мөр 2-т багана 1, тэгээд мөр 3-т аюулгүй нүд алга. Тиймээс мөр 0-ийн бэрсийг багана 1 рүү шилжүүлнэ.

  2. 2.Эхний олдсон шийдийг самбар хэлбэрээр хэвлэ.

    Hint харах

    Мөр бүрийн бэрсний баганыг pos[r] = c гэж хадгал.

    Хариу ба тайлбар

    pos[r] = c;-г тавих үед бичнэ. r == n үед cnt нь 1 бол pos-оор самбарыг хэвлэнэ. Мөр r-д pos[r] баганад Q, бусад нүдэнд . гэж бичнэ.

  3. 3.Самбарын зарим нүд эвдэрсэн, тэнд бэрс тавьж болохгүй. Шийдийн тоог ол.

    Hint харах

    Шалгах нөхцөлд нэг зүйл нэмэхэд хангалттай.

    Хариу ба тайлбар

    if (bad[r][c] || col[c] || d1[r + c] || d2[r - c + n]) continue;. Бусад код хэвээр.

Жишээ

Оролт

4

Гаралт

2