Az előző részben megismerkedtünk a visszalépéses kereséssel, és alkalmaztuk a módszert az $n$-vezér probléma megoldására. A feladatban egy $n\times n$-es sakktáblán helyeztünk el vezéreket úgy, hogy azok ne üssék egymást. A megoldás abból állt, hogy sorrendben végighaladtunk az oszlopokon, és minden oszlopban megpróbáltunk úgy elhelyezni egy vezért, hogy ne álljon ütésben egyik lerakott vezérrel sem. Amikor ez egy oszlopban sikerült, akkor továbbléptünk a következő oszlopra, ha nem sikerült, akkor visszaléptünk az előző oszlopra. A feladat a visszalépéses keresés könnyű iskolapéldája volt, hiszen egy adott oszlopon belül $n$ sorba tudtunk lerakni egy vezért, vagyis egy adott állásból könnyű volt a következőre, vagy az előzőre lépni.
Nézzünk meg egy kicsit összetettebb feladatot. A szeptemberi számban kitűzött K. 508. feladatban egy olyan $N\times N$ méretű falat kellett $1\times 2$-es téglákból megépíteni, amelyet nem lehet vízszintes vagy függőleges vonallal két részre osztani úgy, hogy a vonal ne vágjon el egy téglát sem. Az eredeti feladatban egy ilyen, ,,földrengésbiztos'' falat kértek $8\times 8$-as méretben. Általánosítsuk a feladatot úgy, hogy $N\times M$ méretű, földrengésbiztos falat kívánunk építeni, szintén $1\times 2$-es téglákból. Nézzük meg, hogy milyen $N$ és $M$ esetén adódnak megoldások, illetve mennyi azok száma.
Gondoljuk végig, hogy milyen eseteket kell megnéznünk. Biztosan tudjuk, hogy $\frac{N\cdot M}{2}$ téglát kell majd elhelyeznünk, mindegyiket vízszintesen, vagy függőlegesen. Végeredményként az összes tégla elhelyezésének módját szeretnénk tudni, tehát azt, hogy vízszintesen vagy függőlegesen áll, illetve hogy a fal mely részén helyezkedik el. Ezekre az adatokra a program futása során is szükségünk van. A visszalépéses keresést akarjuk alkalmazni, ezért ki kell találnunk a téglák elhelyezésének sorrendjét. Mivel a téglák nincsenek sorszámozva, ezért két elhelyezés azonos, ha abban két téglát kicserélünk. Hogy ne számoljuk meg az ilyen lehetőségeket többször, állapodjunk meg a következőkben: