Trying to solve a Sokoban level with brute force

Before you even think this script will solve a Sokoban level, I must warn you: this script won’t solve a sokoban level, it won’t even recognize whether a level is solved or not.

This script, part of an old project I am going to bring to life again, will just make Sokoban wander around the maze eventually pushing crates here and there, according to Sokoban’s rules.

Feel free to add some backtracking to make it more interesting, but I have to say coding a Sokoban solver could be a nightmare.

If you want to see another Sokoban script (this time to play the game), read Javascript Sokoban game script.

Sokoban levels are shown and created this way:

# = wall
$ = crate
. = place
* = crate in place
@ = man
+ = man in place

And now the script…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229

<?php
 
function echo_map($map,$width){
	$rows = strlen($map)/$width;
	for($x=0;$x<$rows;$x++){
		for($y=0;$y<$width;$y++){
			$pos = $y+$x*$width;
			if($map{$pos}==" "){
				$return .= "&nbsp;";
			}
			else{
				$return .= $map{$pos};
			}
		}
		$return .= "<br>";
	}
	return("<div style = \"font:normal 18px lucida console\">".$return."</div>");
}
 
function is_solved($map){
	return(!strpos($map,"$"));
}
 
function is_empty($map,$pos){
	return(($map{$pos}==" ")or($map{$pos}=="."));
}
 
function is_crate($map,$pos){
	return(($map{$pos}=="$")or($map{$pos}=="*"));
}
 
function get_player_pos($map){
	return(strpos($map,"@")+strpos($map,"+"));
}
 
function echo_possible_directions($map,$width){
	$player_pos = get_player_pos($map);
	if (is_empty($map,$player_pos-1) or (is_crate($map,$player_pos-1) and is_empty($map,$player_pos-2))){
		$return .= "L";
	}
	if (is_empty($map,$player_pos+1) or (is_crate($map,$player_pos+1) and is_empty($map,$player_pos+2))){
		$return .= "R";
	}
	if (is_empty($map,$player_pos-$width) or (is_crate($map,$player_pos-$width) and is_empty($map,$player_pos-2*$width))){
		$return .= "U";
	}
	if (is_empty($map,$player_pos+$width) or (is_crate($map,$player_pos+$width) and is_empty($map,$player_pos+2*$width))){
		$return .= "D";
	}
	return($return);
}
 
function move($map,$width,$dir){
	$player_pos = get_player_pos($map);
	if($dir=="L"){
		if($map{$player_pos}=="@"){
			$map{$player_pos} = " ";
		}
		else{
			$map{$player_pos} = ".";
		}
		if (!is_empty($map,$player_pos-1)){
			if($map{$player_pos-1}=="$"){
				if($map{$player_pos-2}==" "){
					$map{$player_pos-2}="$";
					$map{$player_pos-1}=" ";
				}
				else{
					$map{$player_pos-2}="*";
					$map{$player_pos-1}=" ";
				}
			}
			else{	
				if($map{$player_pos-2}==" "){
					$map{$player_pos-2}="$";
					$map{$player_pos-1}=".";
				}
				else{
					$map{$player_pos-2}="*";
					$map{$player_pos-1}=".";
				}
			}			
		}
		if($map{$player_pos-1}==" "){
			$map{$player_pos-1}="@";
		}
		else{
			$map{$player_pos-1}="+";
		}	
	}
	if($dir=="R"){
		if($map{$player_pos}=="@"){
			$map{$player_pos} = " ";
		}
		else{
			$map{$player_pos} = ".";
		}
		if (!is_empty($map,$player_pos+1)){
			if($map{$player_pos+1}=="$"){
				if($map{$player_pos+2}==" "){
					$map{$player_pos+2}="$";
					$map{$player_pos+1}=" ";
				}
				else{
					$map{$player_pos+2}="*";
					$map{$player_pos+1}=" ";
				}
			}
			else{	
				if($map{$player_pos+2}==" "){
					$map{$player_pos+2}="$";
					$map{$player_pos+1}=".";
				}
				else{
					$map{$player_pos+2}="*";
					$map{$player_pos+1}=".";
				}
			}			
		}
		if($map{$player_pos+1}==" "){
			$map{$player_pos+1}="@";
		}
		else{
			$map{$player_pos+1}="+";
		}	
	}
	if($dir=="U"){
		if($map{$player_pos}=="@"){
			$map{$player_pos} = " ";
		}
		else{
			$map{$player_pos} = ".";
		}
		if (!is_empty($map,$player_pos-$width)){
			if($map{$player_pos-$width}=="$"){
				if($map{$player_pos-2*$width}==" "){
					$map{$player_pos-2*$width}="$";
					$map{$player_pos-$width}=" ";
				}
				else{
					$map{$player_pos-2*$width}="*";
					$map{$player_pos-$width}=" ";
				}
			}
			else{	
				if($map{$player_pos-2*$width}==" "){
					$map{$player_pos-2*$width}="$";
					$map{$player_pos-$width}=".";
				}
				else{
					$map{$player_pos-2*$width}="*";
					$map{$player_pos-$width}=".";
				}
			}			
		}
		if($map{$player_pos-$width}==" "){
			$map{$player_pos-$width}="@";
		}
		else{
			$map{$player_pos-$width}="+";
		}	
	}
	if($dir=="D"){
		if($map{$player_pos}=="@"){
			$map{$player_pos} = " ";
		}
		else{
			$map{$player_pos} = ".";
		}
		if (!is_empty($map,$player_pos+$width)){
			if($map{$player_pos+$width}=="$"){
				if($map{$player_pos+2*$width}==" "){
					$map{$player_pos+2*$width}="$";
					$map{$player_pos+$width}=" ";
				}
				else{
					$map{$player_pos+2*$width}="*";
					$map{$player_pos+$width}=" ";
				}
			}
			else{	
				if($map{$player_pos+2*$width}==" "){
					$map{$player_pos+2*$width}="$";
					$map{$player_pos+$width}=".";
				}
				else{
					$map{$player_pos+2*$width}="*";
					$map{$player_pos-$width}=".";
				}
			}			
		}
		if($map{$player_pos+$width}==" "){
			$map{$player_pos+$width}="@";
		}
		else{
			$map{$player_pos+$width}="+";
		}	
	}
	return($map);
}
 
 
 
/*  
 
# = wall
$ = crate
. = place
* = crate in place
@ = man
+ = man in place
 
*/
 
$width = 8;
$map = "  ###     #.#     # #######$ $.##. $@#######$#     #.#     ###  ";
for($x=1;$x<=100;$x++){
     echo echo_map($map,$width);
     $possible = echo_possible_directions($map,$width);
     echo "Possible directions: $possible";
     $new_dir = $possible{rand(0,strlen($possible)-1)};
     echo " - going ".$new_dir;
     $map = move($map,$width,$new_dir);
     if(is_solved($map)){
          echo "<h1>S</h1>";
     }
}
 
?>

And this is the result:

Feel free to do something interesting with the script…

Rate this post: 1 Star2 Stars3 Stars4 Stars5 Stars (4 votes, average: 3.00 out of 5)
Loading ... Loading ...
If you found this post useful, please consider a small donation.

13 Responses

  1. It has not... says:
    January 22, 2009 at 12:52 am

    … been solved yet. but i can!

    Reply
  2. Alex says:
    January 22, 2009 at 3:38 am

    First off, I appologize if this offends you, but are you a boy or a girl?

    I ask only because First i thought you were a guy, because your name is Emanuele. But then you got your new logo and it looks like you are a girl. So i figured, “i guess Emanuele could be a girls name”. Now i see at the bottom of this post, “the geek has spoken… share HIS words”. This causes confusion for me.

    It really doesnt matter, i just want clarification. Either way, Great post. Love your work. Look forward to seeing more of your work

    Reply
  3. Xavi says:
    January 22, 2009 at 6:45 am

    lol… Alex.

    Reply
  4. FrozenHaddock says:
    January 22, 2009 at 1:54 pm

    Alex, after this post ( http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/ ) not even the regulars are sure anymore.

    :P

    Reply
  5. Shival says:
    January 22, 2009 at 2:22 pm

    What use is this script?

    Reply
  6. Xodus says:
    January 22, 2009 at 2:23 pm

    lol, he is a guy, the logo is a bit misleading but read this post:
    http://www.emanueleferonato.com/2009/01/14/improve-your-brand-with-a-logo-part-2/

    Reply
  7. Monkios says:
    January 22, 2009 at 3:48 pm

    The first thing I would do with this script is breaking out of the loop once is_solved() returns true.

    It is not a big optimization but the script wouldn’t print many useless iterations of the map.

    Reply
  8. dim says:
    January 22, 2009 at 5:12 pm

    i think, gilrs will never be interested with these kind of things :) this answer at half for the question i guess :)

    Reply
  9. dim says:
    January 22, 2009 at 5:13 pm

    oh, and thanks a lot for good posts Emauele … i’m yure fan !

    Reply
  10. Krystian Majewski says:
    January 22, 2009 at 8:25 pm

    Good job. Now you are just a step away from an evolutionary algorythm for generating Sokoban puzzles by the thousands.

    Reply
  11. Hey its that guy says:
    January 23, 2009 at 12:24 am

    Anyone know how I can contact Emanuele? I think someone may be trying to steal Emanuele’s games and put them under their own name.

    Reply
  12. Hey its that guy says:
    January 23, 2009 at 12:26 am

    Whoop, nevermind. Its not there anymore so I assume they did the right thing and removed it.

    Reply
  13. Prankard says:
    January 23, 2009 at 2:20 pm

    Looks good :)

    First the Soduku and now this. Keep up all these “classic” engines. I really am interested in learning how to make these type of common well used generic engines.

    Reply

Leave a Reply