Sokobanı necə oynamaq barədə təkliflər

Qeyd

Bu təlimatda aşağıdakı terminlərdən istifadə olunacaq:

• hərəkət etmək: itələsə də, itələməsə də işcinin bir addımı.
• yol: hərəkətlərin ardıcıllığı.
• mövqe: işçi və bütün qutuların müəyyən yerdə olması ilə bağlı bütün problem.
• həll: hər qutunun bir nöqtə üzərində olduğu mövqe.
• həll yolu: ilkin mövqedən həllə doğru hərəkətlərin ardıcıllığı.
• ölü mövqe: həll yolu ilə mümkün olmayan mövqe.

Ümumi Strategiya

Ən qısa həll 100, 300 və ya hətta 1000 hərəkətdən ibarət ola bilər (ən sadə oyunumuz 1-də 73 hərəkət, 8-ci oyunda 126 hərəkət lazımdır). Hər bir hərəkət üçün orta hesabla, məsələn, 2 mümkün yol varsa və həll 100 hərəkət tələb edirsə, kobud güc axtarışı həlli tapmaq üçün 2¹⁰⁰ yolu axtarmağı tələb edəcək. Hətta kompüterlər üçün bu mümkün deyil. Buna görə də bizə lazımdır:

1. mövqe ölübsə, onu erkən tanımaq.
2. ümumi məqsədi alt tapşırıqlara parçalamaq. Əgər 100 hərəkətdən ibarət həll yolu parçalana bilirsə, deməli, 10 alt tapşırıq o zaman problemin mürəkkəbliyi kəskin şəkildə azalır. Bundan başqa, alt tapşırıqların yerinə yetirilməsi lazım olan nizamı aradan qaldırmaq və sonra bütün problemi həll etmək asanlaşır,
3. həll yolunda məhdudiyyətlər tapın,
4. digər heuristikalar haqqında düşünün.

Təxminən 1) Ölü mövqeləri erkən tanımaq

1.1) Bəzən bir mövqenin ölü olub-olmadığına qərar vermək asandır, yalnız bir qutunun qonşuluğuna baxmaq lazımdır. Bunun üçün lazım olan hər şey “yerli” yoxlamadır. Bir qutu nöqtə üzərində dayanmırsa və üfüqi deyil, şaquli olaraq hərəkət edə bilmirsə, mövqe ölüdür. Qutu divar və ya başqa qutular tərəfindən bloklana bilər, onları da daşımaq mümkün deyil.

1.2) Əgər qutu divarın yanındadırsa və onu itələmək mümkündürsə, ancaq eyni tərəfdəki divar boyunca və onun çata bildiyi yerlərdən heç biri yoxdursa, mövqenin ölü olduğunu görmək bir qədər çətindir.

1.3) Bu ümumiləşdirmədə qutu divarın yanındadır və onun tərəfində divarı olmayan yerə (aşağıda A yeri) köçürülə bilər, lakin bu boş qonşu A yeri ola bilməz. işçi A-nın yanındakı qutunu itələdikdən sonra çatdı.

Bu üç hal yerli olaraq və işçini köçürmədən həll edilə bilər. Beləliklə, onlar ilkin vəziyyətdə yoxlanıla bilər və yerləri, məsələn ! ilə qadağan edilmiş kimi qeyd etmək olar ki, belə bir qutu heç vaxt bu yerə hərəkət etdirilməsin.

1.4) Əlavə ümumiləşdirmədə A yerinə işçi çata bilər, ancaq qadağan olunmuş yerə başqa bir qutu qoymaq qiymətinə.

Bu izahat rekursivdir^[1], yəni 'ölü mövqe' sözlərindən istifadə etməklə ölü mövqeyi xarakterizə edir. Bu cür ölü mövqeləri tanımaq daha çətindir, çünki onlar yerli yoxlama ilə aşkar edilə bilməz və sınaq hərəkətləri tələb oluna bilər.

Təxminən 2) Alt tapşırıqların tərtibi

Alt tapşırıqlara misal olaraq:

1. İşçini A-dan B-yə hərəkət etdirin,
2. Müəyyən qutunu A-dan B-yə hərəkət etdirin

burada bu vəzifələrin hər biri ölü mövqe yaratmadan yerinə yetirilməlidir.

(a) - ya misal: A-ya çatmaq üçün işçi qutudan necə keçə bilər:

İşçi qutunun ətrafında gəzməli olduğu üçün bütün boş yer lazımdır. Daha az boş yer varsa, işçi ölü mövqe yaratmadan qutunu keçə bilməz.

Əgər dəhlizin formaları ilə belə bir çox alt tapşırıqları əzbər bilirsinizsə, bu barədə düşünməyə ehtiyac qalmayaraq çox vaxta qənaət etmiş olursunuz, burada bu 9 hərəkət yolu. Daha da əhəmiyyətlisi, kimsə bu alt tapşırığın qeyri-mümkün olduğunu düşündüyü üçün imtina etməyəcək.

Alt tapşırıqlarla bağlı sual onları necə tapmaqdır. Məsələn, problemi tərsinə həll edərkən alt tapşırıqlar ortaya çıxır. Tutaq ki, müəyyən bir nöqtəyə yalnız bir tərəfdən və yalnız bir qutu ilə çatmaq olar. Bu qutu nəticədə müəyyən bir istiqamətə itələməlidir. Bunun üçün işçi onun digər tərəfinə keçməlidir. Tapşırıq qutunu və işçini düzgün mövqeyə gətirmək ola bilər.

Alt vəzifə ilə gəlməyin başqa bir tipik nümunəsi aşağıdakılardır. Həll üçün bir mövqedəki bütün daxili məkanın lazım olduğunu güman etmək təhlükəsizdir. Bu o deməkdir ki, əgər orijinal mövqedə yuxarıdakı misaldakı 2 dəfə 3 boş sahə kimi böyük daxili boşluqlar varsa, o zaman həmin məkanın məqsədinin nə olduğunu soruşmaq olar. Ola bilər ki, o, işçiyə bir qutudan keçmək üçün lazımdır və ya aralıq olaraq başqa yerdə yer boşaltmaq üçün müvəqqəti olaraq bir qutu saxlamaq üçün istifadə olunur. Beləliklə, böyük yer müvəqqəti olaraq bir qutu saxlamağa qadirdirsə, bu hansı qutu ola bilər? Bu qutunu bu aralıq dayanacaqa necə çatdırmaq olar?

Təxminən 3) Həll yolunda məhdudiyyətlərin formalaşdırılması

Hərəkətləri sınamadan yalnız mövqeyə baxmaqla həll yolunda bir çox məhdudiyyətlər var. Nümunələr bunlardır:

3.1) Bir qutu ilə girilə bilən bir dəhliz var, lakin qutu heç vaxt bütün dəhlizdən keçə bilməz və buna görə də dəhlizin bitdiyi tərəfdən dəhlizin sonundakı boşluğa heç vaxt çatmaq mümkün deyil.

3.2) Müxtəlif tərəflərdə boş yer olmasına baxmayaraq, müəyyən nöqtəyə yalnız bir tərəfdən çatmaq olar.

3.3) Müəyyən bir qutu heç vaxt müəyyən istiqamətə köçürülə bilməz və buna görə də yalnız bir xüsusi nöqtəyə çata bilər.

3.4) Nöqtələrə qutularla yalnız hansısa tərəfdən çatmaq mümkün olduğundan, o, nöqtələrin tutulmalı olduğu sıranı müəyyən edir.

3.5) İşçinin qutusunu müəyyən istiqamətə itələmək üçün boşluq tələb olunduğundan, sonuncu hansı nöqtənin örtülməsi lazım olduğu aydın ola bilər.

Təxminən 4) Digər Heuristika

4.1) Geri qaytarıla bilən hər hansı bir təkan ardıcıllığı sınaqdan keçirilə bilər və sınanmalıdır, hətta bu, işçinin bu təkanları geri qaytarmaq üçün digər tərəfdən itələmək üçün uzun bir yol qət etməli olduğunu bildirsə belə. Belə bir məşq mənasız görünsə belə, yeni mövqedə necə davam etmək üçün yeni imkanlar aça bilər.

4.2) Əgər ən azı bir qutudan bütün nöqtələri ayıran düz xətt varsa, bu qutu həmin xətti keçməlidir. Bu mümkün deyilsə, mövqe ölüdür. Əgər qutunun həmin xətti keçməsi üçün yalnız bir yol varsa, bu, həll yolu üçün güclü məhdudiyyətdir.

Tam həllin nümunəsi (8-ci oyun)

Nöqtələri etiketləmək üçün koordinatları təqdim edirik. Məsələn, işçi əvvəlcə G1 nöqtəsindədir.

Əvvəlcə işçinin yalnız 2 variantı var: a) G3 dəliyindən keçmək və ya b) E3 dəliyindən keçmək. G3-dən keçmək yalnız işçiyə B3-dəki qutunu B1-ə itələməyə imkan verir & # x2192; Beləliklə, işçi E3 dəliyindən B2-yə keçir:

Bizim edə biləcəyimiz yeganə təkan a) B3-dən B4-ə qədər (ölüm mənasını verən B5-ə deyil) və ya C2 qutusunu sağa.

Biz başa düşürük ki, qutuları G3-dən keçən yolda nöqtələrə köçürmək mümkün deyil, çünki onlar heç vaxt sonra sola köçürülə bilməz (bax 1.2).

Amma onları B3,C3 dəliyindən keçirtmək üçün bu sahədə boş yerə ehtiyacımız var, ona görə də sağda bir və ya iki qutu saxlamalı və sonra onları geri götürməliyik.

Biz həmçinin başa düşürük ki, B3 qutusu yalnız B xəttinə köçürülə bilər və buna görə də nəhayət B4 nöqtəsində bitməli olacaq.

Sonrakı qutuları C4-ə köçürmək və sonra onları sağa itələmək üçün işçi A4-ə keçə bilməlidir, lakin aşağıdan oraya çatmaq üçün B3 qutusu B2-də və B3, C3, C2 boşluqları boş olmalıdır, buna görə də iki qutu yoldan çıxmalı və aşağı sağda dayandırılmalıdır.

lakin A3 və ya B3 qutularını aşağı itələmək alınmır. (2) mövqeyində əldə etdiyimiz yeganə başqa variant əvvəlcə B3 qutusunu B4-ə itələmək və sonra (3) mövqeyinə aparan hərəkətləri etməkdir. Alırıq

İndi biz C3 qutusunu C2-yə itələməklə irəliləyişə nail ola bilərik və F2 qutusunu G2 və G3-ə itələmək üçün işçi ilə birlikdə hərəkət edə bilərik:

Yuxarıda müzakirə edildiyi kimi, bizə pulsuz B3, C3, C2 boşluqları lazımdır və B4 qutusunu B2-yə endirək, buna görə də C2 qutusunu müvəqqəti olaraq G2-də park etməliyik. Biz əldə edirik:

İndi biz əvvəlki planımıza əməl edə və onu daha da sağa itələmək üçün G2 qutusunu C4-ə itələyə bilərik:

Sualımız belədir: C4 qutusunu nə qədər sağa itələməliyik. Biz hələ də G3 qutusunu eyni yolla itələməliyik, çünki işçini G4-ə çatdırmalıyıq və bunun üçün C4 qutusunu F4-ə qədər itələməliyik və G4-ü G3-ə itələmək üçün işçini G4-ə aparmalıyıq:

Qutu G2-nin sola keçməsi üçün işçi sayğacı saat əqrəbinin əksi ilə H2-yə qədər getməlidir.

Qalanları sadədir: qutu G2-ni itələyir C2-yə, C4-ə, D4-ə itələyir.

sonra B2 qutusunu B4-ə itələyir və sonra işçi G4-ə keçir ki, nəhayət, F4 qutusunu E4 nöqtəsi üzərinə itələyir.

YERINƏ YETİRİLDİ.