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.
BemenetA tábla mérete: 2 <= N <= 16.
KimenetAz 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
CímkékA feladat forrása: ismert feladat
Algoritmusok: backtrack, visszalépéses keresés
megoldás |
Programozás > Feladatok >