Səyahət edən Kraliça Problemi#2530
Qara məğlub edilib və ağ ordusu qələbə qazanıb, lakin təəssüf ki, ağ şah döyüşdə öldürülüb. Buna görə də ağ şahmat kraliçası (qız) özünə yeni həyat yoldaşı axtarır. O, hansı atı (şahmat fiqurunu) seçəcəyinə qərar verə bilmir və onların hamısını ziyarət etməyə qərar verir. Bundan sonra, toy təşkil etmək üçün yepiskopa baş çəkməyi planlaşdırır.
Verilmiş şahmat taxtası üzrə mövcud vəziyyəti nəzərə alaraq, kraliçanın bütün atları ziyarət edib, sonda yepiskopa baş çəkməsi üçün minimal gedişlərin sayını tapın.
Kraliça ziyarəti, hər atdan və ya yepiskopdan ən çox səkkiz qonşu xanadan birində dayanmaqla sayılır; o, ziyarətlər arasında hərəkət etməli deyil. Hər bir gedişdə, kraliça istənilən səkkiz istiqamətin (üfüqi, şaquli və diaqonal) birində istənilən sayda xananı keçə bilər. Heç bir gedişdə dolu (başqa fiqur olan) xanadan keçmək və ya orada dayanmaq olmaz.
Birinci sətirdə ssenarilərin sayı verilir. Hər bir ssenari şahmat taxtasının təsviri ilə başlayır. Sətirlər 8, \ldots, 1 ardıcıllığında, hər bir satır üzrə bir xətt verilir. Hər sətir sütunlar a, \ldots, h-ə uyğun simvoldan ibarətdir. Hər bir təsvir boş sətirlə tamamlanır.
Bir simvolu kraliçanın başlanğıc mövqeyini göstərir və bir simvolu yepiskopun yerləşdiyi xanadadır. Orada hərəkəti sadəcə bloklayan istənilən sayda piyada () ola bilər, həmçinin – at simvolu ilə göstərilir. Bütün digər xanalarda simvolu olur və onlar boşdur.
Hər bir ssenari üçün əvvəlcə bir sətirdə "\textbf{Scenario #i:}" yazın, burada nömrələmə üzrə ssenarinin nömrəsidir (-dən başlayaraq).
Sonra minimal gediş sayına malik, yepiskopa qonşu xana başa çatan və hər bir atı ən azı bir dəfə ziyarət edən leksikoqrafik olaraq birinci olan yolu əlavə edin. Yol bir sətirdə kraliçanın dayandığı xanalardan ibarət olaraq verilir, ardıcıllıqla kvadrat adlarını birləşdirərək yazılır. Hər bir xana adı kiçik hərf və ardınca bir rəqəmdən ibarət olmalıdır. Əgər belə yol yoxdursa, bir sətirdə "" yazın. Hər bir ssenarinin cavabını boş sətirlə tamamlayın.
Nümunə 1