Boyalı Kub

Güç üzüyünün Frodo'nun əlində olduğu aşkar edildikdən sonra, Gandalf dərhal öz ordeninin başçısı Sarumanın məsləhətini almaq üçün yola çıxdı. Saruman, üzüyü məhv etməli olduqlarına dair Gandalfın inancına razı olmadı. O, Gandalfı dərhal azad buraxıb Frodoya kömək edə bilməyəcəyinə qərar verdi və onu Isengarddakı qaranlıq qülləsinin ən yüksək otağında kilidlədi. Gandalfı məşğul etmək üçün otağa yalnız tapmacasını həll etməklə qaçmaq mümkün olan bir qapı qoydu.

Qısa müddət sonra otaqda qaçış yolu axtararkən, Gandalf qüllənin damına aparan bir qapıda çox qəribə bir kilid gördü. Kilid, üzərində heç bir işarəsi olmayan standart altı tərəfli bir kub idi. O, m×n ölçüsündə bir şəbəkənin üstündə yerləşdirilmişdi. Şəbəkədə üzərində boya olan dəqiq altı kvadrat var idi. Gandalf gördü ki, kubun boş bir üzü üzərində boya işarələri olan bir kvadrata yuvarlandıqda, işarələr şəbəkədən kubun üzünə köçürülürdü. Kub, üzərində heç bir işarə olmayan bir kvadrata yuvarlandıqda və kubun təmas səthində bir işarə olduqda, işarə kubdan şəbəkəyə köçürülürdü. Əgər kub şəbəkədə işarə olan bir kvadrat üzərinə yuvarlanarsa və kubun təmas səthində hər hansı bir işarə varsa, heç nə baş vermirdi.

Gandalf başa düşdü ki, dam qapısını açmaq yalnız kubun bir sıra hərəkətlərlə hədəf kvadratına yuvarlanması ilə baş verə bilər, belə ki, şəbəkədəki bütün işarələr kubun üzərinə köçürülsün. Üstəlik, Sarumanın tələsindən qaçmaq üçün, (düzgün) təxmin etdi ki, bunu minimum hərəkət sayında etməlidir.

Kvadratlarda ilkin boya konfiqurasiyası, kubun ilkin yeri və istənilən hədəf yeri verildikdə, Gandalfın kubu bütün tərəflərində boya ilə hədəf vəziyyətinə gətirmək üçün etməli olduğu minimum hərəkət sayı nədir?

Birinci nümunə üçün (aşağıya baxın), nümunə həll aşağı, sağa, sağa, yuxarı, sağa, sağa, aşağı, sola, sağa, sola ola bilər.