Atın keçməyən yolu

Klassik tapmaca "at" vasitəsilə 8 \times 8 ölçülü şahmat taxtasının bütün xanalarını "gəzmekdən" ibarətdir. At — bir xana bir istiqamətə, iki xana perpendikulyar istiqamətə tullanaraq gedir. Bütün taxtadakı hər bir xananı məhz bir dəfə ziyarət etmək və başlanğıc nöqtəsinə qayıtmaq tələb olunur. Bu üsulla məsələni həll etmək üçün bir çox yol mövcuddur və taxtanın ölçüsü kifayət qədər kiçikdir, buna görə də bu məsələni həqiqətən insan həll edə bilər.

Lakin sizin kompüter və proqramlaşdırma bacarıqlarınız var! Beləliklə, biz daha çətin versiyanı təklif edirik: düz bucaqlı m \times n ölçülü taxta üçün əlavə bir məhdudiyyətlə: at heç vaxt öz yolunu keçməməlidir. Əgər yolu, atın hərəkət etdiyi xanalardan mərkəzi birləşdirən doğru seqmentlər toplusu kimi təqdim etsək, bu seqmentlər sadə çoxbucaq əmələ gətirməlidir. Başqa sözlə, heç bir iki seqment bir-birini kəsməməli və ya birləşdirməməlidir, qonşu olanlar tərəfindən paylaşılan son nöqtə istisna olmaqla.

Bu məhdudiyyətə görə bütün taxtanı ziyarət etmək qeyri-mümkün olur. Bu səbəbdən, atın ziyarət edə biləcəyi xana sayını maksimumlaşdırmaq tələb olunur. Eyni zamanda, yol başlanğıc xanasında bitməlidir. Şəkildə birinci nümunə üçün - 6 \times 6 taxtası üçün optimal həll göstərilmişdir.