Izpitno vprašanje RAČ2PRA 16700

Iz MaFiRaWiki

Vprašanje

|16700| Opiši postopek reševanja problema postavitve n-kraljic na šahovsko desko.

Odgovor

Problem rešujemo s pomočjo sestopanja.
Imamo šahovsko polje velikosti n x n. Rešitve problema obstajajo za n >= 4.

Algoritem

  • Na i-tem koraku algoritma poskušamo kraljico postaviti v i-ti stolpec. Če nam to uspe, nadaljujemo algoritem z (i+1)-im korakom.
  • Če je ne moremo postaviti v i-ti stolpec, sestopimo en korak nazaj in poskušamo kraljico postaviti na drugo mesto v (i-1)-vem stolpcu. Če je ne moremo postaviti niti tu, sestopimo še korak nazaj...

Primer Kako postaviti 4 kraljice na šahovskem polju 4 x 4

  • Prvo kraljico postavimo v prvi stolpec prve vrste:
K - - -
- - - -
- - - -
- - - -
  • Druge ne moremo postaviti v prvi stolpec

Niti v drugi stolpec
Postavimo jo v tretjega:

K - - -
X X K -
- - - -
- - - -
  • Tretje ne moremo postaviti v prvi stolpec

Niti v drugi stolpec
Niti v tretjega
In tudi v četrtega ne!
Očitno kraljica v drugi vrstici ni dobro postavljena:

K - - -
X X K -
X X X X
- - - -
  • Zato se vrnemo v drugo vrstico in postavimo drugo kraljico v četrti stolpec:
K - - -
X X e K
- - - -
- - - -
  • Tretjo kraljico lahko postavimo v drugi stolpec:
K - - -
X X e K
X K - -
- - - -
  • Ampak potem četrte kraljice ne moremo postaviti nikamor:
K - - -
X X e K
X K - -
X X X X
  • Vrnemo se v tretjo vrstico in postavimo kraljico...

...pravzaprav je nimamo kam postaviti
Torej gremo spet višje:

K - - -
X X e K
X e X X
- - - -
  • Vrnemo se v drugo vrstico in poskušamo prestaviti drugo kraljico en stolpec naprej...

... pa ne gre:

K - - -
X X e e
- - - -
- - - -
  • Torej smo napačno postavili prvo kraljico

Prestavimo jo:

e K - -
- - - -
- - - -
- - - -
  • Postavimo drugo kraljico<br/

Imamo samo eno možnost:

e K - -
X X X K
- - - -
- - - -
  • Postavimo tretjo kraljico

Spet imamo samo eno možnost:

e K - -
X X X K
K - - -
- - - -
  • In postavimo še zadnjo kraljico na edino preostalo prosto mesto.

To je ena izmed rešitev postavitve štirih kraljic na polje 4 x 4:

e K - -
X X X K
K - - -
X X K -
Osebna orodja