Slink
Slitherlink, Sudoku-nu məşhurlaşdıran Yapon şirkəti Nikoli tərəfindən yayımlanan bir tapmacadır. Slitherlink tapmacaları sürətlə populyarlaşır və bu tapmacaların kitabları dünya üzrə yayılmağa başlayıb. Tapmacalar anlamaq üçün asandır, lakin həll etmək çətin ola bilər. Tapmaca, nöqtələrdən ibarət düzbucaqlı bir şəbəkədən ibarətdir və bu, hüceyrələr toplusunu təşkil edir. Hər bir hüceyrə ya boşdur, ya da sıfırdan üçə qədər bir ədəd ehtiva edir. Məqsəd, nöqtələri xətt seqmentləri ilə bir dövrə (hər bir zirvənin dəqiq iki insident kənarı olan birləşdirilmiş yol) yaratmaqdır ki, hər bir dəyəri olan hüceyrənin dəqiq olaraq ehtiva etdiyi rəqəm qədər insident kənarları olsun. Dəyəri olmayan hüceyrələrdə istənilən sayda insident kənarları ola bilər. Etibarlı bir Slitherlink tapmacası həmişə unikal həllini təmin etmək üçün kifayət qədər boş olmayan hüceyrələr ehtiva edir. Aşağıda Nikoli veb saytından bir Slitherlink tapmacası və onun həlli nümunəsi verilmişdir.
Tokio Universitetindən Takayuki Yato tərəfindən göstərilmişdir ki, ümumi Slitherlink problemi NP-tamdır. (Əgər bu konsepsiya ilə tanış deyilsinizsə, qeyri-rəsmi olaraq bu, problemi həll etmək üçün "səmərəli" bir alqoritm olmadığını bildirir.) Lakin, kiçik bir dəyişiklik və bəzi sadə heuristikalarla, proqramlaşdırılmış həllər mümkündür. Bizim yeni tapmacamız, Slink adlandıracağımız, Slitherlink-dən yalnız tapmacanın boş hüceyrələrə malik olmaması ilə fərqlənir. Yəni, hər bir hüceyrə insident kənarların sayını göstərməlidir. Aşağıda yuxarıdakı Slitherlink tapmacası Slink-ə çevrilmişdir (əlavə edilmiş rəqəmlər boz rəngdə göstərilmişdir). Qeyd edək ki, həll dəyişmir, yalnız tapmacanın özündə verilən məlumat dəyişir.
Slink-i həll etmək üçün heuristikalar tapmacanın öz təbiətindən yaranır. Məsələn, sıfır ehtiva edən bir hüceyrəni nəzərdən keçirin. Heç bir insident kənar olmamalıdır, buna görə də bütün sıfırlara insident olan kənarlar dərhal həll yolunun bir hissəsi kimi nəzərdən çıxarılmalıdır. Sıfırın yanında üçü nəzərdən keçirin. Çünki sıfıra insident olan bütün kənarlar aradan qaldırılacaq, üç ilə ortaq olan kənar da aradan qaldırılır. Lakin bu, üç ətrafında yalnız üç kənar buraxır və buna görə də bu üç kənar həll yolunun bir hissəsi olmalıdır. Aşağıdakı cədvəl Slink tapmacasını həll etmək üçün düzgün tətbiq olunmalı olan heuristik qaydaları göstərir. Zirvələr arasında olan "x" simvolları həll yolunun bir hissəsi olmayan kənarları işarələyir, zirvələr arasında olan xətt seqmentləri isə həll yolunun bir hissəsini təşkil edən kənarları işarələyir. Boz elementlər qaydanın əsaslandığı nümunəni, qara elementlər isə qayda uyğun gəldikdə daxil edilməli və ya xaric edilməli olan əlavə kənarları göstərir. Qeyd edək ki, göstərilən nümunələr yalnız nümayiş məqsədlidir və bəyan edilmiş qaydanın hər mümkün düzülüşünü göstərmir!
Giriş verilənləri
Bu problemin girişi həll olunacaq Slink tapmacaları dəstidir. Slink probleminin girişinin ilk sətri bir boşluqla ayrılmış iki tam ədəd, r və c ehtiva edir, tapmacanın satır və sütunlarının sayını göstərir. Girişin növbəti r satırı tapmacanın məzmununu göstərən, 0-dan 3-ə qədər qiymətləndirilmiş, boşluqla ayrılmış c tam ədəd ehtiva edir. Tapmacanın minimum ölçüsü 2 x 2 hüceyrədir və maksimum ölçüsü 20 x 20 hüceyrədir. Hər bir giriş tapmacasının unikal həllinin mövcud olduğu və qayda tətbiq oluna bilən zaman həmişə tətbiq olunarsa, yuxarıdakı qaydalarla müəyyən edilə biləcəyi təmin edilir. r və c üçün sıfır dəyərləri olan bir sətir girişin sonunu işarələyir.
Çıxış verilənləri
Bu problemin çıxışı Slink tapmacasının həllinin qrafik təsviridir. İlk məlumat dəsti 1, ikinci məlumat dəsti 2 və s. Bir sətirdə məlumat dəsti nömrəsini, ardınca aşağıda göstərilən formatda dəqiq həlli göstərin. Şaquli kənarlar '|' simvolu ilə, üfüqi kənarlar isə tire '-' simvolu ilə göstərilir, yolun istiqamətini dəyişdiyi zirvələr isə üstəgəl işarələri '+' ilə göstərilir və hüceyrə nömrələri həmişə solunda və sağında boşluqla göstərilir. Bundan əlavə, bütün çıxışı haş işarələrindən '#' ibarət bir sərhədlə əhatə edin ki, tapmacanın sol üst hüceyrəsindəki nömrə həmişə sərhəddən dörd mövqe sağda və sərhəddən üç mövqe aşağıda, sağ alt hüceyrədəki nömrə isə həmişə sərhəddən dörd mövqe solda və sərhəddən üç mövqe yuxarıda yerləşsin.