Je možné n queen vyriešiť problém bez spätného odkliknutia?
Stretol som sa s mnohými typmi odpovedí na n queen problém, ale všetky z nich vyžadujú spätnú väzbu. Existuje spôsob, ako to vyriešiť bez spätného odkráčania?
odpovede:
5 pre odpoveď č. 1Áno. Mohli by ste ho vyhnúť tým, že vygenerujete všetky možné dosky a potom ich otestujete.
Tento prístup by sa však nezmenil;
Upozorňujeme tiež, že wikipedia článok obsahuje niekoľko riešení vrátane "opakovanej opravy".
1 pre odpoveď č. 2
Genetický algoritmus, ktorý vyvíja to najlepšieriešenie by nevyžadovalo spätné prevrátenie, ale to je iný spôsob riešenia problému než algoritmus na prekonanie grafu štátneho priestoru, ktorý sa zdá, že vaša otázka naznačuje
0 pre odpoveď č. 3
Áno. Wikipedia uvádza niekoľko, vrátane jedného z faktorov (ktoré som teraz zvedavý, ale nezaznamenal) Dovoľte mi skopírovať a vložiť jednu doslovne:
Vyššie uvedené príklady sa dajú získať pomocou nasledujúcich vzorcov. Nech (i, j) je štvorec v stĺpci i a riadok j na nx n šachovnici, k celé číslo.
- Ak n je rovnomerné a n ≠ 6k + 2, potom dámy queens v (i, 2i) a (n / 2 + i, 2i - 1) pre i = 1,2, ..., n / 2.
- Ak n je rovnomerné a n ≠ 6k, potom matky položte na (i, 1 + (2i + n / 2 - 3 (mod n))) a n + 1 - i, n - (mod n))) pre i = 1,2, ..., n / 2.
- Ak n je nepárne, použite jeden z vyššie uvedených vzorov pre (n - 1) a pridajte kráľovnú v (n, n).