Qum saatı

Bu tapşırıqda sizdən fişlərlə düz bir lövhədə tapmaca həll etməyiniz tələb olunur.

"Qum saatı" adlı tapmaca n ölçüsündə aşağıdakı kimidir. Lövhə müstəvidə yerləşir və (2 ∙ n + 1) sıradan ibarətdir. Sıralar üfüqi yerləşir və biri digərinin altında yerləşir. Hər bir sıra mövqelərdən ibarətdir: orta sıra bir mövqedən ibarətdir, və orta sıraya yaxın olan hər bir növbəti sıra yuxarıda və aşağıda bir mövqe daha çoxdur. Qonşu sıradakı mövqelər elə birləşdirilib ki, qısa sıradakı hər bir mövqe daha böyük sırada dəqiq iki qonşuya malikdir. n = 2 üçün lövhə aşağıda göstərilmişdir.

Lövhədə bir neçə fiş var. Əvvəlcə hər bir mövqe n yuxarı sırada qırmızı fiş (qum) və hər bir mövqe n aşağı sırada mavi fiş (hava) ilə doldurulub. Tapmacanın məqsədi fişlərin yerini dəyişməkdir, yəni yuxarı n sıranı hava ilə, aşağı n sıranı isə qumla doldurmaqdır. Eyni rəngli fişlər eyni hesab olunur. Hər bir mövqedə hər hansı bir hərəkət zamanı ən çox bir fiş ola bilər. n = 2 üçün başlanğıc və son vəziyyət aşağıda göstərilmişdir. Qırmızı fişlər “X”, mavi fişlər isə “O” ilə göstərilmişdir.

Fişlərin hərəkəti aşağıdakı qaydalara uyğun olaraq baş verir.

• Qırmızı fişlər yalnız aşağıya hərəkət edə bilər, mavi fişlər isə yalnız yuxarıya.

• Hər bir gedişdə yalnız bir fiş yerini dəyişir.

• Əgər müəyyən bir fiş üçün icazə verilən istiqamətdə (yuxarı-sol və ya yuxarı-sağ mavilər üçün, aşağı-sol və ya aşağı-sağ qırmızılar üçün) iki qonşu mövqedən biri mövcuddur və boşdursa, o, ora hərəkət edə bilər.

• Əgər bu mövqe başqa rəngli fişlə doludursa, lakin eyni istiqamətdə (yuxarı-sol, yuxarı-sağ, aşağı-sol, aşağı-sağ) növbəti mövqe mövcuddur və boşdursa, fiş onu keçərək həmin mövqeni tuta bilər.

• Tullanma yalnız düz xətt üzrə, iki mövqe uzunluğunda və başqa rəngli fiş üzərindən baş verərsə icazəlidir. Digər tullanma növləri (məsələn, düz yuxarı və ya düz aşağı iki mövqe üzrə) icazəli deyil.

Aşağıda n = 2 üçün tapmacanın həlli üçün gedişlər ardıcıllığı göstərilmişdir.

Gedişlər ardıcıllığı aşağıdakı kimi yazılır.

• Yuxarı-sol hərəkət və ya tullanma «b» hərfi ilə göstərilir.

• Yuxarı-sağ hərəkət və ya tullanma «d» hərfi ilə göstərilir.

• Aşağı-sol hərəkət və ya tullanma «p» hərfi ilə göstərilir.

• Aşağı-sağ hərəkət və ya tullanma «q» hərfi ilə göstərilir.

Notasiyanın intuitiv izahı ondan ibarətdir ki, hərfin quyruğu hərəkət və ya tullanmanın istiqamətini göstərir.

Məlum olur ki, bu notasiya tapmacanın bütün aralıq vəziyyətlərini bərpa etməyə imkan verir.

Tapmacanın ölçüsü n verildikdə, onun həllini çıxarın. Gedişlərin sayını minimallaşdırmaq və ya maksimallaşdırmaq lazım deyil.