Slink

Slitherlink, Sudoku-nu məşhurlaşdıran Yaponiyanın Nikoli şirkəti tərəfindən nəşr olunan bir tapmacadır. Slitherlink tapmacaları getdikcə daha da məşhurlaşır və artıq dünyanın müxtəlif yerlərində Slitherlink tapmacalarından ibarət kitablar çap olunur. Tapmacaların qaydası sadədir, lakin həll etmək çətin ola bilər. Hər bir tapmaca nöqtələrdən ibarət düzbucaqlı şəbəkədir və bu nöqtələrdən yaranan hüceyrələr ya boş olur, ya da $0$-dan $3$-ə qədər bir tam ədəd ehtiva edir. Məqsəd nöqtələri xətt seqmentləri ilə birləşdirərək elə bir dövr (hər bir nöqtədə yalnız iki kənar olan birləşik yol) qurmaqdır ki, istənilən rəqəm olan hüceyrənin üzərində göstərilən qədər kənar bu hüceyrəyə bitişik olsun. Dəyəri olmayan hüceyrələrdə isə istənilən sayda kənar ola bilər. Həmişə yeganə həllə zəmanət verilən düzgün Slitherlink tapmacasında kifayət qədər qeyri-boş hüceyrə olur. Aşağıda Nikoli saytından götürülmüş bir Slitherlink tapmacasının nümunəsi və onun həlli göstərilib.

Tokio Universitetindən Takayuki Yato sübut edib ki, ümumi Slitherlink problemi NP-tamdır. (Bu anlayışla tanış deyilsinizsə, qeyri-rəsmi desək, bu o deməkdir ki, problemin “səmərəli” həll alqoritmi yoxdur.) Lakin bir qədər dəyişiklik və sadə evristikalarla proqramlaşdırılmış həllər tapmaq mümkündür. Slink adlandırdığımız yeni tapmaca Slitherlink-dən yalnız bir cəhətinə görə fərqlənir: tapmacada heç bir boş hüceyrə yoxdur. Yəni, hər bir hüceyrədə bitişik kənarların sayı göstərilməlidir. Aşağıda yuxarıdakı Slitherlink tapmacasının Slink-ə çevrilmiş forması verilmişdir (əlavə edilmiş ədədlər boz rəngdə göstərilib). Qeyd edək ki, həll dəyişmir, sadəcə tapmacada verilən məlumatlar artır.

Slink üçün həll evristikaları bilavasitə tapmacanın öz mahiyyətindən yaranır. Məsələn, sıfır olan hüceyrələri nəzərdən keçirək. Burada heç bir bitişik kənar ola bilməz, buna görə bütün sıfırların ətrafındakı kənarları dərhal həll yolundan çıxarmaq olar. İndi sıfırın yanında üç olan bir hüceyrəni götürək. Sıfıra bitişik olan bütün kənarlar aradan qaldırıldıqda, üçlüklə sıfırın ortaq kənarı da aradan qalxır. Beləliklə, üçlüyün ətrafında yalnız üç kənar qalır və deməli, həmin üç kənar həll yolunun bir hissəsidir. Aşağıdakı cədvəldə Slink tapmacasını həll etmək üçün tətbiq olunmalı olan evristik qaydalar göstərilmişdir. Qrafikdə nöqtələr arasındakı "x" işarələri həll yolunda olmayan kənarları, xətt seqmentləri isə həll yolunun tərkibi olan kənarları göstərir. Boz elementlər qaydaya əsaslanan nümunəni, qara elementlər isə uyğunluq tapılıbsa əlavə edilməli və ya çıxarılmalı olan kənarları göstərir. Qeyd edək ki, göstərilən nümunələr sadəcə izah məqsədlidir və qaydanın bütün mümkün vəziyyətlərini əhatə etmir!