Ezt milyen algoritmussal oldanátok meg?

Fogalmam sincs, mi a neve az algoritmusnak, de ha az előttem szóló kolléga szerint backtracking, akkor legyen úgy.

Ennyi a feladat? Mert így kevés az értelme. Milyen színűek ugyanis a figurák? Ha mind világos vagy sötét, akkor semmilyen helyzetben nem üthetik egymást. Ha fele-fele, akkor némelyik üthet, némelyik nem. Vagy mindegyik üthet mindenkit, függetlenül a színüktől? De tételezzük fel az utóbbit.

Az a baj, hogy ha nekiállnék legenerálni az összes variációt, az olyan elképesztő adattömeg lenne, amivel kár is vesződni. Ez tehát nem járható. De hatalmasat optimalizálunk rajta, ha azt csináljuk, hogy először egy királynőt teszünk le az A1-be, majd utána a következőt olyan helyzetbe, ahol sem vízszintesen, sem függőlegesen nincs vele egy vonalban. A következőt ehhez képest már csak azokra a helyekre tehetjük, ahol szintén egyikkel sincs vonalban, és a negyediket is. Ezzel nagyon lecsökken a variációk száma, szerintem kezelhetővé is válik.

Ezután a meglévő királynő-konfigurációkba elkezdjük belepróbálgatni a négy huszárt. Keresünk olyan konfigurációkat, ahol a királynők vonalai között megmaradt négy olyan vakfolt, amely L alakú.

Ez szerintem elfogadható sebességgel lefutna még JavaScriptben is.

Jajj...

A huszár egyébként L alakban léphet.

Klasszikus, n-királynő probléma:

[link]