Caribou in Covid: Contests are running online as usual. Check out the FAQ for further questions.
300000
English | Français | فارسی | 中文 | Українська | Azerbaijani | ខ្មែរ | Tiếng Việt | Bahasa Melayu131561
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 owes someone else money and has no cash money and either has no receipt for having borrowed someone else’s money, or has a receipt for having borrowed someone else’s 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.
Gợi ý về cách chơi Sokoban
Chú thích
Các thuật ngữ sau sẽ được sử dụng xuyên suốt bản hướng dẫn này:
- Di chuyển: một bước của người thợ dù đẩy hay không đẩy một ô.
- Lộ trình: một chuỗi các bước di chuyển.
- Vị trí: toàn bộ vấn đề liên quan tới người thợ và tất cả các hộp ở một nơi nhất định.
- Giải pháp: một vị trí mà mỗi ô đều nằm trên một dấu chấm.
- Lộ trình giải pháp: chuỗi chuyển động từ vị trí ban đầu đến giải pháp.
- Vị trí chết: một vị trí mà từ đó không thể đạt được giải pháp.
Chiến lược chung
: Lời giải ngắn nhất có thể chứa 100, 300 hoặc thậm chí 1000 nước đi. (Ván 1 đơn giản nhất của chúng ta đã cần 73 nước đi, ván 8 cần 126 nước đi). Nếu trung bình có 2 khả năng xảy ra cho mỗi lần di chuyển và giải pháp thì cần đến 100 lần di chuyển thì một sự tìm kiếm thủ công đầy khó khăn sẽ yêu cầu nghiên cứu 2^100 lộ trình để tìm ra giải pháp. Ngay cả đối với máy tính, điều này là không thể. Do đó, chúng ta cần phải:
- Nhận biết sớm một vị trí đã chết,
- Chia mục tiêu tổng thể thành các nhiệm vụ nhỏ. Nếu một lộ trình giải pháp gồm 100 bước đi có thể được chia nhỏ thành 10 nhiệm vụ nhỏ thì mức độ phức tạp của vấn đề sẽ giảm đáng kể. Hơn nữa, có thể suy ra thứ tự mà các nhiệm vụ nhỏ cần phải hoàn thành và sau đó toàn bộ vấn đề trở nên dễ giải quyết hơn,
- Tìm hạn chế trên lộ trình giải pháp,
- Hãy suy nghĩ về các phương pháp khác.
Phần 1: Nhận biết sớm các vị trí chết
1.1) Đôi khi rất dễ dàng để quyết định xem một vị trí đã chết hay chưa, ta chỉ cần nhìn vào vùng lân cận của một ô duy nhất. Tất cả những gì cần làm là một cuộc kiểm tra 'cục bộ'. Nếu một hộp không đứng trên một dấu chấm và không thể di chuyển theo chiều ngang và cả chiều dọc, thì vị trí đó đã chết. Hộp có thể bị chặn bởi tường hoặc bởi các hộp khác và cũng không thể di chuyển được.
Ví dụ:
1.2) Sẽ hơi khó nhận ra rằng một vị trí đã chết nếu chiếc hộp nằm cạnh một bức tường và nó có thể được đẩy nhưng chỉ dọc theo bức tường cùng phía và nó không thể tới được bất kỳ chỗ dấu chấm nào.
Ví dụ:
1.3) Tổng hợp lại, hộp nằm cạnh một bức tường và có thể được di chuyển đến một nơi không có bức tường ở phía bên của nó (vị trí A bên dưới), nhưng người thợ không thể tới được địa điểm lân cận đang trống đó sau khi đẩy hộp bên cạnh A.
Ví dụ:
Ba trường hợp này có thể được quyết định cục bộ và không cần di chuyển người thợ. Vì vậy, chúng có thể được kiểm tra ở vị trí ban đầu và người ta có thể đánh dấu những nơi bị cấm, chẳng hạn dùng ! để một hộp có thể không bao giờ bị đẩy lên một nơi như vậy.
1.4) Nói một cách tổng quát hơn, người thợ có thể đến được nơi A nhưng chỉ khi đánh đổi đặt một chiếc hộp khác vào một nơi bị cấm.
Ví dụ:
Lời giải thích này là đệ quy[1], tức là nó đặc trưng cho một vị trí chết bằng cách sử dụng các từ vị trí chết. Những vị trí chết như vậy khó nhận ra hơn vì chúng không thể được phát hiện bằng cách kiểm tra tại chỗ và có thể cần đến các lượt di chuyển thử.
Phần 2: Lập Các Nhiệm Vụ Nhỏ
Ví dụ về các nhiệm vụ phụ là:
- Di chuyển người thợ từ A đến B,
- Di chuyển một ô nhất định từ A sang B
Mỗi một nơi trong số những nhiệm vụ này phải được hoàn thành mà không tạo ra một vị trí chết.
Ví dụ cho (a): Làm thế nào để người thợ có thể vượt qua một chiếc hộp để đến A:
→→→→
Tất cả không gian trống là cần thiết vì người thợ phải đi vòng quanh chiếc hộp. Nếu có ít không gian trống hơn thì người thợ không thể vượt qua hộp mà không tạo ra vị trí chết.
Nếu một người biết nhiều nhiệm vụ nhỏ như vậy với hình dạng của hành lang thuộc lòng thì người ta sẽ tiết kiệm được nhiều thời gian mà không cần phải suy nghĩ về nó, đây là lộ trình 9 bước đi. Quan trọng hơn là một người sẽ không bỏ cuộc bởi vì một người nghĩ rằng nhiệm vụ nhỏ này là không thể.
Một câu hỏi liên quan đến nhiệm vụ nhỏ là làm thế nào để tìm chúng. Ví dụ: các nhiệm vụ nhỏ xuất hiện khi giải quyết vấn đề ngược lại. Giả sử một dấu chấm nhất định chỉ có thể đạt được từ một phía và chỉ bằng một hộp. Do đó, hộp này cần được đẩy theo một hướng cụ thể. Để làm như vậy, người lao động cần phải đi đến phía bên kia của nó. Một nhiệm vụ có thể là đưa hộp và người thợ vào đúng vị trí.
Một ví dụ điển hình khác về việc đưa ra một nhiệm vụ nhỏ là như sau. Có một điều chắc chắn khi giả định rằng tất cả không gian nội thất ở một vị trí là cần thiết cho giải pháp. Điều đó có nghĩa là, nếu vị trí ban đầu có không gian bên trong rộng rãi, giống như diện tích trống 2 x 3 trong ví dụ trên, thì người ta có thể tự hỏi mục đích của không gian đó là gì. Có thể là do người thợ cần đến để vượt qua một chiếc hộp hoặc nó được sử dụng để đặt tạm một chiếc hộp nhằm giải phóng không gian ở một nơi khác ngay lập tức. Vậy nếu không gian rộng có khả năng cất giữ một chiếc hộp tạm thời thì đó có thể là chiếc hộp nào? Làm thế nào người ta có thể đưa chiếc hộp này đến điểm đặt trung gian này?
Phần 3: Trình bày Hạn Chế trên Lộ Trình Giải Pháp
Có rất nhiều hạn chế đối với lộ trình giải pháp có thể chỉ bằng cách nhìn vào vị trí mà không thử di chuyển. Ví dụ như:
3.1) Có một hành lang có thể tiến vào bằng một chiếc hộp nhưng chiếc hộp không bao giờ có thể di chuyển qua toàn bộ hành lang và do đó không gian ở cuối hành lang không bao giờ có thể đến được từ phía nơi hành lang kết thúc.
ví dụ, Điểm A không bao giờ có thể chạm tới được bằng một chiếc hộp nằm trên B và không thể chạm tới điểm B bằng một chiếc hộp nằm trên A bằng cách đi qua góc.
3.2) Một dấu chấm nhất định chỉ có thể đạt được từ một phía mặc dù có không gian trống ở các phía khác nhau.
eg) The dot can not be reached by a box from below.
3.3) Một hộp nhất định không bao giờ có thể di chuyển theo một hướng nhất định và do đó chỉ có thể đạt đến một dấu chấm cụ thể.
ví dụ, Cái hộp chỉ có thể chạm tới dấu chấm ở bên trái của nó.
3.4) Bởi vì các dấu chấm có thể được tiếp cận bởi các hộp chỉ từ một số phía nên nó xác định thứ tự các dấu chấm phải được chiếm.
ví dụ, Ở vị trí sau dấu chấm bên trái phải được chiếm trước dấu chấm bên phải của nó.
3.5) Có thể thấy rõ rằng điểm nào cần được che lại cuối cùng bởi vì không gian là cần thiết để người thợ đẩy một hộp theo một hướng nhất định.
ví dụ: Cần có khoảng trống của dấu chấm ngoài cùng bên phải để công nhân đứng và đẩy một ô sang trái, vì vậy dấu chấm ngoài cùng bên phải là ô cuối cùng được chiếm, (trong cùng hình trên).Phần 4: Các Phương Pháp Khác
4.1) Bất kỳ chuỗi đẩy hộp nào có thể đảo ngược đều có thể và nên được thử, ngay cả khi điều đó có nghĩa là người thợ phải đi một quãng đường dài để đẩy từ phía khác để đảo ngược những cú đẩy này. Ngay cả khi một bài tập như vậy trông có vẻ vô nghĩa, vị trí mới có thể mở ra những khả năng mới về cách tiến hành.
4.2) Nếu có một đường thẳng ngăn cách tất cả các dấu chấm khỏi ít nhất một ô, thì ô này phải cắt qua đường thẳng đó. Nếu điều này là không thể thì vị trí đã chết. Nếu chỉ tồn tại một đường để hộp đi qua đường đó thì đây là một hạn chế lớn đối với lộ trình giải pháp.
Ví dụ về Giải pháp Hoàn chỉnh, Trò chơi 8
(1)
Chúng tôi giới thiệu tọa độ để đánh dấu các điểm. Ví dụ, ban đầu người thợ đang ở điểm G1.
Ban đầu người thợ chỉ có 2 lựa chọn: A, đi qua lỗ G3, hoặc B, đi qua lỗ E3. Đi qua G3 không cho phép người thợ đẩy hộp ở B3 đến B1 → dẫn đến điểm chết. Vì vậy, công nhân đi qua lỗ E3 đến B2:
(2)
Cách đẩy duy nhất có thể thực hiện là A, ô B3 lên đến B4 (không phải đến B5 có nghĩa là điểm chết), hoặc ô C2 ở bên phải.
Chúng tôi nhận thấy rằng các hộp không thể được di chuyển đến các dấu chấm trên tuyến đường qua G3 vì chúng không bao giờ có thể được di chuyển sang bên trái sau đó, như đã thấy trong 1.2.
Nhưng để di chuyển chúng qua lỗ B3, C3, chúng ta cần không gian trong khu vực này, vì vậy chúng ta cần phải đặt một hoặc hai hộp bên phải và phải lấy chúng trở lại sau đó.
Chúng tôi cũng nhận ra rằng ô B3 chỉ có thể được di chuyển trên dòng B và do đó cuối cùng sẽ phải kết thúc trên chấm B4.
Để di chuyển các ô sau đó trên C4 và sau đó để đẩy chúng sang phải, công nhân phải có khả năng di chuyển đến A4 nhưng để đến đó từ bên dưới, ô B3 phải ở B2 và các khoảng trống B3, C3, C2 phải trống, vì vậy hai hộp phải ra khỏi đường và được đặt ở phía dưới bên phải.
Vì vậy, để đưa ô C2 ra khỏi đường và đưa người thợ lên trên cùng bên trái, chúng ta có thể sử dụng ví dụ 2.1 và tiếp cận
(3)
nhưng việc đẩy hộp A3 hoặc B3 xuống không khả thi. Lựa chọn duy nhất còn lại mà chúng ta có ở vị trí 2 là đẩy hộp B3 lên B4 trước và sau đó thực hiện các động tác dẫn đến vị trí 3. Chúng ta nhận được
(4)
Bây giờ chúng ta có thể tiếp tục bằng cách đẩy hộp C3 xuống C2 và di chuyển công nhân xung quanh để đẩy hộp F2 đến G2 và G3:
(5)
Như đã thảo luận ở trên, chúng ta cần khoảng trống B3, C3, C2 và đưa hộp B4 xuống B2 nên chúng ta cần tạm thời đậu hộp C2 trên G2. Chúng ta có:
(6)
Bây giờ chúng ta có thể làm theo kế hoạch trước đó của mình và đẩy hộp G2 đến C4 để đẩy nó xa hơn về bên phải:
(7)
Câu hỏi là chúng ta phải đẩy hộp C4 đó đi bao xa. Vì chúng ta vẫn cần đẩy hộp G3 qua cùng một con đường nên chúng ta cần đưa thợ đến G4 và để làm điều đó, chúng ta cần đẩy hộp C4 ra xa F4 và di chuyển người thợ đến G4 để đẩy G4 đến G3:
(8)
Để chuyển hộp G2 sang trái người thợ cần phải quay lại theo hướng ngược chiều kim đồng hồ đối với hộp H2.
(9)
Phần còn lại rất đơn giản: hộp G2 được đẩy đến C2, C4, D4
(10)
sau đó hộp B2 được đẩy đến B4 và sau đó người thợ chuyển sang G4 để hoàn thành đẩy hộp F4 trên chấm E4.
HOÀN THÀNH.
Một người nào đó bị phá sản nếu người đó sở hữu tiền của người khác và không có tiền mặt và không có biên lai vì đã vay tiền của người khác hoặc có biên lai vì đã vay ai đó khác tiền nhưng người đó bị phá sản.
Giải thích về từ phá sản này sử dụng từ phá sản, và do đó nó được gọi là đệ quy.
Ví dụ:
Người A,B,C không có tiền, tất cả đều nợ người D,
A có biên lai vay tiền từ B,
B có biên lai vay tiền từ C,
C có biên lai vay tiền từ A
nhưng họ như một nhóm phá sản, mỗi người trong số họ.
Tương tự nhưng với một tình huống khác:
Người A, B, C không có tiền, tất cả đều nợ người D một số tiền,
A có biên lai vay tiền từ B,
B có biên lai vay tiền từ C,
C có biên lai vay tiền từ F,
Bởi vì người F có thể có tiền, có thể không ai trong số A,B,C bị phá sản.
Để phân biệt giữa hai trường hợp, người ta cần xem xét tất cả các mối quan hệ, không chỉ một mối quan hệ riêng lẻ bởi vì định nghĩa trên về phá sản là đệ quy.
Des Astuces pour Jouer à Sokoban
Notation
Ce guide utilisera les termes suivants :
- coup: un pas du robot, que ce soit une poussée ou un simple déplacement.
- chemin: une séquence de coups.
- position: le puzzle entier décrivant l’emplacement du robot et des boîtes.
- solution: une position où chaque boîte est sur un point rouge
- chemin de solution:la séquence de coups permettant de passer de la position initiale à la solution.
- position morte: une position à partir de laquelle la solution est inatteignable .
Stratégie générale
La solution la plus rapide peut contenir 100, 300, voire 1 000 coups (il faut déjà 73 coups pour compléter notre puzzle le plus simple, dans le 8ème puzzle il faut 126 coups). S’il y a en moyenne deux possibilités pour chaque coup et la solution nécessite 100 coups alors il faudrait chercher 2 100 chemins pour retrouver la solution si on les vérifier un par un. Alors il faut :
- reconnaître les positions mortes au plus tôt,
- diviser l'objectif global en sous-tâches. La complexité du problème est considérablement réduite quand on peut diviser un chemin de solution de 100 coups en 10 sous-tâches par exemple. En plus, il pourrait être possible de déterminer l’ordre dans lequel il faut réaliser les sous-tâches pour faciliter la résolution du problème,
- trouver des restrictions sur le chemin de la solution,
- penser à d'autres heuristiques.
1) 1) Reconnaître les positions mortes au plus tôt
1.1) Parfois il est facile à déterminer qu’une position est morte, il suffit de regarder la région entourant une seule boîte. Une inspection « locale » est suffisante. Si une boîte n’est pas sur un point rouge et ne peut se déplacer horizontalement ni verticalement, la position est morte. La boîte est peut-être bloquée par le mur ou d’autres boîtes qui ne peuvent pas être déplacées non plus.
Exemples:
1.2) Il est un peu plus difficile de voir qu'une position est morte quand la boîte se trouve sur un mur et on peut la pousser mais uniquement le long du même mur où aucune des cases qu’elle peut atteindre n’est un point.
Exemple:
1.3) Dans cette généralisation, la boîte se trouve sur un mur et on peut la déplacer dans une case où elle n’aura pas le mur de côté (la case A ci-dessous), mais le robot ne pourra pas atteindre cette case A car elle sera bloquée par la boîte.
Exemple:
On peut reconnaître ces trois cas localement sans déplacer le robot. Alors on peut les retrouver dès la position initiale pour ensuite les marquer comme « interdits » avec un symbole tel que ! pour éviter de pousser une boîte dans une telle case.
1.4) Prenant cette généralisation plus loin, le robot pourra atteindre la case A mais uniquement s’il condamne une autre boîte.
Exemple:
Cette explication est récursive.[1], c.-à-d. qu’elle définit une position morte en utilisant les mots « position morte ». Il est plus difficile de reconnaître de telles positions mortes car on ne peut pas les détecter localement et il est peut-être nécessaire d’effectuer des coups d’essai.
2) Formuler des sous-tâches
Exemples des sous-tâches:
- Déplacer le robot de A à B,
- Déplacer une boîte de A à B
Où chaque tâche doit être réalisée sans créer de position morte.
Exemple pour (a) : Comment contourner une boîte pour rejoindre la case A:
→→→→
Tout l’espace vide est nécessaire pour que le robot puisse faire le tour de la boîte. Sans cet espace vide le robot ne pourra contourner la boîte sans faire de position morte.
Si on connaît déjà le nombre de sous-tâches ainsi que le plan du labyrinthe, on peut résoudre le problème plus rapidement, dans ce cas-ci le chemin à 9 coups. Encore plus important, on sera plus motivé à compléter la sous-tâche sachant qu’elle n’est pas impossible.
Une question liée à des sous-tâches, c’est comment les identifier, ce qui peut se faire, par exemple, en essayant de résoudre le problème à rebours. Supposons qu’on ne peut atteindre un certain point rouge qu’avec une certaine boîte poussée d’une seule direction. Pour ce faire, le robot doit se mettre dans la case derrière pour pousser la boîte. Une sous-tâche peut consister à mettre la boîte et le robot dans les bonnes cases.
Ce qui suit est une autre manière typique de déterminer des sous-tâches. Il est raisonnable de supposer que tout l’espace intérieur dans une position est nécessaire pour la solution. Ceci veut dire que si la position initiale a plein de gros espaces vides, comme la zone 2×3 vide dans l’exemple ci-dessus, on doit déterminer à quoi sert cet espace. Peut-être est-il est nécessaire pour permettre au robot de contourner une boîte ou pour poser une boîte le temps de libérer de la place ailleurs. Dans ce deuxième cas on se demande ensuite quelle boîte? Et comment mettre la boîte dans cet espace?
3) Formuler des Restrictions sur le Chemin de Solution
Dès la position initiale, sans essayer de coups, on peut identifier plein de restrictions sur la solution. Voici quelques exemples :
3.1) Il existe un couloir qu’une boîte ne peut pas traverser mais dans lequel elle peut pourtant entrer, alors l’espace au bout du couloir sera bloqué.
Une boîte dans la case A ne pourra jamais atteindre B en passant par le coin, ni l’inverse.
3.2) On ne peut atteindre un certain point rouge que par un côté même s’il y a de l’espace sur d’autres côtés.
Par exemple) Le point ne peut pas être atteint par une boîte de dessous.
3.3) On ne peut pas déplacer une certain boîte dans une certaine direction et donc on ne peut la placer que sur un seul point rouge.
Ex) Cette boîte ne peut atteindre que le point rouge sur sa gauche.
3.4) Puisque certains point rouges ne sont accessibles que par certains côtés, l’ordre dans lequel les points seront occupés est déjà déterminé.
Ex. Dans la position suivante le point rouge à gauche doit être occupé avant celui à droite.
3.5) Il est évident dès le départ quel point il faudra couvrir en dernier car l’espace doit d’abord servir à déplacer d’autres boîtes.
Ex) Pour pouvoir pousser une boîte à gauche il faudra utiliser la case occupée par le point le plus à droite, donc il sera le dernier point recouvert par une boîte.4) D’autres Heuristiques
4.1) Il faut essayer toute séquence de poussées réversible, même si le robot doit effectuer beaucoup de déplacements pour défaire ces poussées. Cet exercice a l’air inutile mais la nouvelle position résultante peut révéler la façon de procéder.
4.2) S’il y a une ligne droite séparant tous les points d’au moins une boîte, alors cette boîte doit traverser cette ligne. Si ceci est impossible alors la position est morte. S’il n’existe qu’une seule façon pour faire traverser la boîte alors on identifie ainsi une forte restriction sur le chemin de solution.
Exemple d’une Solution Complète (Jeu 8)
(1)
On assigne des coordonnées pour pouvoir décrire les cases. Par exemple, le robot commence dans la case G1.
Au début le robot n’a que 2 options : a) entrer dans le trou G3, ou b) entrer dans le trou E3. Entrer dans le trou G3 ne lui permettra que de pousser la boîte dans B3 dans B1 → position morte. Alors le robot entrer dans le trou E3 et se met sur B2 :
(2)
Les seules poussées possibles sont a) la boîte B3 à B4 (pas B5, ce sera la mort) ou la boîte C2 à la droite.
On se rend compte qu’on ne pourra pas pousser les boîtes sur un chemin qui passe par G3 car il sera impossible de les pousser à gauche après. (voir 1.2)
Cependant, pour les déplacer à travers le trou B3,C3 il faut y faire de la place, donc il va falloir mettre une ou deux boîtes sur la droite pour revenir les chercher après.
On se rend compte que la boîte B3 ne peut se déplacer que sur la ligne B alors elle finira certainement sur le point B4.
Pour pouvoir mettre des boîtes sur C4 et les pousser à droite, le robot doit pouvoir se mettre sur A4, mais pour y accéder de dessous, il faut poser la boîte B3 sur B2 et les cases B3, C3, C2 doivent être vides, alors il faut dégager deux boîtes et les mettre en bas à droite.
Alors, pour libérer la place occupée par la boîte C2 et mettre le robot en haut à gauche, on pourra suivre l’exemple 2.1 et atteindre
(3)
Mais on ne peut pas pousser les boîtes A3 et B3 en bas. La seule option restante dans la position (2) est de pousser d’abord la boîte de B3 à B4 et ensuite d’effectuer les coups pour atteindre la position (3). On obtient
(4)
Maintenant on peut avancer en poussant la boîte C3 à C2 et puis en déplaçant le robot pour pousser la boîte F2 à G2 et ensuite à G3 :
(5)
Comme mentionné ci-dessus, il faut libérer les cases B3, C3, C2 pour pousser la boîte B4 à B2 donc il faut poser la boîte C2 temporairement sur G2. On obtient :
(6)
Ensuite on peut poursuivre notre programme est pousser la boîte G2 à C4 pour ensuite la pousser à droite :
(7)
Attendez : on doit pousser la boîte C4 à droite, mais de combien de cases? Il faut toujours pousser la boîte G3 le long du même chemin nécessaire pour que le robot atteigne G4. Pour ce faire il faut pousser la boîte C4 à F4, déplacer le robot à G4, et pousser la boîte G4 à G3 :
(8)
Pour pousser la boîte G2 à gauche le robot doit refaire tout le chemin dans le sens antihoraire jusqu’à H2.
(9)
Il ne reste que des coups simples : pousser la boîte G2 à C2, C4, D4.
(10)
Ensuite on pousse la boîte B2 à B4 et le robot se met sur G4 pour pousser la boîte F4 sur le point E4.
TERMINÉ.
Par exemple, on dit que quelqu’un est insolvable s’il doit de l’argent mais n’a pas d’argent liquide et il n’a pas de reçu attestant un emprunt de l’argent à un tiers, ou il a un reçu attestant un emprunt de l’argent à un tiers mais cette tierce personne est insolvable elle aussi.
Cette explication du mot insolvable utilise le mot insolvable alors elle est récursive.
Exemple:
Les personnes A,B,C n’ont pas d’argent, et chacune d’entre elles doit de l’argent à D.
A a un reçu pour avoir fait un emprunt à B,
B a un reçu pour avoir fait un emprunt à C,
C a un reçu pour avoir fait un emprunt à A
Mais l’ensemble est insolvable, chacune d’entre elles.
Une situation similaire mais différente :
Les personnes A,B,C n’ont pas d’argent, et chacune d’entre elles doit de l’argent à D.
A a un reçu pour avoir fait un emprunt à B,,
B a un reçu pour avoir fait un emprunt à C,
C a un reçu pour avoir fait un emprunt à F
Si la personne F a de l’argent, alors ni A ni B ni C ne seront insolvables.
Pour faire la différence entre ces deux cas il faut bien regarder toutes les relations et non une seule, car la susdite définition d’insolvable est récursive.
关于推箱子游戏的建议
符号
本指南将使用以下术语：
- 步数： 工人的步数，推或不推箱子都计入。
- 路径： 一系列动作。
- 位置： 工人和所有箱子在某地特定地方的情况。
- 解决方案： 所有箱子都在红点上的位置。
- 解决方案路径： 从初始位置到解决方案的一系列动作。
- 死局： 无法达到解决方案的路径。
总体战略
最短的解决方案可能包含100,300甚至1000个步数。 （我们最简单的游戏1需要73个动作，游戏8需要126个动作）。 如果平均每个移动有两种可能性，并且解决方案需要100次移动，那么盲目搜索将需要搜索2100个路径以找到解决方案。 即使对于计算机，这也是不可能的。 因此，我们需要：
- 尽早明确一个位置是不是死局，
- 将总体目标分解为子任务。 如果100个步骤的解决方案路径可以分解为，例如，10个子任务，那么问题的复杂性将大大降低。 此外，有可能推断出完成子任务的顺序，然后整个问题变得容易解决，
- 找到解决方案路径上的限制，
- 想想其他探索方法。
关于1：今早找出死局
1.1：有时判断一个位置是否是死局很容易，只需要查看一个单独的箱子附近的情况。 要做的只是“本地”检查。 如果一个箱子不在一个点上并且不能水平移动，也不能垂直移动，那么该位置就是死局。 箱子可能被墙壁或其他也不能移动的箱子挡住。
例如：
1.2：如果箱子靠近墙壁并且它可以被推动但是只能沿着同一侧的墙壁被推动而且它可以到达的任何地方都不是一个点，那么这个位置也是死局，虽然稍微难看出来一点。
例如：
在这种概括的情况中，箱子靠近墙壁并且可以移动到其侧面没有墙壁的地方（下面的位置A），但是将箱子推到A附近后，小工人无法到达A。
例如：
这三种情况可以只看箱子就决定，而不需要移动工人。 因此，可以在初始位置检查是否有此类情况，并可以标记出这些禁止的地方，比如说用！标记。 这样箱子就永远不会被推到这里。
1.4：在进一步概括的情况中，小工人想要到达地点A就不得不把另一个箱子推到一个禁止的地方。
例如：
这种解释是循环的[1], 也就是说，它用死局来描述死局。 这种死局更难以识别，因为它们无法通过“本地”检查发现，并且可能需要一些走步骤来测试。
关于2：制定子任务
子任务的例子如下：
- 把小工人从A移到B，
- 把某个箱子从A移到B
完成这些任务都不应该制造出死局。
（a）的例子：工人怎么样才能绕过箱子到达A？
→→→→
必须要有空间工人才能在箱子周围走动。 如果空的空间较少，那么工人无法在不产生死局的情况下绕过箱子。
如果玩家把大量子任务的路线烂熟于心，那么就可以节省很多时间，在本例中是一个9个步骤。更重要的是，玩家这道这个子任务是可能的，所以不会放弃。
与子任务相关的一个问题是如何找到它们。 例如，当反向解决问题时，就会出现子任务。 假设只能从一侧由一个箱子到达某个点，那么就需要将该箱子推向特定方向。 为了做到这一点，工人需要到达它的另一边。任务就可能是将箱子和工人放在正确的位置。
提出子任务的另一个典型示例如下。 安全地假设解决方案需要一个位置的所有内部空间。 这意味着，如果初始 位置具有庞大的内部空间，如上例中的2*3的空区域，这些空间用来干什么。可能是工人需要这个空间来绕过一个箱子，或者用于临时放一个箱子以便在其他地方释放空间。 因此，如果多余的空间能够临时存放一个箱子，那哪个箱子需要临时存放呢？怎么把这个箱子推到这个中间停放点？
关于3：制定解决方案路径的限制
只需通过查看位置而不尝试移动就可以对解决方案路径进行许多限制。 例如：
3.1：有一个箱子可以进入但不可能贯穿的走廊，因此走廊末端的空间永远不能从走廊结束的一侧到达。
例如，B上的一个盒子永远无法到达A点，并且A上的盒子无法通过拐角到达B。
3.2：即使在不同侧面有空间，某个点也只能从一侧到达。
例如，箱子无法从下面到达的点
3.3：某个盒子永远不能在某个方向上移动，因此只能到达一个特定的点。
例如，该箱子只能到达其左侧的点。
3.4：因为某些点只能从特定的方向到达，所以它决定了到达不同的点的顺序。
例如，在以下位置，左边的点必须在它右边的点之前到达。
3.5：最后到达哪一点可能很清楚，因为工人需要空间来向某个方向推动一个盒子。
例如，工人需要站在最右边的点的空间，并将一个盒子推到左边，所以最右边的点是最后一个到达的点（与上图相同）。关于4：其他探索
4.1：可以并且应该尝试任何可以反转的推动顺序，即使这意味着工人必须走很长的路才能从另一侧推箱子以反转这些推动。即使这样的练习看起来毫无意义，但新位置也可能为如何开展提供新的可能性。
4.2：如果有一条直线将所有点与至少一个箱子分开，则该箱子必须越过该线。如果这是不可能的，那么该位置就是死局。如果盒子只有一种方式穿过该线，则这就是对解决方案路径的巨大限制。
完整解决方案示例，游戏8
(1)
中文：为了标记点，我们引入了坐标。 例如，工人最初在G1点。/p>
最初，工人只有两个选项：A，穿过洞G3，或B，穿过洞E3。穿过G3只能让工人将B3的盒子推到B1，导致死局。所以工人穿过E3到达B2
(2)
我们可以做的唯一移动是A，将箱子从B3推到B4（不是B5，B5是死局），或者是从C2推到右边。
我们意识到盒子不能移动到通过G3的路线上的点，因为在这个它们之后就不能移动到左边了，如1.2中所示。
但是为了让它们通过洞B3，C3，我们需要在这个区域内有空间，所以我们需要在右边停放一个或两个箱子，之后又必须把它们移回来。
我们还意识到盒子B3只能在B线上移动，因此最终必须在B4点结束。
要在C4上移动后面的箱子然后将它们推到右边，工人必须能够移动到A4但是从下面到B4，箱子B3必须在B2处且空间B3，C3，C2必须是空的，所以两个盒子必须移开并停在右下方。
所以，为了让箱子C2不挡路并让工人到达左上方，我们可以使用示例2.1
(3)
但是把箱子A3或B3推下去并不起作用。 我们在位置2唯一的另一个选择是首先将箱子B3推到B4，然后进行到位置3的移动。我们得到了
(4)
现在我们可以通过将箱子C3向下推到C2并与工人一起移动以将方框F2推到G2和G3：
(5)
如上所述，我们需要空间B3，C3，C2空出来，并将箱子B4下移到B2，所以我们需要暂时将箱子C2放在G2。我们得到：
(6)
简体中文：现在我们可以按照我们之前的计划将箱子G2推到C4，以便将其推向右边：
(7)
问题是我们要将盒子C4推到多右边。因为我们仍然需要通过相同的路径推箱子G3，所以我们需要让工人到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可能都不会破产。
区分这两种情况，需要关注所有关系，而不仅仅是单独的一个关系，因为上述破产定义是循环的。
توصیه هایی در راستای چگونگی بازی سوکوبان
نوشتار
عبارات زیر در حین این راهنمایی استفاده می شوند:
- حرکت: یک قدم کارگر چه جعبه ای را حرکت بدهد چه ندهد.
- مسیر: دنباله ای از حرکات.
- موقعیت: کل این مساله با در نظر گرقتن کارگر و همه ی جعبه ها در یک موقعیت خاص.
- پاسخ: موقعیتی که در آن هر جعبه ای روی یک نقطه قرار دارد.
- مسیر پاسخ: دنباله ای از حرکات از موقعیت اصلی به پاسخ.
- موقعیت مرده: موقعیتی که از آن پاسخ نمی تواند به دست آید.
استراتژی کلی
کوتاهترین پاسخ ممکن است شامل ۱۰۰، ۳۰۰ یا حتی ۱۰۰۰ حرکت. ساده ترین بازی ۱ ما ۷۳ حرکت لازم دارد، بازی ۸، ۱۲۶ حرکت لازم دارد. اگر به طور متوسط، فرض کنید، ۲ احتمال برای هر حرکت و پاسخ ۱۰۰ حرکت می خواهد، آنگاه یک جستجوی جامع ممکن است نیازمند جستجوی ۲۱۰۰ مسیر برای پیدا کردن پاسخ باشد. حتی برای رایانه ها این ممکن نیست. در نتیجه ما لازم است که:
- زود تشخیص دهیم اگر موقعیتی مرده است،
- هدف نهایی را به چند کار زیرمجموعه ای تقسیم کنید. اگر یک مسیر پاسخ ۱۰۰ حرکتی بتواند به مثلا، ۱۰ زیر شاخه تقسیم شود، آنگاه پیچیدگی مساله به شدت کاهش پیدا می کند. . به علاوه، ممکن است که بتوان ترتیبی که در آن زیرشاخه باید انحام شود را کاهش داد و آنگاه کل مساله برای حل شدن ساده می شود،
- اولین محدودیت برای مسیر پاسخ،
- به ابتکارهای دیگر فکر کنید.
درباره ی ۱: تشخیص زودهنگام موقعیت های مرده
۱. ۱: گاهی آسان است که تصمیم بگیریم آیا موقعیتی مرده است، فقط کافی است به همسایگی یک جعبه ی تنها نگاه کرد. تنها چیزی که لازم است یک بازرسی موضعی است. اگر جعبه ای روی یک نقطه قرار نگرفته است و نمی تواند به صورت افقی و عمودی حرکت کند، آنگاه آن موقعیت مرده است. جعبه ممکن است با دیوار و یا جعبه های دیگر بلوکه شده باشد که باز هم نمی تواند حرکت کند.
مثال ها:
۱.۲: این اندکی سخت تر است که ببینیم که موقعیتی مرده است اگر که جعبه در کنار دیوار قرار دارد و می تواند هل داده شود اما فقط در راستای دیوار و در جهت یکسان، و هیچ یک از موقعیت هایی که این جعبه می تواند به آن برسد نقطه نمی باشد.
مثال ها:
۱.۳: در این تعمیم جعبه در کنار دیوار قرار دارد و می تواند به موقعیتی که دیوار در کنارش قرار نداشته باشد، حرکت داده شود, نقشه ی 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 ورشکست نباشند.
برای تشخیص دادن این دو مورد لازم است که به همه ی روابط نگاه کرد، نه فقط به یک مورد، چرا که تعریف بالا از ورشکست بازگشتی است.
Поради щодо того, як грати в Сокобан
Зауваження
У цьому посібнику використовуватимуться такі терміни:
- Переміщення: один крок працівника, байдуже він штовхає чи не штовхає ящик.
- Шлях: послідовність ходів
- Позиція: вся задача з працівником і всіма коробками в певному місці.
- Рішення: положення, де кожна коробка стоїть на крапці.
- Шлях рішення: послідовність переміщень від вихідного положення до рішення.
- мертва позиція: позиція, з якої неможливо досягти рішення.
Загальна стратегія
Найкоротше рішення може містити 100, 300 або навіть 1000 ходів. (Нашій найпростішій грі 1 вже потрібно 73 ходи, 8 грі – 126 ходів). Якщо є в середньому, скажімо, 2 можливості для кожного ходу, і рішення займає 100 ходів, то для пошуку методом перебору знадобиться шукати 2^100 шляхів, щоб знайти рішення. Навіть для комп’ютерів це неможливо. Тому нам необхідно:
- рано розпізнавати, якщо позиція мертва,
- Розбийте загальну мету на підзавдання. Якщо шлях вирішення 100 ходів можна розбити, скажімо, на 10 підзадач, тоді складність задачі різко зменшиться. Крім того, можна було б визначити порядок, в якому потрібно виконати підзадачі, і тоді вся проблема стане простішою для вирішення,
- Знайдіть обмеження на шляху вирішення,
- Подумайте про інші евристики.
Про 1: Раннє розпізнавання мертвих позицій
1.1: Іноді легко вирішити, чи позиція мертва, потрібно лише подивитися в околі однієї коробки. Все, що потрібно, це «локальна» перевірка. Якщо коробка не стоїть на точці і її не можна переміщати по горизонталі, і по вертикалі, значить, позиція мертва. Ящик може бути заблокований стіною або іншими ящиками, які також не можна пересунути.
Examples:
1.2: Трохи важче побачити, що позиція мертва, якщо коробка стоїть біля стіни і її можна штовхнути, але тільки вздовж стіни з тієї ж сторони, і жодне з місць, до яких вона може досягти, не є крапкою.
Example:
1.3: У цьому узагальненні коробка знаходиться поруч зі стіною і може бути переміщена в місце, де немає стіни що заважає (місце A нижче), але це вільне сусіднє місце A не може бути досягнуто працівником після пересування коробки в А.
Example:
Ці три випадки можуть бути вирішені на місці і без переміщення працівника. Таким чином їх можна перевірити в початковій позиції і позначити місця як заборонені, скажімо, за допомогою ! щоб коробку ніколи не штовхали на таке місце.
1.4: У подальшому узагальненні працівник може досягти місця А, але лише за ціну постановки іншої коробки в забороненому місці.
Example:
Це пояснення є рекурсивним[1], тобто характеризує мертву позицію за допомогою слів мертва позиція. Такі мертві позиції важче розпізнати, оскільки вони не можуть бути виявлені місцевою інспекцією і, можливо, знадобляться тестові переміщення.
Про 2: Формулювання підзадач
Приклади підзадач:
- перемістіть працівника з точки А в точку Б,
- Перемістіть певну коробку з А в Б
Де кожне з цих завдань має бути виконане без створення мертвої позиції.
Приклад для (a): Як працівник може обминути коробку, щоб дістатися до A:
→→→→
Потрібне все порожнє місце, оскільки працівник повинен обходити коробку. Якщо порожнього місця не достатньо, то працівник не може пройти коробку без створення мертвої позиції.
Якщо вивчити багато таких підзадач з їхніми формами коридору, то можна заощадити багато часу, не думаючи про це, ось цей шлях із 9 рухів. Що ще важливіше, людина не здасться через те, що вважає це підзавдання неможливим.
Питання, пов’язане з підзадачами, полягає в тому, як їх знайти. Підзадачі виникають, наприклад, при розв’язуванні задачі в зворотному порядку. Припустимо, що до певної точки можна дістатися лише з одного боку і лише за допомогою однієї коробки. Отже, цю коробку потрібно штовхати в певному напрямку. Для цього робітнику необхідно перейти на інший бік. Завдання може полягати в тому, щоб привести коробку і робітника в потрібне положення.
Іншим типовим прикладом створення підзавдання є наступний. Можна з упевненістю припустити, що для рішення необхідний весь внутрішній простір у певному положенні. Це означає, що якщо вихідна позиція має об’ємні внутрішні простори, як-от порожня область 2 на 3 у наведеному вище прикладі, тоді можна задуматись, яка мета цього простору. Можливо, він потрібен працівникові для пересування коробки або він використовується для тимчасового зберігання коробки, щоб тимчасово звільнити простір в іншому місці. Отже, якщо громіздкий простір здатний тимчасово зберігати коробку, то яка коробка це може бути? Як можна доставити цю коробку до цього проміжного паркувального місця?
Про 3: Формулювання обмежень на шлях вирішення
Існує багато обмежень на шляху вирішення, можливих просто подивившись на позицію, не випробовуючи ходи. Приклади:
3.1: Є коридор, в який можна потрапити за допомогою коробки, але коробка ніколи не може переміщатися по всьому коридору, і тому до місця в кінці коридору ніколи не можна дістатися з боку, де закінчується коридор.
наприклад, до точки A ніколи не можна дістатися ящиком, що стоїть на B, а B не можна досягти ящиком, що стоїть на A, проходячи через коридор.
3.2: До певної точки можна дістатися лише з одного боку, навіть якщо з різних сторін є вільний простір.
наприклад, крапка не може бути досягнута коробкою знизу.
3.3: Певна коробка ніколи не може бути переміщена у певному напрямку, і тому вона може досягати лише однієї певної точки.
наприклад, коробка може досягати лише точки зліва.
3.4: Оскільки до точок можна потрапити за допомогою квадратів лише з певної сторони, це визначає порядок, у якому точки мають бути зайняті.
наприклад, у наступному положенні ліва точка має бути зайнята перед точкою праворуч від неї.
3.5: Може бути зрозумілим, яку точку потрібно досягнути останньою, тому що працівнику потрібен простір, щоб штовхнути коробку в певному напрямку.
наприклад, простір крайньої правої точки необхідний для того, щоб працівник стояв і штовхав коробку ліворуч, тому сама права точка займає останню (на тому ж малюнку, що й вище).Про 4: Інші евристики
4.1: Будь-яку послідовність поштовхів, яку можна змінити, можна і потрібно спробувати, навіть якщо це означає, що працівник повинен пройти довгий шлях, щоб штовхнути з іншого боку, щоб змінити ці поштовхи. Навіть якщо така вправа здається безглуздою, нова позиція може відкрити нові можливості як діяти далі.
4.2: Якщо є пряма лінія, яка відокремлює всі точки принаймні від однієї коробки, то ця коробка повинна перетнути цю лінію. Якщо це неможливо, позиція мертва. Якщо існує лише один спосіб перетину прямокутника цієї лінії, то це є сильним обмеженням для шляху вирішення.
Приклад повного рішення, гра 8
(1)
Ми вводимо координати до точок мітки. Наприклад, робітник спочатку знаходиться в точці G1.
Спочатку робітник має лише 2 варіанти: A, пройти крізь отвір G3, або B, пройти крізь отвір E3. Перехід через G3 дозволяє працівнику лише перемістити коробку від B3 до B1, що призводить до мертвої позиції. Отже, робітник проходить через отвір E3 до B2:
(2)
Єдине, що ми можемо зробити, це A, коробку B3 до B4 (а не B5, що означає мертву позицію), або коробку C2 праворуч.
Ми усвідомлюємо, що коробки не можна переміщати в точки на маршруті через G3, тому що вони ніколи не можуть бути переміщені ліворуч, як показано в 1.2.
Але для того, щоб перемістити їх через отвір B3,C3, нам потрібен простір у цій області, тому нам потрібно припаркувати однe або дві коробки праворуч, а потім повернути їх.
Ми також усвідомлюємо, що блок B3 можна переміщати лише на лінії B, і тому, він повинен закінчитися на точці B4.
Щоб перемістити пізніші ящики на C4, а потім штовхнути їх праворуч, працівник повинен мати можливість перейти до A4, але щоб потрапити туди знизу, коробка B3 має бути на B2, а місця B3, C3, C2 мають бути вільними, тож дві коробки мають відійти з дороги та припаркуватися в нижньому правому куті.
Отже, щоб усунути блок C2 і перевести працівника вгору зліва, ми можемо використати приклад 2.1
(3)
але перемістити коробку A3 або B3 не виходить. Єдиний інший варіант, який у нас був у позиції 2, - це спочатку підсунути коробку B3 до B4, а потім зробити ходи, що ведуть до позиції 3. Ми отримуємо
(4)
Тепер ми можемо досягти прогресу, перемістивши коробку C3 вниз до C2 і перемістити коробку F2 до G2 і G3:
(5)
Як обговорювалося вище, нам потрібні вільні місця B3,C3,C2 і містити коробку B4 до B2, тому нам потрібно тимчасово припаркувати коробку C2 на G2. Ми отримуємо:
(6)
Тепер ми можемо слідувати нашому попередньому плану та перемістити коробку G2 на C4, щоб перемістити її далі вправо:
(7)
Питання полягає в тому, наскільки вправо ми маємо відсунути коробку C4. Оскільки нам все ще потрібно проштовхнути блок G3 по тому самому шляху, нам потрібно перевести працівника в G4, а для цього нам потрібно перемістити коробку C4 до F4 і перемістити працівника в G4, щоб перемістити G4 до G3:
(8)
Щоб перемістити коробку G2 ліворуч, робітнику необхідно повернутись назад проти годинникової стрілки до H2.
(9)
Все інше просто: коробка G2 переміщується до C2, C4, D4
(10)
потім коробка B2 переміщується до B4, а потім працівник переходить до G4, щоб нарешті перемістити коробку F4 на точку E4.
ГОТОВО.
Особа вважається банкрутом, якщо вона володіє грошима іншого, але не має готівкових грошей і або не має квитанції про те, що позичила комусь гроші, або має квитанцію про те, що вона позичила чужі гроші, але ця особа є банкрутом.
У цьому поясненні слова банкрут використовується слово банкрут, тому воно називається рекурсивним.
Приклад:
Особи A,B,C не мають грошей, усі вони винні гроші людині D,
А має квитанцію про позику грошей у В,
B має квитанцію про позику грошей C,
C має квитанцію про позику грошей А
але вони як група банкроти, кожен з них.
Схожа, але інша ситуація:
Особи A,B,C не мають грошей, усі вони винні гроші людині D,
А має квитанцію про позику грошей у В,
B має квитанцію про позику грошей C,
C має квитанцію про позику грошей F.
Оскільки особа F може мати гроші, можливо, жоден з A,B,C не є банкрутом.
Щоб розрізнити ці два випадки, потрібно розглянути всі зв’язки, а не лише один окремо, оскільки наведене вище визначення банкрутства є рекурсивним.
ការណែនាំអំពីរបៀបលេងល្បែង សូគូបាន
កំណត់ចំណាំ
លក្ខណ្ឌខាងក្រោមនឹងត្រូវបានប្រើក្នុងការណែនាំនេះ។
- ផ្លាស់ទីមួយជំហ៊ាននៃតួអង្គក្នុងល្បែងទោះបីជារុញឬទាញប្រអប់។
- គន្លង៖ ការផ្លាស់ប្ដូរជាបន្តបន្ទាប់
- ទីតាំង៖ បញ្ហាទាំងស្រុងជាមួយអ្នកលេងល្បែងនិង ប្រអប់ទាំងអស់ដែលស្ថិតនៅកន្លែងជាក់លាក់មួយ។
- ដំណោះស្រាយ៖ ទីតាំងដែលប្រអប់នីមួយៗស្ថិតនៅលើចំណុចមួយ។
- គន្លងដំណោះស្រាយ៖ លំដាប់នៃការផ្លាស់ប្តូរពីទីតាំងដើម ទៅកាន់ដំណោះស្រាយ។
- ទីតាំងស្លាប់៖ ជាទីតាំងដែលមិនអាចរកដំណោះស្រាយបាន។
យុទ្ធសាស្ត្រទូទៅ
ដំណោះស្រាយដ៏ខ្លីបំផុតអាចមាន ១០០, ៣០០ ឬសូម្បីតែផ្លាស់ទី១០០០ផ្លាស់ទី។(ល្បែងសាមញ្ញបំផុតទី១របស់យើងគឺត្រូវការផ្លាស់ទី៧៣ រួចហើយល្បែងទី៨ ត្រូវការផ្លាស់ទី១២៦)។ ប្រសិនបើមានតម្លៃមធ្យម នោះលទ្ធភាពមានពីរសម្រាប់ការផ្លាស់ទីនីមួយៗ ហើយដំណោះស្រាយត្រូវចំណាយពេល ១០០ផ្លាស់ទី បន្ទាប់មកស្វែងរកដំណោះស្រាយគន្លង ២^១០០ ដើម្បីរកដំណោះស្រាយ។ សូម្បីតែកុំព្យូទ័រក៏មិនអាចទៅរួចដែរ។ ដូច្នេះយើងចាំបាច់ត្រូវ៖
- ត្រូវដឹងជាមុន ប្រសិនបើទីតាំងស្លាប់
- បំបែកគោលដៅរួមទៅជាកិច្ចការរង។ ប្រសិនបើដំណោះស្រាយដោយផ្នែក ១០០ផ្លាស់ទី អាចត្រូវបានបំបែក ទៅជា១០ កិច្ចការរង នោះភាពស្មុគស្មាញនៃបញ្ហាត្រូវបានកាត់បន្ថយយ៉ាងខ្លាំង។ លើសពីនេះទៅទៀត វាអាចនឹងកាត់បន្ថយនូវលំដាប់ដែលកិច្ចការរងត្រូវបានបញ្ចប់ ហើយបន្ទាប់មកបញ្ហាទាំងមូល នឹងងាយស្រួលក្នុងការដោះស្រាយ។
- ស្វែងរកលក្ខខណ្ឌ ក្នុងគន្លងដោះស្រាយ
- ពិចារណាអំពីវិធីដោះស្រាយផ្សេងទៀត។
ករណីទី ១៖ ការទទួលស្គាល់ពីទីតាំងស្លាប់ជាមុន
១.១៖ ពេលខ្លះវាងាយស្រួលក្នុងការសម្រេចថាតើ ទីតាំងណាស្លាប់ឬអត់ មានតែសង្កេតមើលទៅលើអ្វីដែលនៅជុំវិញប្រអប់តែ១ប៉ុណ្ណោះ។ អ្វីទាំងអស់ដែលវាត្រូវការត្រួតពិនិត្យមើលគឺ “ទីតាំង”។ ប្រសិនបើប្រអប់មួយមិនស្ថិតលើចំណុចមួយ ហើយមិនអាចផ្លាស់ទីតាមជួរដេក និងមិនអាចផ្លាស់ទីតាមជួរឈរទេ នោះជាទីតាំងស្លាប់ហើយ។ ប្រអប់ត្រូវបានបិទដោយ ជញ្ជាំង ឬដោយប្រអប់ផ្សេងទៀតដែលមិនអាចផ្លាស់ទីបាន។
Examples:
១.២៖ វាពិបាកបន្តិចក្នុងការមើលថាទីតាំងមួយនិងស្លាប់ ប្រសិនបើប្រអប់នៅជាប់នឹងជញ្ជាំង ហើយវាអាចរុញបាន ប៉ុន្តែមានតែនៅតាមបណ្តោយជញ្ជាំងនោះតែប៉ុណ្ណោះ ហើយគ្មានកន្លែងណាដែលវាអាចទៅដល់ជាចំណុចនោះទេ។
Example:
ជាទូទៅប្រអប់នៅជាប់នឹងជញ្ជាំង ហើយអាចផ្លាស់ទីទៅកន្លែងដែល វាមិនមានជញ្ជាំងនៅចំហៀងបស់វា (កន្លែងAខាងក្រោម) ប៉ុន្តែកន្លែងជិតខាងAដែលទំនេរ មិនអាចផ្លាស់ទីដោយអ្នកលេងល្បេងរុញប្រអប់បន្ទាប់នៅជាប់ A។
Example:
ករណីទាំងបីនេះសម្រេចបាននៅមូលដ្ឋាន និងមិនចាំបាច់ផ្លាស់ទីអ្នកលេងល្បែង។ ដូច្នេះគេអាចពិនិត្យមើលទីតាំងដំបូង ហើយគេសម្គាល់កន្លែងដែលត្រូវបានហាមមិនឲ្យនិយាយជាមួយ ដូច្នេះប្រអប់មួយអាចនឹងមិនត្រូវបានរុញទៅកាន់កន្លែងបែបនេះឡើយ។
ជាទូទៅ កន្លែង A អាចទៅដល់ដោយអ្នកលេងល្បែង ប៉ុន្តែត្រឹមតែតម្លៃនៃការដាក់ប្រអប់មួយទៀត នៅកន្លែងហាមឃាត់។
Example:
ការពន្យល់នេះកើតឡើងដដែលៗ[1]វាមានលក្ខណៈជាទីតាំងស្លាប់ដោយប្រើពាក្យ ស្លាប់។ ទីតាំងស្លាប់បែបនេះគឺពិបាកក្នុងការទទួលស្គាល់ ព្រោះវាមិនអាចនឹងត្រូវបានរកឃើញ ដោយការត្រួតពិនិត្យទីតាំង ហើយប្រហែលជាត្រូវ ការការផ្លាស់ទីសាកល្បង។
ករណីទី ២ ៖ ការបង្កើតកិច្ចការរង
ឧទាហរណ៍កិច្ចការរងនោះគឺ
- ផ្លាស់ទីអ្នកលេងល្បែងពី A ទៅ B
- ផ្លាស់ទីប្រអប់ជាក់លាក់មួយពី A ទៅ B
កន្លែងដែលកិច្ចការនីមួយៗត្រូវបានសម្រេចដោយមិនបង្កើតទីតាំងស្លាប់។
ឧទាហរណ៍សម្រាប់ (a) ៖ តើអ្នកលេងល្បែងអាចហុចប្រអប់មួយយ៉ាងដូចម្តេច ដើម្បីទៅដល់ A ៖
→→→→
លំហរទទេរទាំងអស់គឺ ត្រូវការជាចាំបាច់ព្រោះអ្នកលេងល្បែងត្រូវរុញជុំវិញប្រអប់។ ប្រសិនបើមានលំហទទេរតិចនោះអ្នកលេងល្បែងមិនអាចឆ្លងកាត់ប្រអប់ដោយមិនបង្កើតទីតាំងស្លាប់បានទេ។
ប្រសិនបើមានមនុស្សស្គាល់កិច្ចការរងបែបនេះជាមួយរូបរាងនៃច្រករហៀង ដោយរត់មាត់ នោះគេអាចសន្សំពេលវេលាបានច្រើន ដោយមិនចាំបាច់គិតពីវាទេ នេះជាគន្លងផ្លាស់ទី ទី៩ ។ សំខាន់ជាងនេះទៅទៀតគេមិនចុះចាញ់ទេ ព្រោះគេគិតថាកិច្ចការរងនេះគឺមិនអាចទៅរួច។
សំណួរទាក់ទងនឹងកិច្ចការរងគឺជាវិធីក្នុងការរកកិច្ចការរងទាំងនោះ។ ឧទាហរណ៍ កិច្ចការរងកើតឡើងនៅពេលដោះស្រាយបញ្ហាបញ្ច្រាស។ ឧបមាថាចំណុចជាក់លាក់មួយអាចទៅដល់បានតែម្ខាង ហើយបានតែប្រអប់មួយប៉ុណ្ណោះ។ ជាលទ្ធផលប្រអប់នេះត្រូវការរុញក្នុងទិសដៅជាក់លាក់មួយ។ ដើម្បីធ្វើដូច្នេះអ្នកលេងល្បែងត្រូវទៅម្ខាងទៀត។ កិច្ចការនោះអាចជាការនាំយកប្រអប់ និងអ្នកលេងល្បែងនៅក្នុងទីតាំងត្រឹមត្រូវ។
ឧទាហរណ៍ធម្មតាមួយទៀតនៃការបង្កើតកិច្ចការរងគឺដូចខាងក្រោម។ វាជារឿងធម្មតាក្នុងការសន្មត់ថាចន្លោះខាងក្នុងទាំងអស់នៅក្នុងទីតាំងមួយគឺត្រូវការនូវដំណោះស្រាយ។ នោះមានន័យថា ប្រសិនបើទីតាំងដើមមានចន្លោះខាងក្នុងធំ ដូចជាផ្ទៃទទេ 2 គុណ 3 ក្នុងឧទាហរណ៍ខាងលើ នោះគេអាចសួរថាតើគោលបំណងអ្វីសម្រាប់លំហនោះ។ អាចថា អ្នកលេងល្បែងត្រូវការវាដើម្បីហុចប្រអប់មួយ ឬវាត្រូវបានប្រើសម្រាប់រក្សាទុកប្រអប់បណ្ដោះអាសន្ន ដើម្បីទុកកន្លែងទំនេរនៅកន្លែងផ្សេងជាមធ្យម។ ដូច្នេះប្រសិនបើទំហំទំនេរធំនោះអាចរក្សាទុកប្រអប់មួយជាបណ្ដោះអាសន្ន តើប្រអប់នោះអាចជាប្រអប់មួយណា? តើគេអាចយកប្រអប់នេះទៅកន្លែងផ្ទុកកម្រិតមធ្យមដោយរបៀបណា?
អំពី 3: ការបង្កើតលក្ខខណ្ឌលើគន្លងវិធីដោះស្រាយ
មានលក្ខខណ្ឌជាច្រើននៅលើគន្លងវិធីដោះស្រាយដែលអាចធ្វើទៅបានដោយគ្រាន់តែមើលទីតាំងដោយមិនព្យាយាមផ្លាស់ទី។ ឧទាហរណ៍គឺ៖
3.1៖ មានច្រកតូចមួយដែលអាចចូលបានដោយប្រអប់ ប៉ុន្តែប្រអប់មិនអាចឆ្លងកាត់ច្រកនោះទាំងមូលបានទេ ដូច្នេះហើយចន្លោះនៅចុងបញ្ចប់នៃច្រកនោះមិនអាចទៅដល់ទីតាំងដែលច្រកមួយនោះបញ្ចប់ទេ។
ឧទាហរណ៍ ចំណុច A មិនអាចទៅដល់បានដោយប្រអប់ដែលកំណត់លើ B ហើយ B មិនអាចទៅដល់ដោយប្រអប់ដែលកំណត់លើ A ដោយឆ្លងកាត់ជ្រុង។
3.2៖ ចំណុចជាក់លាក់មួយអាចទៅដល់បានតែម្ខាងប៉ុណ្ណោះ ទោះបីជាមានលំហរទំនេរនៅសងខាងក៏ដោយ។
ឧទាហរណ៍ ចំណុចមិនអាចទៅដល់បានដោយប្រអប់ខាងក្រោម។
3.3៖ ប្រអប់ជាក់លាក់មួយមិនអាចផ្លាស់ទីក្នុងទិសដៅជាក់លាក់មួយបានទេ ដូច្នេះហើយអាចទៅដល់ចំណុចជាក់លាក់មួយប៉ុណ្ណោះ។
ឧទាហរណ៍ ប្រអប់អាចទៅដល់ចំណុចនៅលើផ្នែកខាងឆ្វេងរបស់វាប៉ុណ្ណោះ។
3.4៖ ដោយសារតែប្រអប់ អាចទៅដល់ចំណុចបានតែផ្នែកខ្លះប៉ុណ្ណោះ ដែលវាអាចកំណត់នូវលំដាប់ដែលចំណុចត្រូវស្ថិតនៅ។
ឧទាហរណ៍ នៅទីតាំងខាងក្រោម ចំណុចខាងឆ្វេងត្រូវតែស្ថិតនៅមុនចំណុចនៅខាងស្តាំរបស់វា។
3.5៖ វាអាចបញ្ជាក់ច្បាស់អំពីចំណុចណាដែលត្រូវស្ថិតនៅចុងក្រោយ ព្រោះអ្នកលេងល្បែងត្រូវការកន្លែងដើម្បីរុញប្រអប់ក្នុងទិសដៅជាក់លាក់មួយ។
ឧទាហរណ៍ ចន្លោះនៃចំណុចខាងស្តាំបំផុតគឺត្រូវការសម្រាប់អ្នកលេងល្បែងដើម្បីឈរ ហើយរុញប្រអប់មួយទៅខាងឆ្វេង ដូច្នេះចំណុចខាងស្តាំបំផុតគឺជាចំណុចចុងក្រោយដែលត្រូវស្ថិតនៅ (ក្នុងរូបភាពដូចខាងលើ)។អំពី 4៖ វិធីដោះស្រាយផ្សេងៗទៀត។
៤.១៖ រាល់ការរុញច្រានដែលអាចបញ្ច្រាស់បាន អាចនិងគួរត្រូវបានសាកល្បង ទោះបីជាវាមានន័យថា អ្នកលេងល្បែងត្រូវទៅផ្លូវឆ្ងាយ ដើម្បីរុញពីម្ខាងទៀតដើម្បីបញ្ច្រាសការរុញទាំងនេះ។ ទោះបីជាលំហាត់បែបនេះមើលទៅគ្មានន័យក៏ដោយ ក៏ទីតាំងថ្មីអាចបើកឱកាសឱ្យរកឃើញនូវលទ្ធភាពដោះស្រាយថ្មីៗក្នុងដំណើរការនេះ។
៤.២៖ ប្រសិនបើមានបន្ទាត់ត្រង់មួយដែលបែងចែកចំណុចទាំងអស់ចេញពីប្រអប់យ៉ាងតិចមួយ នោះប្រអប់នេះត្រូវតែឆ្លងកាត់បន្ទាត់នោះ។ បើមិនអាចធ្វើទៅបាន នឹងមិនមានទីតាំងណាកើតឡើងទេ។ ប្រសិនបើមានផ្លូវតែមួយសម្រាប់ប្រអប់ដើម្បីឆ្លងកាត់បន្ទាត់នោះ មានន័យថាគន្លងដំណោះស្រាយមានលក្ខខណ្ឌកំណត់តឹងរឹងមួយ។
ឧទាហរណ៍នៃដំណោះស្រាយពេញលេញ ល្បែងទី 8
(1)
យើងណែនាំកូអរដោនេរដល់ចំណុចស្លាក។ ជាឧទាហរណ៍ អ្នកលេងល្បែងដំបូងស្ថិតនៅចំណុច G1។
ដំបូងឡើយ អ្នកលេងល្បែងមានជម្រើសតែ 2 ប៉ុណ្ណោះគឺ A ចូលតាមរន្ធ G3 ឬ B ដើម្បីចូលតាមរន្ធ E3។ ឆ្លងកាត់ G3 គ្រាន់តែអនុញ្ញាតឱ្យអ្នកលេងល្បែងរុញប្រអប់ B3 ទៅ B1 លទ្ធផលបណ្តាលឱ្យចាញ់។ ដូច្នេះលេងល្បែងឆ្លងកាត់រន្ធ E3 ទៅ B2:
(2)
ការរុញតែមួយគត់ដែលយើងអាចធ្វើបានគឺ A, ប្រអប់ B3 រហូតដល់ B4 (មិនមែន B5 ដែលមានន័យថាចាញ់) ឬប្រអប់ C2 ទៅខាងស្តាំ។
យើងដឹងថាប្រអប់មិនអាចផ្លាស់ទីទៅចំណុចនៅលើផ្លូវឆ្លងកាត់ G3 បានទេព្រោះវាមិនអាចផ្លាស់ទីទៅខាងឆ្វេងនៅពេលក្រោយ ដូចដែលបានឃើញក្នុង 1.2 ។
ប៉ុន្តែដើម្បីផ្លាស់ទីពួកវាតាមរន្ធ B3, C3 យើងត្រូវការកន្លែងទំនេរនៅក្នុងតំបន់នេះ ដូច្នេះយើងត្រូវដាក់ប្រអប់មួយ ឬពីរនៅខាងស្តាំ ហើយត្រូវយកវាមកវិញនៅពេលក្រោយ។
យើងក៏ដឹងដែរថាប្រអប់ B3 អាចផ្លាស់ទីបានតែនៅលើបន្ទាត់ B ដូច្នេះទីបំផុតនឹងត្រូវបញ្ចប់នៅលើចំណុច B4 ។
ដើម្បីផ្លាស់ទីប្រអប់នៅពេលក្រោយនៅលើ C4 ហើយបន្ទាប់មករុញពួកវាទៅខាងស្តាំ អ្នកលេងល្បែងត្រូវតែអាចផ្លាស់ទីទៅ A4 ប៉ុន្តែដើម្បីទៅដល់ទីនោះពីខាងក្រោម ប្រអប់ B3 ត្រូវតែនៅ B2 ហើយចន្លោះ B3, C3, C2 ត្រូវតែទំនេរ ដូច្នេះពីរ ប្រអប់ត្រូវតែចេញពីផ្លូវ ហើយត្រូវចតនៅខាងស្តាំខាងក្រោម។
ដូច្នេះ ដើម្បីយកប្រអប់ C2 ចេញពីផ្លូវ ហើយយកអ្នកលេងល្បែងទៅខាងឆ្វេងខាងលើ យើងអាចប្រើឧទាហរណ៍ 2.1 ហើយឈានដល់។
(3)
ដោយរុញចុះក្រោម ប្រអប់A3 ឬB3ពុំមានការប្រែប្រួលទេ។ មានជម្រើសតែមួយគត់ដែលយើងនៅក្នុងទីតាំង2គឺរុញប្រអប់B3 ឡើងទៅដល់B4មុន ហើយបន្ទាប់មកប្តូរទៅទីតាំងទី3។ យើងបាន៖
(4)
ឥឡូវនេះយើងអាចដំណើរការបានដោយរុញប្រអប់ C3 ចុះទៅ C2 ហើយផ្លាស់ទីជាមួយអ្នកលេងល្បែងជុំវិញដើម្បីរុញប្រអប់ F2 ទៅ G2 និង G3៖
(5)
ដូចដែលបានពិភាក្សាខាងលើ យើងត្រូវការចន្លោះ B3, C3, C2 ឲ្យនៅទំនេរ ហើយយកប្រអប់ B4 ចុះទៅ B2 ដូច្នេះយើងត្រូវដាក់ប្រអប់ C2 ជាបណ្តោះអាសន្ននៅលើ G2សិន។ យើងបាន៖
(6)
ឥឡូវយើងអាចធ្វើតាមផែនការដំបូងរបស់យើងហើយរុញប្រអប់ G2 ទៅកាន់ C4ដើម្បីរុញវាបន្ថែមទៀតឲ្យទៅខាងស្តាំ។
(7)
សំណួរគឺថាតើយើងត្រូវរុញប្រអប់ C4 នោះដល់កម្រិតណា? ដោយសារតែយើងនៅតែត្រូវរុញប្រអប់ G3 ឆ្លងកាត់ផ្លូវដដែល យើងត្រូវយកអ្នកលេងល្បែងទៅ 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ក្ស័យធនឡើយ។
ដើម្បីញែករវាងករណីពីរ។ ករណីមួយត្រូវការមើលរាល់ទំនាក់ទំនងទាំងអស់ហើយមិនត្រឹមតែបុគ្គលម្នាក់នោះទេ តែវាអាស្រ័យលើនិយមន័យនៃពាក្សក្ស័យធនខាងលើដែលវាប្រទាក់ក្រឡាគ្នា។
Cadangan cara bermain Sokoban
Notasi
Panduan ini akan menggunakan istilah berikut:
- Langkah: satu langkah pekerja sama ada menolak atau tidak menolak kotak.
- Laluan: urutan pergerakan.
- Lokasi: Keadaan pekerja dan semua kotak berada di tempat tertentu.
- Penyelesaian: lokasi di mana setiap kotak terletak di atas satu titik.
- Laluan penyelesaian: urutan pergerakan dari lokasi asal ke penyelesaian.
- Lokasi buntu: lokasi yang penyelesaiannya tidak dapat dicapai.
Strategi Umum
Penyelesaian terpendek mungkin mengandungi 100, 300 atau 1000 langkah. (Permainan paling mudah 1 kita sudah memerlukan 73 langkah, permainan 8 memerlukan 126 langkah.) Jika secara purata, katakan, 2 kemungkinan untuk setiap langkah dan penyelesaiannya mengambil 100 langkah maka pencarian kekerasan memerlukan mencari 2^100 laluan untuk mencari penyelesaian. Malah untuk komputer ini tidak mungkin. Oleh itu kita perlu:
- Mengenali terlebih dahulu jika lokasi itu buntu,
- Pecahkan matlamat keseluruhan kepada sub tugasan. Jika laluan penyelesaian 100 langkah boleh dipecahkan kepada, katakan, 10 sub tugasan maka kerumitan soalan dikurangkan secara drastik. Tambahan pula, adalah mungkin untuk menyimpulkan susunan sub tugasan perlu diselesaikan dan kemudian keseluruhan soalan menjadi mudah untuk diselesaikan,
- Cari sekatan pada laluan penyelesaian.
- Fikirkan tentang heuristik lain.
Mengenai 1: Mengenali lokasi buntu terlebih dahulu
1.1: Kadang-kadang mudah untuk memutuskan sama ada sesuatu lokasi adalah buntu, seseorang hanya perlu melihat kejiranan satu kotak. Apa yang diperlukan hanyalah pemeriksaan “tempatan”. Jika kotak tidak berdiri di atas titik dan tidak boleh digerakkan secara mendatar dan tidak menegak, maka lokasinya buntu. Kotak itu mungkin terhalang oleh dinding atau oleh kotak lain yang juga tidak boleh dialihkan.
Examples:
1.2: Adalah lebih sukar untuk melihat bahawa lokasi buntu jika kotak itu berada di sebelah dinding dan ia boleh ditolak tetapi hanya di sepanjang dinding di sebelah yang sama dan tiada satu pun tempat yang boleh dicapainya adalah titik.
Example:
1.3: Dalam generalisasi ini, kotak berada di sebelah dinding dan boleh dialihkan ke tempat di mana ia tidak mempunyai dinding di sisinya (tempat A di bawah), tetapi tempat jiran A yang bebas itu tidak boleh dicapai oleh pekerja selepas menolak kotak di sebelah A.
Example:
Ketiga-tiga kes ini boleh diputuskan secara tempatan dan tanpa memindahkan pekerja. Oleh itu, mereka boleh diperiksa dalam lokasi awal dan seseorang boleh menandakan tempat sebagai larang, katakan, dengan! supaya kotak itu tidak boleh ditolak di tempat sedemikian.
1.4: Dalam generalisasi lanjut, tempat A boleh dicapai oleh pekerja tetapi hanya dengan kos meletakkan kotak lain di tempat larangan.
Example:
Penjelasan ini adalah rekursif[1], iaitu mencirikan lokasi buntu dengan menggunakan perkataan lokasi buntu. Lokasi buntu sedemikian lebih sukar untuk dikenali kerana ia tidak dapat dikesan oleh pemeriksaan tempatan dan mungkin memerlukan langkah percubaan.
Mengenai 2: Merumus Sub Tugasan.
Contoh sub tugasan ialah:
- Pindahkan pekerja dari A ke B,
- Pindahkan kotak tertentu dari A ke B
Di mana setiap tugasan ini perlu diselesaikan tanpa mewujudkan lokasi buntu.
Contoh untuk (a): Bagaimana pekerja boleh melepasi kotak untuk sampai ke A:
→→→→
Semua ruang kosong diperlukan kerana pekerja perlu berjalan di sekeliling kotak. Sekiranya terdapat ruang kosong yang kurang maka pekerja tidak boleh melepasi kotak tanpa menghasilkan lokasi buntu.
Jika seseorang mengetahui banyak sub tugasan sedemikian dengan bentuk koridornya dengan teliti, maka seseorang itu menjimatkan banyak masa dengan tidak perlu memikirkannya, di sini laluan 9-langkah ini.Lebih penting lagi, seseorang itu tidak akan berputus asa kerana menganggap sub tugasan ini adalah mustahil.
Soalan yang berkaitan dengan sub tugasan ialah cara mencarinya. Sub tugasan muncul, sebagai contoh, apabila menyelesaikan soalan secara terbalik. Katakan titik tertentu hanya boleh dicapai dari satu sisi dan hanya dengan satu kotak. Oleh itu, kotak ini perlu ditolak ke arah tertentu. Untuk berbuat demikian, pekerja perlu pergi ke sisi lain. Satu tugas boleh membawa kotak dan pekerja dalam lokasi yang betul.
Satu lagi contoh tipikal untuk menghasilkan sub tugasan ialah yang berikut. Adalah selamat untuk mengandaikan bahawa semua ruang dalaman dalam lokasi diperlukan untuk penyelesaian. Ini bermakna, jika lokasi asal mempunyai ruang dalaman yang besar seperti 2 kali 3 kawasan kosong dalam contoh di atas, maka seseorang boleh bertanya apakah tujuan ruang itu. Boleh jadi ia diperlukan oleh pekerja untuk melepasi kotak atau ia digunakan untuk meletak kotak sementara untuk mengosongkan ruang di tempat lain secara pertengahan. Jadi jika ruang yang besar mampu menyimpan sebuah kotak buat sementara waktu maka kotak yang manakah itu? Bagaimanakah seseorang boleh membawa kotak ini ke tempat sementara?
Mengenai 3: Merumuskan Sekatan pada Laluan Penyelesaian.
Terdapat banyak sekatan pada laluan penyelesaian yang mungkin hanya dengan melihat lokasi tanpa mencuba langkah. Contohnya ialah
3.1: Terdapat koridor yang boleh dimasuki oleh kotak tetapi kotak itu tidak boleh bergerak melalui keseluruhan koridor dan oleh itu ruang di hujung koridor tidak boleh dicapai dari sisi di mana koridor itu berakhir.
contohnya, Titik A tidak boleh dicapai oleh kotak yang terletak di B dan B tidak boleh dicapai oleh kotak yang duduk di A dengan melalui sudut.
3.2: Titik tertentu boleh dicapai hanya dari satu sisi walaupun terdapat ruang kosong pada sisi yang berbeza.
contohnya, Titik itu tidak boleh dicapai oleh kotak dari bawah.
3.3: Kotak tertentu tidak boleh dialihkan ke arah tertentu dan oleh itu hanya boleh mencapai satu titik tertentu.
contohnya, kotak hanya boleh mencapai titik di sebelah kirinya.
3.4: Oleh kerana titik boleh dicapai dengan kotak hanya dari beberapa bahagian, ia menentukan susunan titik mesti diduduki.
contohnya, Dalam lokasi berikut, titik kiri perlu diduduki sebelum titik di sebelah kanannya.
3.5: Mungkin jelas titik mana yang perlu ditutup terakhir kerana ruang diperlukan untuk pekerja menolak kotak ke arah tertentu.
contohnya, Ruang titik paling kanan diperlukan untuk pekerja berdiri dan menolak kotak ke kiri, jadi titik paling kanan adalah yang terakhir untuk diduduki, (dalam gambar yang sama seperti di atas).Mengenai 4: Other Heuristics
4.1: Sebarang urutan tolakan yang boleh diterbalikkan dan harus dicuba, walaupun ia bermakna pekerja perlu pergi jauh untuk menolak dari sisi lain untuk membalikkan tolakan ini. Walaupun latihan sebegitu kelihatan sia-sia, lokasi baharu mungkin membuka kemungkinan baharu bagaimana untuk meneruskan.
4.2: Jika terdapat garis lurus yang memisahkan semua titik daripada sekurang-kurangnya satu kotak, maka kotak ini mesti melintasi garisan tersebut. Jika ini tidak mungkin maka lokasi itu buntu. Jika terdapat hanya satu cara untuk kotak itu melepasi garisan itu maka ini adalah sekatan yang kuat untuk laluan penyelesaian.
Contoh Penyelesaian Lengkap, Permainan 8
(1)
Kita memperkenalkan koordinat kepada titik label. Contohnya, pekerja pada mulanya berada di titik G1.
Pada mulanya, pekerja hanya mempunyai 2 pilihan: A, untuk melalui lubang G3, atau B, untuk melalui lubang E3. Melalui G3 hanya membenarkan pekerja menolak kotak di B3 ke B1, mengakibatkan buntu. Jadi pekerja melalui lubang E3 ke B2:
(2)
Satu-satunya tolakan yang boleh kita lakukan ialah A, kotak B3 sehingga B4 (bukan ke B5 yang bermaksud buntu), atau kotak C2 ke kanan.
Kita menyedari bahawa kotak tidak boleh dialihkan ke titik pada laluan melalui G3 kerana ia tidak boleh dialihkan ke kiri selepas itu, seperti yang dilihat dalam 1.2.
Tetapi untuk memindahkannya melalui lubang B3, C3, kita memerlukan ruang di kawasan ini, jadi kita perlu meletakkan satu atau dua kotak di sebelah kanan dan perlu mendapatkannya semula selepas itu.
Kita juga menyedari bahawa kotak B3 hanya boleh dialihkan pada garisan B dan oleh itu akhirnya perlu berakhir pada titik B4.
Untuk mengalihkan kotak pada C4 kemudian dan kemudian untuk menolaknya ke kanan, pekerja mesti boleh bergerak ke A4 tetapi untuk ke sana dari bawah, kotak B3 mesti berada di ruang B2 dan ruang B3, C3, C2 mesti kosong, jadi dua kotak mesti keluar dari laluan dan diletakkan di bahagian bawah sebelah kanan.
Jadi, untuk menyingkirkan kotak C2 dan membawa pekerja ke sebelah kiri atas, kita boleh menggunakan contoh 2.1 dan mencapai.
(3)
tetapi menolak kotak A3 atau B3 ke bawah tidak berfungsi. Satu-satunya pilihan lain yang kita ada di lokasi 2 adalah untuk menolak kotak B3 sehingga B4 terlebih dahulu dan kemudian melakukan langkah menuju ke lokasi 3. Kita mendapat
(4)
Kini kita boleh membuat kemajuan dengan menolak kotak C3 ke C2 dan bergerak bersama pekerja untuk menolak kotak F2 ke G2 dan G3:
(5)
Seperti yang dibincangkan di atas, kita memerlukan ruang B3, C3, C2 bebas dan menolak kotak B4 ke B2, jadi kita perlu meletakkan kotak C2 buat sementara pada G2. Kita mendapat
(6)
Sekarang kita boleh mengikut rancangan awal kita dan menolak kotak G2 ke C4 untuk menolaknya lebih jauh ke kanan:
(7)
Persoalannya adalah sejauh mana kita perlu menolak kotak C4 itu. Kerana kita masih perlu menolak kotak G3 melalui laluan yang sama, kita perlu membawa pekerja ke G4 dan untuk melakukan itu, kita perlu menolak kotak C4 sejauh F4 dan memindahkan pekerja ke G4 untuk menolak G4 ke G3:
(8)
Untuk mengalihkan kotak G2 ke kiri, pekerja perlu bergerak jauh ke belakang arah lawan jam ke H2.
(9)
Selebihnya mudah: kotak G2 ditolak ke C2, C4, D4
(10)
kemudian kotak B2 ditolak ke B4 dan kemudian pekerja bergerak ke G4 untuk akhirnya menolak kotak F4 pada titik E4.
SELESAI.
Seseorang muflis jika orang itu memiliki wang orang lain dan tidak mempunyai wang tunai dan sama ada tidak mempunyai resit kerana meminjam wang orang lain, atau mempunyai resit kerana meminjam wang orang lain tetapi orang itu muflis.
Penjelasan perkataan muflis ini menggunakan perkataan muflis, dan oleh itu ia dipanggil rekursif.
Contoh:
Orang A,B,C tidak mempunyai wang, mereka semua berhutang wang kepada orang D,
A mempunyai resit untuk meminjam wang kepada B,
B mempunyai resit untuk meminjam wang kepada C,
C mempunyai resit untuk meminjam wang kepada A.
tetapi mereka sebagai satu kumpulan muflis, setiap orang daripada mereka.
Keadaan yang sama tetapi berbeza:
Orang A,B,C tidak mempunyai wang, mereka semua berhutang wang kepada orang D,
A mempunyai resit untuk meminjam wang kepada B,
B mempunyai resit untuk meminjam wang kepada C,
C mempunyai resit untuk meminjam wang kepada F.
Kerana orang F mungkin mempunyai wang, mungkin tidak ada daripada A,B,C yang muflis.
Untuk membezakan antara kedua-dua kes seseorang perlu melihat semua hubungan, bukan hanya satu secara individu kerana definisi muflis di atas adalah rekursif.
Follow or subscribe for updates: