Programozás‎ > ‎Feladatok‎ > ‎

8 királynő probléma

A back-track algoritmusát legegyszerűbb a 8 királynő problémáján megtanulni. Ez a feladat arról szól, hogy hogyan (és hányféle módon) helyezhető el 8 királynő a sakktáblán úgy, hogy semelyik kettő ne üsse egymást. 


Feladat

Írjunk programot, ami felsorolja az összes lehetséges megoldást, és megadja azt is, hogy hány van. Nehezebb változat: ne különböztessük meg azokat egymástól, amelyek tükrözéssel vagy forgatással egymásba vihetők.

Bemenet

A tábla mérete: 2 <= N <= 16.

Kimenet

Az első sorba a megoldások M számát kell írni, majd a következő M sorba egy-egy megoldást. A megoldások N szóközzel elválasztott egésszel kódolhatók, ahol az i. szám azt írja le, hogy az i. oszlop hányadik sorában áll a királynő. A sorokat és oszlopokat egytől számozzuk.

Példa

Bemenet  Kimenet
42
2 4 1 3
3 1 4 2


Címkék

A feladat forrása: ismert feladat
Algoritmusok: backtrack, visszalépéses keresés

megoldás