Sokoban: Difference between revisions
Content added Content deleted
No edit summary |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 10: | Line 10: | ||
* + is the player on a goal |
* + is the player on a goal |
||
* * is a box on a goal |
* * is a box on a goal |
||
<lang>####### |
<syntaxhighlight lang="text">####### |
||
# # |
# # |
||
# # |
# # |
||
Line 17: | Line 17: | ||
#.$$ # |
#.$$ # |
||
#.# @# |
#.# @# |
||
#######</ |
#######</syntaxhighlight> |
||
Sokoban solutions are usually stored in the LURD format, where lowercase l, u, r and d represent a move in that ('''l'''eft, '''u'''p, '''r'''ight, '''d'''own) direction and capital LURD represents a push. |
Sokoban solutions are usually stored in the LURD format, where lowercase l, u, r and d represent a move in that ('''l'''eft, '''u'''p, '''r'''ight, '''d'''own) direction and capital LURD represents a push. |
||
Line 29: | Line 29: | ||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="11l">[String] data |
||
V nrows = 0 |
V nrows = 0 |
||
V px = 0 |
V px = 0 |
||
Line 115: | Line 115: | ||
init(level) |
init(level) |
||
print(level"\n\n"solve())</ |
print(level"\n\n"solve())</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 133: | Line 133: | ||
=={{header|Befunge}}== |
=={{header|Befunge}}== |
||
El código no es mío, sólo lo reproduzco. |
El código no es mío, sólo lo reproduzco. |
||
< |
<syntaxhighlight lang="befunge"> |
||
589*+0g"0"-25**689*+0g"0"-+50p v # Sokoban - (c) Matthew Westcott 2000 # 03 |
589*+0g"0"-25**689*+0g"0"-+50p v # Sokoban - (c) Matthew Westcott 2000 # 03 |
||
83*>10p99*2->:00p10gg"x"-#v_v p01g<> ## # # # # # # # # # # # # # # # # # # # |
83*>10p99*2->:00p10gg"x"-#v_v p01g<> ## # # # # # # # # # # # # # # # # # # # |
||
Line 159: | Line 159: | ||
#0 x 0# |
#0 x 0# |
||
######## |
######## |
||
</syntaxhighlight> |
|||
</lang> |
|||
=={{header|C}}== |
=={{header|C}}== |
||
Long, long, long C99 code (plus GNU C nested functions). Doesn't output the movement keys, instead it animates the sequence for you. Solution is move optimized. For an even longer solution, see [[Sokoban/C]]. |
Long, long, long C99 code (plus GNU C nested functions). Doesn't output the movement keys, instead it animates the sequence for you. Solution is move optimized. For an even longer solution, see [[Sokoban/C]]. |
||
< |
<syntaxhighlight lang="c">#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
#include <string.h> |
#include <string.h> |
||
Line 564: | Line 564: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|C sharp|C#}}== |
=={{header|C sharp|C#}}== |
||
< |
<syntaxhighlight lang="csharp">using System.Collections.Generic; |
||
using System.Linq; |
using System.Linq; |
||
using System.Text; |
using System.Text; |
||
Line 740: | Line 740: | ||
} |
} |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> |
<pre> |
||
Line 765: | Line 765: | ||
This performs a breadth-first search by moves, so the results should be a move-optimal solution. |
This performs a breadth-first search by moves, so the results should be a move-optimal solution. |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <string> |
#include <string> |
||
#include <vector> |
#include <vector> |
||
Line 918: | Line 918: | ||
cout << level << endl << endl << b.solve() << endl; |
cout << level << endl << endl << b.solve() << endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
Output: |
Output: |
||
Line 938: | Line 938: | ||
{{works with|GCC 4.6}} |
{{works with|GCC 4.6}} |
||
Alternative version, about twice faster (about 2.1 seconds runtime), same output. |
Alternative version, about twice faster (about 2.1 seconds runtime), same output. |
||
< |
<syntaxhighlight lang="cpp">#include <iostream> |
||
#include <string> |
#include <string> |
||
#include <vector> |
#include <vector> |
||
Line 1,077: | Line 1,077: | ||
cout << board.solve() << endl; |
cout << board.solve() << endl; |
||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|D}}== |
=={{header|D}}== |
||
Line 1,083: | Line 1,083: | ||
{{trans|C++}} |
{{trans|C++}} |
||
This version uses the queue defined in the Queue/Usage task. |
This version uses the queue defined in the Queue/Usage task. |
||
< |
<syntaxhighlight lang="d">import std.string, std.typecons, std.exception, std.algorithm; |
||
import queue_usage2; // No queue in Phobos 2.064. |
import queue_usage2; // No queue in Phobos 2.064. |
||
Line 1,227: | Line 1,227: | ||
immutable b = immutable(Board)(level.splitLines); |
immutable b = immutable(Board)(level.splitLines); |
||
writeln(level, "\n\n", b.solve); |
writeln(level, "\n\n", b.solve); |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>####### |
<pre>####### |
||
Line 1,244: | Line 1,244: | ||
{{trans|C}} |
{{trans|C}} |
||
This code is not idiomatic D, it retains most of the style of the C version. |
This code is not idiomatic D, it retains most of the style of the C version. |
||
< |
<syntaxhighlight lang="d">import core.stdc.stdio: printf, puts, fflush, stdout, putchar; |
||
import core.stdc.stdlib: malloc, calloc, realloc, free, alloca, exit; |
import core.stdc.stdlib: malloc, calloc, realloc, free, alloca, exit; |
||
Line 1,657: | Line 1,657: | ||
return 0; |
return 0; |
||
}</ |
}</syntaxhighlight> |
||
=={{header|Elixir}}== |
=={{header|Elixir}}== |
||
{{works with|Elixir|1.3}} |
{{works with|Elixir|1.3}} |
||
{{trans|Ruby}} |
{{trans|Ruby}} |
||
< |
<syntaxhighlight lang="elixir">defmodule Sokoban do |
||
defp setup(level) do |
defp setup(level) do |
||
{leng, board} = normalize(level) |
{leng, board} = normalize(level) |
||
Line 1,842: | Line 1,842: | ||
""" |
""" |
||
IO.puts level |
IO.puts level |
||
Sokoban.solve(level)</ |
Sokoban.solve(level)</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 1,861: | Line 1,861: | ||
{{trans|C++}} |
{{trans|C++}} |
||
Well, it started as a C++ translation, but turned out different. It's still the breadth-first set-based algorithm, but I dropped the sdata/ddata optimization and just maintained a single string as the board representation. Also dropped the code to handle non-rectangular boards, and probably some other stuff too. |
Well, it started as a C++ translation, but turned out different. It's still the breadth-first set-based algorithm, but I dropped the sdata/ddata optimization and just maintained a single string as the board representation. Also dropped the code to handle non-rectangular boards, and probably some other stuff too. |
||
< |
<syntaxhighlight lang="go">package main |
||
import ( |
import ( |
||
Line 1,977: | Line 1,977: | ||
} |
} |
||
return string(buffer) |
return string(buffer) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 1,994: | Line 1,994: | ||
=={{header|Haskell}}== |
=={{header|Haskell}}== |
||
< |
<syntaxhighlight lang="haskell">import Control.Monad (liftM) |
||
import Data.Array |
import Data.Array |
||
import Data.List (transpose) |
import Data.List (transpose) |
||
Line 2,125: | Line 2,125: | ||
mapM_ putStrLn exampleA |
mapM_ putStrLn exampleA |
||
putStrLn "" |
putStrLn "" |
||
putStrLn $ concatMap show solution</ |
putStrLn $ concatMap show solution</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>####### |
<pre>####### |
||
Line 2,141: | Line 2,141: | ||
Translation of [[Sokoban#C++|C++]] via [[Sokoban#D|D]] |
Translation of [[Sokoban#C++|C++]] via [[Sokoban#D|D]] |
||
{{works with|Java|7}} |
{{works with|Java|7}} |
||
< |
<syntaxhighlight lang="java">import java.util.*; |
||
public class Sokoban { |
public class Sokoban { |
||
Line 2,278: | Line 2,278: | ||
System.out.println(new Sokoban(level.split(",")).solve()); |
System.out.println(new Sokoban(level.split(",")).solve()); |
||
} |
} |
||
}</ |
}</syntaxhighlight> |
||
<pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
<pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
||
Line 2,284: | Line 2,284: | ||
=={{header|Julia}}== |
=={{header|Julia}}== |
||
{{trans|Go}} |
{{trans|Go}} |
||
< |
<syntaxhighlight lang="julia">struct BoardState |
||
board::String |
board::String |
||
csol::String |
csol::String |
||
Line 2,377: | Line 2,377: | ||
#######""") |
#######""") |
||
println("For sokoban level:\n$testlevel\n...solution is :\n$(solve(testlevel))") |
println("For sokoban level:\n$testlevel\n...solution is :\n$(solve(testlevel))") |
||
</ |
</syntaxhighlight>{{output}}<pre> |
||
For sokoban level: |
For sokoban level: |
||
####### |
####### |
||
Line 2,393: | Line 2,393: | ||
=={{header|Kotlin}}== |
=={{header|Kotlin}}== |
||
{{trans|Java}} |
{{trans|Java}} |
||
< |
<syntaxhighlight lang="scala">// version 1.2.0 |
||
import java.util.LinkedList |
import java.util.LinkedList |
||
Line 2,508: | Line 2,508: | ||
println() |
println() |
||
println(Sokoban(level).solve()) |
println(Sokoban(level).solve()) |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,528: | Line 2,528: | ||
We have chosen to use a double queue (deque) instead of a linked list. |
We have chosen to use a double queue (deque) instead of a linked list. |
||
< |
<syntaxhighlight lang="nim">import deques, sets, strutils |
||
type |
type |
||
Line 2,626: | Line 2,626: | ||
echo Level.join("\n") |
echo Level.join("\n") |
||
echo() |
echo() |
||
echo initSokoban(Level).solve()</ |
echo initSokoban(Level).solve()</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 2,643: | Line 2,643: | ||
{{trans|Python}} |
{{trans|Python}} |
||
This uses a breadth-first move search, so will find a move-optimal solution. |
This uses a breadth-first move search, so will find a move-optimal solution. |
||
< |
<syntaxhighlight lang="ocaml">type dir = U | D | L | R |
||
type move_t = Move of dir | Push of dir |
type move_t = Move of dir | Push of dir |
||
Line 2,736: | Line 2,736: | ||
"#.# @#"; |
"#.# @#"; |
||
"#######"] in |
"#######"] in |
||
solve level</ |
solve level</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>luULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
<pre>luULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
||
Line 2,756: | Line 2,756: | ||
would still be a valid solution. I could fix it, but at the cost of speed and memory. |
would still be a valid solution. I could fix it, but at the cost of speed and memory. |
||
< |
<syntaxhighlight lang="perl">#!perl |
||
use strict; |
use strict; |
||
use warnings qw(FATAL all); |
use warnings qw(FATAL all); |
||
Line 2,960: | Line 2,960: | ||
} |
} |
||
__END__ |
__END__ |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
<pre>Solution found! |
<pre>Solution found! |
||
Line 2,983: | Line 2,983: | ||
Push-optimised, prunes (breadth-first) search space to reachable pushable-to-live boxes.<br> |
Push-optimised, prunes (breadth-first) search space to reachable pushable-to-live boxes.<br> |
||
Fairly fast, but often produces same-push-tally but longer results than move-optimised. |
Fairly fast, but often produces same-push-tally but longer results than move-optimised. |
||
< |
<syntaxhighlight lang="phix">-- demo\rosetta\Sokoban.exw |
||
integer w, h -- (set from parsing the input grid) |
integer w, h -- (set from parsing the input grid) |
||
sequence moves -- "", as +/-w and +/-1 (udlr) |
sequence moves -- "", as +/-w and +/-1 (udlr) |
||
Line 3,153: | Line 3,153: | ||
printf(1,"solution of %d pushes (%s)\n",{pop,elapsed(time()-t0)}) |
printf(1,"solution of %d pushes (%s)\n",{pop,elapsed(time()-t0)}) |
||
plays(level,pushset) |
plays(level,pushset) |
||
end if</ |
end if</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Note that a full solution in LURD format would show as 48 moves, as opposed to |
Note that a full solution in LURD format would show as 48 moves, as opposed to |
||
Line 3,179: | Line 3,179: | ||
Other tests: |
Other tests: |
||
< |
<syntaxhighlight lang="phix">constant input = """ |
||
############# |
############# |
||
# # # |
# # # |
||
Line 3,185: | Line 3,185: | ||
#....... # |
#....... # |
||
############# |
############# |
||
"""</ |
"""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,214: | Line 3,214: | ||
</pre> |
</pre> |
||
Test #3 |
Test #3 |
||
< |
<syntaxhighlight lang="phix">constant input = """ |
||
#### |
#### |
||
##. ## |
##. ## |
||
Line 3,223: | Line 3,223: | ||
###### ## |
###### ## |
||
#### |
#### |
||
"""</ |
"""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,246: | Line 3,246: | ||
</pre> |
</pre> |
||
Test #4 |
Test #4 |
||
< |
<syntaxhighlight lang="phix">constant input = """ |
||
############# |
############# |
||
#... # # |
#... # # |
||
Line 3,252: | Line 3,252: | ||
#... # |
#... # |
||
############# |
############# |
||
"""</ |
"""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,270: | Line 3,270: | ||
</pre> |
</pre> |
||
Test #5 |
Test #5 |
||
< |
<syntaxhighlight lang="phix">constant input = """ |
||
##### |
##### |
||
# # |
# # |
||
Line 3,282: | Line 3,282: | ||
# ######### |
# ######### |
||
####### |
####### |
||
"""</ |
"""</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
Line 3,315: | Line 3,315: | ||
=={{header|PicoLisp}}== |
=={{header|PicoLisp}}== |
||
This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized. |
This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized. |
||
< |
<syntaxhighlight lang="picolisp">(load "@lib/simul.l") |
||
# Display board |
# Display board |
||
Line 3,396: | Line 3,396: | ||
(pushes) ) |
(pushes) ) |
||
(display) # Display solution |
(display) # Display solution |
||
(pack (flip Res)) ) ) )</ |
(pack (flip Res)) ) ) )</syntaxhighlight> |
||
Test: |
Test: |
||
< |
<syntaxhighlight lang="picolisp">(main |
||
(quote |
(quote |
||
"#######" |
"#######" |
||
Line 3,409: | Line 3,409: | ||
"#######" ) ) |
"#######" ) ) |
||
(prinl) |
(prinl) |
||
(go)</ |
(go)</syntaxhighlight> |
||
Output: |
Output: |
||
<pre> 8 # # # # # # # |
<pre> 8 # # # # # # # |
||
Line 3,436: | Line 3,436: | ||
{{works with|Psyco}} |
{{works with|Psyco}} |
||
{{works with|Python 2.6}} |
{{works with|Python 2.6}} |
||
< |
<syntaxhighlight lang="python">from array import array |
||
from collections import deque |
from collections import deque |
||
import psyco |
import psyco |
||
Line 3,531: | Line 3,531: | ||
psyco.full() |
psyco.full() |
||
init(level) |
init(level) |
||
print level, "\n\n", solve()</ |
print level, "\n\n", solve()</syntaxhighlight> |
||
Output: |
Output: |
||
<pre>####### |
<pre>####### |
||
Line 3,548: | Line 3,548: | ||
This was originally inspired by PicoLisp's solution. Modified to use a priority queue as mentioned on the Sokoban wiki for the main breadth first search on pushes but just a plain queue for the move bfs. This uses personal libraries. Vector2 isn't strictly needed but the math/array library is not currently optimized for untyped Racket. push! is comparable to lisp's, awhen is anaphoric when, ret uses the bound value as the result of its expression, and tstruct is short for struct with the #:transparent option. |
This was originally inspired by PicoLisp's solution. Modified to use a priority queue as mentioned on the Sokoban wiki for the main breadth first search on pushes but just a plain queue for the move bfs. This uses personal libraries. Vector2 isn't strictly needed but the math/array library is not currently optimized for untyped Racket. push! is comparable to lisp's, awhen is anaphoric when, ret uses the bound value as the result of its expression, and tstruct is short for struct with the #:transparent option. |
||
<syntaxhighlight lang="racket"> |
|||
<lang Racket> |
|||
#lang racket |
#lang racket |
||
(require data/heap |
(require data/heap |
||
Line 3,656: | Line 3,656: | ||
(pushes s clear)) |
(pushes s clear)) |
||
(bfs)]))) |
(bfs)]))) |
||
</syntaxhighlight> |
|||
</lang> |
|||
{{out}} |
{{out}} |
||
Line 3,669: | Line 3,669: | ||
(formerly Perl 6) |
(formerly Perl 6) |
||
{{trans|Go}} |
{{trans|Go}} |
||
<lang |
<syntaxhighlight lang="raku" line>sub MAIN() { |
||
my $level = q:to//; |
my $level = q:to//; |
||
####### |
####### |
||
Line 3,769: | Line 3,769: | ||
} |
} |
||
return "No solution"; |
return "No solution"; |
||
}</ |
}</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
<pre>Level: |
<pre>Level: |
||
Line 3,784: | Line 3,784: | ||
=={{header|Ring}}== |
=={{header|Ring}}== |
||
< |
<syntaxhighlight lang="ring"> |
||
#--------------------------------------------------# |
#--------------------------------------------------# |
||
# Sokoban Game # |
# Sokoban Game # |
||
Line 4,167: | Line 4,167: | ||
UpdateGameMap(oGame) |
UpdateGameMap(oGame) |
||
lPlayerWin = False |
lPlayerWin = False |
||
</syntaxhighlight> |
|||
</lang> |
|||
Output image: |
Output image: |
||
Line 4,178: | Line 4,178: | ||
===Simple Version=== |
===Simple Version=== |
||
{{trans|Python}} |
{{trans|Python}} |
||
< |
<syntaxhighlight lang="ruby">require 'set' |
||
class Sokoban |
class Sokoban |
||
Line 4,236: | Line 4,236: | ||
"No solution" |
"No solution" |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
'''Test:''' |
'''Test:''' |
||
< |
<syntaxhighlight lang="ruby">level = <<EOS |
||
####### |
####### |
||
# # |
# # |
||
Line 4,248: | Line 4,248: | ||
####### |
####### |
||
EOS |
EOS |
||
puts level, "", Sokoban.new(level).solve</ |
puts level, "", Sokoban.new(level).solve</syntaxhighlight> |
||
{{out}} |
{{out}} |
||
Line 4,269: | Line 4,269: | ||
When a box is pushed there, it doesn't process after that. |
When a box is pushed there, it doesn't process after that. |
||
< |
<syntaxhighlight lang="ruby">class Sokoban |
||
def initialize(level) |
def initialize(level) |
||
board = level.lines.map(&:rstrip) |
board = level.lines.map(&:rstrip) |
||
Line 4,363: | Line 4,363: | ||
"No solution" |
"No solution" |
||
end |
end |
||
end</ |
end</syntaxhighlight> |
||
Runtime: about 0.20 seconds. |
Runtime: about 0.20 seconds. |
||
Line 4,369: | Line 4,369: | ||
This code does a breadth-first search so it finds a solution with a minimum number of moves. |
This code does a breadth-first search so it finds a solution with a minimum number of moves. |
||
{{trans|OCaml}}<!-- the big difference is that this is all in one procedure for speed as it reduces the amount of packing/unpacking of tuples/lists, and the queue isn't shortened as that's significantly slower for these sorts of board sizes --> |
{{trans|OCaml}}<!-- the big difference is that this is all in one procedure for speed as it reduces the amount of packing/unpacking of tuples/lists, and the queue isn't shortened as that's significantly slower for these sorts of board sizes --> |
||
< |
<syntaxhighlight lang="tcl">package require Tcl 8.5 |
||
proc solveSokoban b { |
proc solveSokoban b { |
||
Line 4,438: | Line 4,438: | ||
} |
} |
||
error "no solution" |
error "no solution" |
||
}</ |
}</syntaxhighlight> |
||
Demonstration code: |
Demonstration code: |
||
< |
<syntaxhighlight lang="tcl">set level { |
||
"#######" |
"#######" |
||
"# #" |
"# #" |
||
Line 4,450: | Line 4,450: | ||
"#######" |
"#######" |
||
} |
} |
||
puts [solveSokoban $level]</ |
puts [solveSokoban $level]</syntaxhighlight> |
||
Output: <pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
Output: <pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre> |
||
Runtime with stock Tcl 8.5 installation: ≅2.2 seconds<!-- on what is now a fairly old machine --> |
Runtime with stock Tcl 8.5 installation: ≅2.2 seconds<!-- on what is now a fairly old machine --> |
||
Line 4,460: | Line 4,460: | ||
{{libheader|Wren-set}} |
{{libheader|Wren-set}} |
||
This works but at a rather sedate pace - 26.7 seconds. |
This works but at a rather sedate pace - 26.7 seconds. |
||
< |
<syntaxhighlight lang="ecmascript">import "/dynamic" for Tuple |
||
import "/llist" for DLinkedList |
import "/llist" for DLinkedList |
||
import "/set" for Set |
import "/set" for Set |
||
Line 4,566: | Line 4,566: | ||
System.print(level.join("\n")) |
System.print(level.join("\n")) |
||
System.print() |
System.print() |
||
System.print(Sokoban.new(level).solve())</ |
System.print(Sokoban.new(level).solve())</syntaxhighlight> |
||
{{out}} |
{{out}} |