Sokoban©
Suggestions on how to play Sokoban
Notation
The following terms will be used throughout this guide:
- move: one step of the worker whether pushing or not pushing a box.
- path: a sequence of moves.
- position: the whole problem with the worker and all boxes being at a certain place.
- solution: a position where each box is sitting on a dot.
- solution path: the sequence of moves from the original position to the solution.
- dead position: a position from which the solution can not be reached.
General Strategy
The shortest solution might contain 100, 300 or even 1000 moves (our simplest game 1 already needs 73 moves, game 8 needs 126 moves). If there are on average, say, 2 possibilities for each move and the solution takes 100 moves then a brute force search would require to search 2100 paths to find the solution. Even for computers this is not possible. We therefore need to:
- recognize early if a position is dead,
- break down the overall goal into sub tasks. If a solution path of 100 moves can be broken down into, say, 10 sub tasks then the complexity of the problem is drastically reduced. Furthermore it might be possible to deduce the order in which the sub tasks need to be completed and then the whole problem becomes easy to solve,
- find restrictions on the solution path,
- think about other heuristics.
About 1) Recognizing dead positions early
1.1) Sometimes it is easy to decide whether a position is dead, one only has to look at the neighbourhood of one single box. All it takes is a 'local' inspection. If a box does not stand on a dot and can not be moved horizontally and not vertically, then the position is dead. The box may be blocked by the wall or by other boxes which also can not be moved.
Examples:
1.2) It is slightly harder to see that a position is dead if the box is next to a wall and it can be pushed but only along the wall on the same side and none of the places it can reach is a dot.
Example:
1.3) In this generalization the box is next to a wall and can be moved to a place where it has not the wall on its side (place A below), but that free neighbouring place A can not be reached by the worker after pushing the box next to A.
Example:
These three cases can be decided locally and without moving the worker. Thus they can be checked out in the initial position and one can mark places as forbidden, say, with ! so that a box may never be pushed on such a place.
1.4) In a further generalization the place A can be reached by the worker but only at the price of putting another box at a forbidden place.
Example:
This explanation is recursive[1], i.e. it characterizes a dead position by using the words 'dead position'. Such dead positions are harder to recognize because they can not be detected by local inspection and might need test moves.
About 2) Formulating Sub Tasks
Examples of sub tasks are:
- Move the worker from A to B,
- Move a certain box from A to B
where each of these tasks is to be accomplished without creating a dead position.
Example for (a): How the worker can pass a box to get to A:
→
→
→
→
All the empty space is needed as the worker has to walk around the box. If there is less empty space then the worker can not pass the box without generating a dead position.
If one knows many such subtasks with their shapes of the corridor by heart then one saves much time by not needing to think about it, here this 9-move-path. More importantly one will not give up because one thinks this sub task is impossible.
A question related to subtasks is how to find them. Subtasks come up, for example, when solving the problem reversely. Suppose a certain dot can only be reached from one side and only by one box. This box consequently needs to be pushed in a particular direction. In order to do so the worker needs to get to the other side of it. A task could be to bring the box and worker in the right position.
Another typical example of coming up with a sub task is the following. It is safe to assume that all interior space in a position is needed for the solution. That means, if the original position has bulky inner spaces, like the 2 times 3 empty area in the above example, then one can ask what is the purpose for that space. It could be that it is needed by the worker to pass a box or it is used to park temporarily a box to free space somewhere else intermediately. So if the bulky space is capable of storing a box temporarily then which box could that be? How can one get this box to this intermediate parking spot?
About 3) Formulating Restrictions on the Solution Path
There are many restrictions on the solution path possible just by looking at the position without trying out moves. Examples are:
3.1) There is a corridor that can be entered by a box but the box can never move through the whole corridor and therefore the space at the end of the corridor can never be reached from the side where the corridor ends.
eg) Point A can never be reached by a box sitting on B and B can not be reached by a box sitting on A by going through the corner.
3.2) A certain dot can be reached only from one side even though there is free space on different sides.
eg) The dot can not be reached by a box from below.
3.3) A certain box can never be moved in a certain direction and therefore can only reach one specific dot.
eg) The box can only reach the dot on its left.
3.4) Because dots can be reached by boxes only from some side it determines the order in which dots must be occupied.
eg) In the following position the left dot has to be occupied before the dot to the right of it.
3.5) It may be clear which point needs to be covered last because the space is needed for the worker to push a box in a certain direction.
eg) The space of the most right dot is needed for the worker to stand and push a box to the left, so the most right dot is the last to be occupied (in the same picture as above).About 4) Other Heuristics
4.1) Any sequence of pushes that can be reversed can and should be tried out, even if it means that the worker has to go a long way in order to push from another side to reverse these pushes. Even if such an exercise looks pointless, the new position may open new possibilities of how to proceed.
4.2) If there is a straight line that separates all dots from at least one box, then this box must cross that line. If this is not possible then the position is dead. If there exists only one way for the box to cross that line then this is a strong restriction for the solution path.
Example of a Complete Solution (Game 8)
(1)
We introduce coordinates to label points. For example, the worker is initially at point G1.
Initially the worker has only the 2 options: a) to go through hole G3, or b) to go through hole E3. Going through G3 does only allow the worker to push the box at B3 to B1 → death. So the worker goes through the hole E3 to B2:
(2)
The only pushes we can make is a) box B3 up to B4 (not to B5 which means death) or box C2 to the right.
We realize that boxes can not be moved to dots on a route through G3 because they could never be moved to the left afterwards (see 1.2).
But in order to move them through the hole B3,C3 we need space in this area, so we need to park one or two boxes on the right and have to get them back afterwards.
We also realize that box B3 can only be moved on the B line and therefore will finally have to end on dot B4.
To move later boxes on C4 and then to push them to the right, the worker must be able to move to A4 but to get there from below, box B3 must be at B2 and spaces B3, C3, C2 must be free, so two boxes must get out of the way and be parked in the lower right.
So, to get box C2 out of the way and get the worker to the left top, we could use example 2.1 and reach
(3)
but pushing down boxes A3 or B3 does not work. The only other option we had in position (2) is to push box B3 up to B4 first and then to do the moves leading to position (3). We get
(4)
Now we can make progress by pushing box C3 down to C2 and move with the worker around to push box F2 to G2 and G3:
(5)
As discussed above, we need spaces B3,C3,C2 free and get box B4 down to B2 so we need to park box C2 temporarily on G2. We get:
(6)
Now we can follow our earlier plan and push box G2 to C4 in order to push it further to the right:
(7)
The question is how far right do we have to push that box C4. Because we still need to push box G3 through the same path we need to get the worker to G4 and to do that we need to push box C4 as far as F4 and move the worker to G4 to push G4 to G3:
(8)
To move box G2 to the left the worker needs to go all the way back counter clockwise to H2.
(9)
The rest is simple: box G2 is pushed to C2, C4, D4
(10)
then box B2 is pushed to B4 and then the worker moves to G4 to finally push box F4 on dot E4.
DONE.
Someone is bankrupt if the person owns someone else money and has no cash money and either has no receipt for having borrowed someone else money, or has a receipt for having borrowed someone else money but that person is bankrupt.
This explanation of the word bankrupt uses the word bankrupt, and therefore it is called recursive.
Example:
Persons A,B,C have no money, all of them owe some money to person D,
A has a receipt for borrowing money to B,
B has a receipt for borrowing money to C,
C has a receipt for borrowing money to A
but they are as a group bankrupt, each one of them.
Similar but different situation:
Persons A,B,C have no money, all of them owe some money to person D,
A has a receipt for borrowing money to B,
B has a receipt for borrowing money to C,
C has a receipt for borrowing money to F.
Because person F might have money, it may be that none of A,B,C are bankrupt.
To distinguish between the two cases one needs to look at all relations, not only one individually because the above definition of bankruptcy is recursive.
Quelques Conseils sur Comment jouer Sokoban
Notation
Les termes suivants seront utilisés dans ce guide:
- mouvement: une étape du travailleur soit de pousser ou de ne pas pousser une boîte.
- chemin: une séquence de mouvements.
- position: le problème dans sa totalité avec le travailleur et toutes les cases se trouvant dans un lieu donné.
- solution: une position où chaque boîte est sur un point.
- chemin de solution:la séquence de mouvements de la position initiale à la solution.
- position de point mort: une position à partir de laquelle la solution ne peut pas être atteinte.
Stratégie générale
La solution la plus courte peut contenir 100, 300 ou même 1 000 mouvements (dans notre première et le plus simple jeu on a besoin de 73 mouvements, dans le huitième jeu on a besoin de 126 mouvements). Si il y a au moyenne 2 possibilités pour chaque mouvement et la solution prend 100 mouvements, il faudrait chercher 2100 chemins pour trouver la solution. Même pour les ordinateurs ceci est impossible. Donc, il faut:
- reconnaître tôt si une position est une position de point mort,
- diviser l'objectif global en sous-tâches. Si un chemin de solution de 100 mouvements peut être divisé en 10 sous-tâches alors la complexité du problème est considérablement réduite. En outre, il pourrait être possible de déduire l'ordre dans lequel les sous-tâches doivent être réalisées et puis tout le problème devient facile à résoudre,
- trouver des restrictions sur le chemin de la solution,
- penser à d'autres heuristiques.
1) 1) Reconnaissant des positions du point mort tôt
1.1) Parfois, il est facile a décider si une position est du point mort, il suffit de regarder la région environnante d'une seule boîte. Elle exige seulement une inspection «local». Si une boîte ne se trouve pas sur un point et elle ne peut pas être déplacée horizontalement ou verticalement, la position est du point mort. La boîte peut être bloquée par le mur ou par d'autres boîtes qui aussi ne peut pas être déplacé.
Exemples:
1.2) Il est un peu plus difficile de voir qu'une position est du point mort si la boîte est à côté d'un mur et elle peut être poussée mais seulement le long du mur du même côté et aucun des lieux qu'il peut atteindre est sur un point.
Exemple:
1.3) Dans cette généralisation, la boîte est à côté d'un mur et peut être déplacé vers un endroit où il ne se trouve pas du côté du mur (voir A ci-dessous), mais cette place disponible ne peut être atteinte par le travailleur après avoir poussé la boite à côté de A.
Exemple:
Ces trois cas peuvent être décidées localement et sans déplacer le travailleur. Ainsi, ils peuvent être vérifiés dans la position initiale et on peut marquer des lieux comme interdit en utilisant le symbole "!" de sorte qu'une boîte ne peut jamais être poussé sur ces endroits.
1.4) Dans une autre généralisation le lieu indiqué par A peut être atteint par le travailleur mais seulement au prix de mettre une autre boîte à un endroit interdit.
Exemple:
Cette explication est récursive.[1], Cela veut dire qu'elle caractérise une position de point mort en utilisant les mots: position de point mort. Ces positions de point mort sont plus difficile à reconnaître car elles ne peuvent pas être détectées par l'inspection locale et pourraient avoir besoin de mouvements exprimental.
2) Formuler des sous-tâches
Exemples des sous-tâches:
- Déplacez le travailleur de A à B,
- Déplacez une boite de A à B
woù chacune de ces tâches doit être accomplie sans la création d'une position de point mort.
Exemple pour (a): Comment le travailleur peut passer une boîte pour arriver à A:
→→→→
Tout l'espace vide est nécessaire puisque le travailleur doit marcher autour de la boîte. S'il y a moins d'espace vide, le travailleur ne peut pas passer la boîte sans générer une position de point mort.
Quand on connaît beaucoup de ces sous-tâches avec leurs formes du corridor par coeur, alors on économise beaucoup de temps par ne pas avoir besoin de réfléchir à ce sujet, voici une 9-mouvement-chemin. Plus important on ne va pas abandonner parce que on pense de cette sous-tâche est impossible.
Une question liée à des sous-tâches est comment savoir les trouver. Sous-tâches viennent, par exemple, lorsque la résolution du problème à l'envers. Supposons un certain point ne peut être atteint à partir d'un côté et par une seule boîte. Cette boîte par conséquent doit être poussée dans une direction particulière. Pour ce faire, le travailleur doit se rendre à l'autre côté de cette boîte. Une tâche pourrait être d'apporter la boîte et le travailleur dans la bonne position.
Un autre exemple typique de génération d'une sous-tâche est la suivante. Il est prudent de supposer que tout l'espace intérieur dans une position est nécessaire pour la solution. Cela signifie que, si la position d'origine a espaces intérieurs volumineux, comme le 2 fois 3 zone vide dans l'exemple ci-dessus, alors on peut se demander quel est le but de cet espace. Il pourrait être que cela est nécessaire par le travailleur de passer une boîte ou il est utilisé pour garer temporairement une boîte à l'espace libre ailleurs intermédiairement. Donc, si l'espace volumineux est capable de garder temporairement une boîte, quelle boîte serait-elle? Comment peut-on mettre cette boîte à cet endroit intermédiaire?
3) Formuler des Restrictions sur le Chemin de Solution
Il y a beaucoup de restrictions sur le chemin solution possible qui sont remarquables juste en regardant la position et sans essayer déplace. Quelques exemples sont:
3.1) Il y a couloir qui une boîte peut entrer, mais ne peut jamais se déplacer à travers l'ensemble du couloir. Par conséquent, l'espace à la fin du couloir ne peut jamais être accessible à partir du côté où le couloir se termine.
Par exemple) Point A ne peut jamais être accessible par une boîte assis sur B et B ne peut pas être accessible par une boîte assis sur le point A en passant par le coin.
3.2) Un certain point peut être atteint que d'un côté même s'il y a un espace vide sur des côtés différentes.
Par exemple) Le point ne peut pas être atteint par une boîte de dessous.
3.3) Une certaine boîte ne peut jamais être déplacée dans une certaine direction, et donc ne peut atteindre un point spécifique.
Par exemple) La boîte ne peut atteindre le point sur sa gauche.
3.4) Puisque des points peuvent être atteints par des boîtes à partir de seulement certains côtés, il détermine l'ordre dans lequel des points doivent être occupés.
Par exemple) dans la position suivante le point gauche doit être occupé avant le point vers la droite.
3.5) Le point spécifique qui doit être le dernier à être couverte peut être évident considérant l'espace nécessaire pour le travailleur de pousser une boîte dans une certaine direction.
eg) L'espace du point le plus à droite est nécessaire pour le travailleur de se lever et pousser une boîte à la gauche, de sorte que le point le plus à droite est le dernier à être occupé (en la même image comme ci-dessus).4) Autres Heuristiques
4.1) Toute séquence de poussées qui peuvent être inversés peuvent et doivent même être jugés, même si cela signifie que le travailleur doit parcourir un long chemin afin de pousser d'un autre côté pour inverser ces poussées. Même si un tel exercice semble inutile, la nouvelle position peut ouvrir de nouvelles possibilités pour une façon de procéder.
4.2) S'il est une ligne droite qui sépare tous les points d'au moins une boîte, puis cette case doit traverser cette ligne. Si cela est impossible, la position est du point mort. S'il existe une seule façon pour la boîte à traverser cette ligne alors ceci est une forte restriction de la chemin de solution.
Exemple d'une Solution Complète (Game 8)
(1)
Nous introduisons les coordonnées pour marquer les points. Par exemple, le travailleur est initialement au point G1.
Initialement, le travailleur a seulement les 2 options: a) de passer par le trou G3, ou b) de passer par le trou E3. En passant par G3 ne permet au travailleur de pousser la boîte de B3 à B1 ? la mort. Donc, le travailleur passe par le trou E3 à B2:
(2)
Les seules poussées que nous pouvons faire sont a) boîte B3 jusqu'à B4 (plutôt que B5 qui signifie la mort) ou la boîte C2 vers la droite.
Nous voyons que les boîtes ne peuvent pas être déplacés vers des points sur une route à travers G3 car elles ne pourraient jamais être déplacées vers la gauche par la suite (voir 1.2).
Mais afin de les faire passer par le trou B3, C3 nous avons besoin d'espace dans ce domaine, nous avons donc besoin de garder une ou deux boîtes sur le droit et les remplacer par la suite.
Nous voyons aussi que la boite B3 ne peut être déplacé sur la ligne B et donc aura finalement terminer sur le point B4.
Pour déplacer des boîtes subséquentes sur C4 et ensuite de les pousser vers la droite, le travailleur doit être capable de se déplacer à A4, mais pour y arriver du dessous, boîte B3 doit être à B2 et des espaces B3, C3, C2 doit être vide, de sorte que deux boîtes doivent être déplacées et gardées dans le coin inférieur droit.
Donc, pour déplacer boîte C2 et déplacer le travailleur en haut à gauche, nous pourrions utiliser l'exemple 2.1 pour atteindre
(3)
mais en poussant des boîtes A3 ou B3, on n'a pas atteindre le résultat requis. La seule autre option qui existe en position (2) est de pousser boîte B3 jusqu'à B4 d'abord et ensuite faire les mouvements qui se terminera à la position (3). Nous obtiendrions
(4)
Maintenant, nous pouvons faire des progrès en poussant boîte C3 jusqu'à C2 et déplacer le travailleur pour pousser boîte F2 jusqu'à G2 et G3:
(5)
Comme indiqué plus haut, nous avons besoin des espaces B3, C3, et C2 d'être vide et de déplacer B4 vers le bas. De plus,on a besoin de garder C2 sur G2 temporairement. Nous obtiendrons:
(6)
Maintenant, nous pouvons suivre notre plan et nous pouvons pousser boîte G2 à C4 afin de pousser plus loin vers la droite:
(7)
Nous avons besoin de savoir comment loin vers la droite, nous devons pousser boîte C4. Parce que nous avons encore besoin de pousser boîte G3 par le même chemin que nous devons faire passer le travailleur à G4 et pour ce faire nous avons besoin de pousser boîte C4 autant que F4 et déplacer le travailleur à G4 pour pousser G4 à G3:
(8)
Pour déplacer boîte G2 vers la gauche le travailleur doit retourner dans une façon antihoraire à H2.
(9)
Le reste est simple: boîte G2 est poussé à C2, C4, puis D4
(10)
alors boîte B2 est poussé à B4 et le travailleur se déplace à G4 pour finalement pousser boîte F4 sur le point E4.
TERMINÉ.
Quelqu'un a fait faillite si la personne doit payer une somme d'argent, n'a pas d'argent en espèces et soit ne pas avoir un reçu pour avoir emprunté de l'argent à quelqu'un d'autre, ou a un reçu pour avoir emprunté de l'argent à quelqu'un d'autre, mais cette personne a fait faillite.
Cette explication de faire faillite utilise les mots eux-même et, donc il est appelé récursive.
Exemple:
Personnes A, B, et C n'ont pas de l'argent, chacun d'entre eux doivent doit donner une somme de l'argent à personne D,
Personne A a un reçu pour emprunter de l'argent à B,
Personne B a un reçu pour emprunter de l'argent à C,
Personne C a un reçu pour emprunter de l'argent à A.
comme individus et comme groupe, ils ont fait faillite.
Similar situation:
Personnes A, B, C n'a pas d'argent, chacun d'entre eux doit donner une somme de l'argent à personne D,
Personne A a un reçu pour emprunter de l'argent à B,
Personne B a un reçu pour emprunter de l'argent à C,
Personne C a un reçu pour emprunter de l'argent à F.
Parce que personne F pourrait avoir de l'argent, il peut être qu'aucun de A, B, C fait faillite.
Pour distinguer les deux cas, on doit tenir compte de toutes les connexions, non seulement individuellement parce que la définition ci-dessus de la faillite est récursive.
توصیه هایی در راستای چگونگی بازی سوکوبان
نوشتار
عبارات زیر در حین این راهنمایی استفاده می شوند:
- حرکت: یک قدم کارگر چه جعبه ای را حرکت بدهد چه ندهد.
- مسیر: دنباله ای از حرکات.
- موقعیت: کل این مساله با در نظر گرقتن کارگر و همه ی جعبه ها در یک موقعیت خاص.
- پاسخ: موقعیتی که در آن هر جعبه ای روی یک نقطه قرار دارد.
- مسیر پاسخ: دنباله ای از حرکات از موقعیت اصلی به پاسخ.
- موقعیت مرده: موقعیتی که از آن پاسخ نمی تواند به دست آید.
استراتژی کلی
کوتاهترین پاسخ ممکن است شامل ۱۰۰، ۳۰۰ یا حتی ۱۰۰۰ حرکت. ساده ترین بازی ۱ ما ۷۳ حرکت لازم دارد، بازی ۸، ۱۲۶ حرکت لازم دارد. اگر به طور متوسط، فرض کنید، ۲ احتمال برای هر حرکت و پاسخ ۱۰۰ حرکت می خواهد، آنگاه یک جستجوی جامع ممکن است نیازمند جستجوی ۲۱۰۰ مسیر برای پیدا کردن پاسخ باشد. حتی برای رایانه ها این ممکن نیست. در نتیجه ما لازم است که:
- زود تشخیص دهیم اگر موقعیتی مرده است،
- هدف نهایی را به چند کار زیرمجموعه ای تقسیم کنید. اگر یک مسیر پاسخ ۱۰۰ حرکتی بتواند به مثلا، ۱۰ زیر شاخه تقسیم شود، آنگاه پیچیدگی مساله به شدت کاهش پیدا می کند. . به علاوه، ممکن است که بتوان ترتیبی که در آن زیرشاخه باید انحام شود را کاهش داد و آنگاه کل مساله برای حل شدن ساده می شود،
- اولین محدودیت برای مسیر پاسخ،
- به ابتکارهای دیگر فکر کنید.
درباره ی ۱: تشخیص زودهنگام موقعیت های مرده
۱. ۱: گاهی آسان است که تصمیم بگیریم آیا موقعیتی مرده است، فقط کافی است به همسایگی یک جعبه ی تنها نگاه کرد. تنها چیزی که لازم است یک بازرسی موضعی است. اگر جعبه ای روی یک نقطه قرار نگرفته است و نمی تواند به صورت افقی و عمودی حرکت کند، آنگاه آن موقعیت مرده است. جعبه ممکن است با دیوار و یا جعبه های دیگر بلوکه شده باشد که باز هم نمی تواند حرکت کند.
مثال ها:
۱.۲: این اندکی سخت تر است که ببینیم که موقعیتی مرده است اگر که جعبه در کنار دیوار قرار دارد و می تواند هل داده شود اما فقط در راستای دیوار و در جهت یکسان، و هیچ یک از موقعیت هایی که این جعبه می تواند به آن برسد نقطه نمی باشد.
مثال ها:
۱.۳: در این تعمیم جعبه در کنار دیوار قرار دارد و می تواند به موقعیتی که دیوار در کنارش قرار نداشته باشد، حرکت داده شود, نقشه ی A در زیر، اما آن موقعیت همسایه ی خالی الف نمی تواند توسط کارگر بعد از هل دادن جعبه به کنار A به دست آید.
مثال ها:
این سه مورد می توانند به صورت موضعی و بدون حرکت کردن کارگر تصمیم گیری شوند. بنابراین می توانند در موقعیت ابتدایی بررسی شوند و می توان مکان ها را به عنوان ممنوع مشخص کرد، مثلا با ! ، به گونه ای که یک جعبه هرگز نمی تواند به آن مکان ها هل داده شود.
۱.۴: در تعمیم بعدی، مکان A می تواند توسط کارگر به دست آید اما به قیمت اینکه قرار دادن یک جعبه ی دیگر در یک مکان ممنوع.
مثال ها:
این توضیحات بازگشتی می باشد [1], یعنی، یک مکان مرده را با استفاده از کلمه های موقعیت مرده مشخص می کند. چنین موقعیت های مرده ای سخت تر قابل تشخیص هستند زیرا که نمی توانند با بازرسی موضعی پیدا شوند و ممکن است تست حرکت ها لازم باشد.
در مورد ۲: فرمول بندی کردن کارهای زیرمجموعه ای
مثال هایی از کارهای زیرمجموعه ای:
- کارگر را از A به B حرکت دهید،
- یک جعبه ی مشخص را از A به B حرکت دهید
که هر یک از این کارها قرار است که بدون به وجود آوردن موقعیت مرده به دست آید.
مثالی از: اینکه چگونه کارگر می تواند از یک جعبه برای رسیدن به A
بگذرد:→→→→
از آنجایی که کارگر باید اطراف جعبه قدم بردارد، همه ی فضای خالی لازم می باشد. اگر فضای خالی کمتری وجود داشته باشد، آنگاه کارگر نمی تواند از جعبه بدون تولید موقعیت مرده بگذرد.
اگر کسی تعداد زیادی ازاین کارهای زیرمجموعه ای را عمیقا با شکل های آنها می داند، آنگاه می تواند زمان زیادی را با صرف نکردن برای فکر کردن درباره ی آن ذخیره کند، در اینجا این مسیر ۹ حرکتی. با اهمیت تر از آن، فکر مردن به اینکه یک کاز غیر ممکن است باعث تسلیم شدن نخواهد شد.
یک سوال مرتبط با کار زیرمجموعه ای این است که چگونه آنها را پیدا کنیم. به عنوان مثال، کارهای زیرمجموعه ای در زمان حل کردن مساله به صورت برعکس پدیدار می شوند. فرض کنید یک نقطه ی مشخص فقط می تواند از یک طرف فقط یک جعبه در دسترسی قرار بگیرد. در نتیجه این جعبه لازم است که در یک جهت خاص حرکت داده شود. برای انجام این کار، ازم است که کارگر به طرف دیگر آن برسد. یک کار می تواند آوردن جعبه و کارگر به موقعیت درست باشد.
یک مثال متداول دیگر از پیدا کردن کارهای زیر مجموعه ای مثال این است: می توان با خیال راحت فرض کرد که همه ی فضای داخل یک موقعیت برای پاسخ لازم است. این به ین معنی است که اگر موقعیت ابتدایی فضای داخلی حجیمی دارد، مثلا ۲ ضربدر ۳ مساحت خالی در مثال بالا، آنگاه می توان پرسید که هدف این فضا چیست. می تواند این باشد که این فضا لازم است برای کارگر که از جعبه ها عبور کند و یا اینکه استفاده می شود برای پارک موقت یک جعبه به فضای خالی در جای دیگر به صورت فوری. بنابراین اگر فضای وسیع قابلیت این را دارد که جعبه را به صورت موقت نگه داری کند آنگاه آن جعبه کدام می تواند باشد؟ چگونه می توان این جعبه را به نقطه پارکیگ میانی رساند؟
درباره ی ۳: فرمولسازی کردن محدودیت ها روی مسیر پاسخ
محدودیت های زیادی روی مسیر پاسخ قرار دارند که با نگاه کردن به موقعیت و بدون امتحان کردن هیچ حرکتی ممکن هستند. به عنوان مثال:
۳.۱: یک راهرو وجود دارد که می توان با یک جعبه وارد آن شد، اما جعبه هیچوقت نمی تواند در طول کل راهرو حرکت کند و در نتیجه فضای انتهایی راهرو هرگز از طرفی که آن به پایان می رسد مورد دسترسی قرار نمی گیرد.
مثال: با رفتن به گوشه، نقطه ی A هرگز نمی تواند با جعبه ای که در B قرار دارد به دست آید و B نمی تواند با جعبه ای که در A قرار دارد به دست آید.
۳.۲: یک نقطه ی خاص فقط می تواند از یک طرف مورد دسترسی قرار گیرد حتی اگر فضای خالی در طرف های دیگر وجود داشته باشد.
مثال: یک نقطه نمی تواند توسط جعبه ای از پایین مورد دسترسی قرار گیرد.
۳.۳: یک جعبه ی خاص هرگز نمی تواند در یک جهت خاص خرکت داده شود و در نتیجه فقط می تواند به یک نقطه ی خاص دست یابد.
مثال: جعبه فقط می تواند به نقطه ی سمت چپش دست یابد.
۳.۴: از آنجایی که نقطه ها می توانند توسط جعبه ها فقط از بعضی طرف ها مورد دسترسی قرار گیرند، این ترتیبی که در آن نقطه ها باید اشغال شوند را تعیین می کند.
مثال: در موقعیت زیر نقطه ی سمت چپ باید نقطه ی سمت راستش اشغال شود.
۳.۵: این ممکن است که واضح باشد که کدام نقطه لازم است در آخر پوشانده شود، زیرا که فضا برای کارگر لازم است که بتواند جعبه را در یک مسیر خاص هل دهد.
مثال: فضای راست ترین نقطه برای کارگر لازم است تا بایستد و و جعبه را به چپ هل دهد ، بنابراین راست ترین نقطه، آخرین نقطه ایست که باید اشغال شود.درباره ی ۴: ابتکارهای دیگر
۴.۱: هر دنباله ای از هل دادن ها که بتواند معکوس شودمی تواند و باید امتحان شود، حتی اگر به این معنی باشد که کارگر مجبور است راه طولانی برود تا بتواند از طرف دیگر این هل دادن ها را معکوس کند. حتی اگر همچین تمرینی بی ثمر به نظر آید، موقعیت جدید ممکن است که احتمالات جدیدی را برای چگونگی ادامه دادن باز کند.
۴.۲: اگر یک خط مستقیمی وجود دارد که همه ی نقطه ها را از حداقل یک جعبه جدا کند، آنگاه این جعبه باید از آن خط بگذرد. اگر این ممکن نیست آنگاه موقعیت مرده است. اگر برای جعبه فقط یک راه وجود دارد که از آن خط بگذرد آنگاه این یک محدودیت قوی برای مسیر پاسخ است.
مثالی از پاسخ کامل: بازی ۸
(1)
ما مختصات را برای نشانه گذاری نقطه ها معرفی می کنیم. برای مثال، کارگر در آغاز در نقطه ی G1 می باشد.
در آغاز کارگر فقط دو گزینه دارد: الف: الف: رفتن به حفره ی G3 ، یا ب: رفتن به حفره ی E3. رفتن به G3 فقط به کارگر اجازه می دهد که جعبه را در B3 به B1 هل دهد، نتیجه مرگ است. بنابراین کارگر از حفره ی E3 به B2 می رود:
(2)
تنها هل دادن هایی که می توانیم اعمال کنیم الف: جعبه ی B3 تا جعبه ی B4 است یا جعبه ی C2 به راست است.
ما تشخیص می دهیم که جعبه ها نمی توانند به نقاط در مسیر G3 حرکت داده شوند زیرا که آنها بعد از همه ی اینها هرگز نمی توانند به چپ حرکت داده شوند (۱.۲ را ببینید).
اما در راستای حرکت دادن آنها از حفره ی B3,C3 ما فضای این ناحیه را احتیاج داریم، بنابراین لازم است یک یا دو جعبه را به راست حرکت دهیم و مجبوریم بعد از همه ی اینها، آنها را برگردانیم.
ما همچنین تشخیص می دهیم که جعبه ی B3 فقط می تواند روی خط B B حرکت داده شود و در نتیجه در نهایت مجبور است که در نقطه ی B4 خاتمه یابد.
برای حرکت جعبه های بعدی روی C4 و آنگاه هل دادن آنها به سمت راست، کارگر باید قادر باشد که به A4 حرکت کند اما برای رسیدن به آنجا از پایین، جعبه ی B3 باید در B2 باشد و فضاهای B3, C3, C2 باید خالی باشند، بنابراین دو جعبه باید از مسیر خارج شوند و در پایینتر سمت راست پارک شوند.
بنابراین، برای خارج کردن جعبه ی C2 از مسیر و رساندن کارگر به بالا سمت چپ، می توانیم از مثال ۲.۱ استفاده کنیم و برسیم
(3)
اما پایین هل دادن جعبه های A3 یا B3 نتبجه نخواهد داشت. تنها گزینه ی دیگر که در موقعیت ۲ که داشتیم این است که در ابتدا جعبه ی B3 را تا B4 هل دهیم و آنگاه حرکت هایی را اعمال کنیم که منجر به موقعیت ۳ می شوند. بدست می آوریم
(4)
اکنون می توانیم با هل دادن جعبه ی C3 به پایین تا C2 و حرکت کردن با کارگر به اطراف برای هل دادن جعبه ی F2 به G2 و G3 :
(5)
همانطور که در بالا مطرح شد، ما فضاهای B3,C3,C2 را خالی احتیاج داریم و لازم است جعبه ی B4 را پایین تا B2 برسانیم، بنابراین لازم است که جعبه ی C2 به طور موقت روی G2 . پارک کنیم. بدست می آوریم:
(6)
اکنون می توانیم نقشه ی اولیه مان را دنبال کنیم و جعبه ی G2 . را در راستای هل دادنش بعدا به سمت راست به C4 . هل دهیم:
(7)
سوال این است که چه مقدار به سمت راست باید آن جعبه ی C4 . را هل دهیم. زیراکه هنوز لازم است که جعبه ی G3 را در طول مسیری که لازم است کارگر را به G4 G4 برسانیم، هل دهیم و همچنین جعبه ی C4 را تا F4 هل دهیم و کارگر را به G4 برسانیم با G4 را به G3 هل دهد:
(8)
برای هل دادن جعبه ی G2 به چپ، لازم است کارگر تمام راه را در خلاف حرکت عقربه ی ساعت تا H2 برگردد.
(9)
از این پس آسان است: جعبه ی G2 به C2, C4, D4 هل داده می شود
(10)
سپس جعبه ی B2 به B4 هل داده می شود و کارگر به G4 حرکت می کند با سرانجام جعبه ی F4 را روی نقطه ی E4 هل دهد.
تمام شد.
یک نفر ورشکست است اگر آن نفر به شخص دیگری پول بدهکار است و پولی ندارد و یا رسیدی از اینکه پولی از شخص دیگری قرض گرفته ندارد، و یا رسید از اینکه از شخص دیگری پول قرض گرفته دارد اما آن شخص ورشکست شده است.
این توضیح از کلمه ی ورشکست خود کلمه ی ورشکسترا استفاده می کند، و در نتیجه بازگشتی نامیده می شود.
مثال:
افراد A,B,C هیچ پولی ندارند، همه ی آنها مقداری پول به شخص D بدهکارند،
A رسید دارد که از B پول قرض گرفته،
B رسید دارد که از C پول قرض گرفته،
C رسید دارد که از A پول قرض گرفته،
اما اینها به عنوان یک گروه ورشکست هستند، هر یک از آنها.
پاسخی مشابه اما متفاوت:
افراد A,B,C هیچ پولی ندارند، همه ی آنها مقداری پول به شخص D بدهکارند،
A رسید دارد که از B پول قرض گرفته،
B رسید دارد که از C پول قرض گرفته،
C رسید دارد که از F پول قرض گرفته،
از آنجایی که ممکن است شخص F پول داشته باشد، ممکن است که هیچ یک از A,B,C ورشکست نباشند.
برای تشخیص دادن این دو مورد لازم است که به همه ی روابط نگاه کرد، نه فقط به یک مورد، چرا که تعریف بالا از ورشکست بازگشتی است.