Sokoban: Difference between revisions

* + is the player on a goal

* * is a box on a goal

 

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.

For more information, see [http://www.sokobano.de/wiki/index.php?title=Main_Page the Sokoban wiki].

 

 

=={{header|Befunge}}==

El código no es mío, sólo lo reproduzco.

589*+0g"0"-25**689*+0g"0"-+50p v # Sokoban - (c) Matthew Westcott 2000 # 03

83*>10p99*2->:00p10gg"x"-#v_v p01g<> ## # # # # # # # # # # # # # # # # # # #

#0 x 0#

########

 

=={{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]].

#include <stdlib.h>

#include <string.h>

 

return 0;

 

=={{header|C sharp|C#}}==

using System.Linq;

using System.Text;

}

}

Output:

<pre>

 

This performs a breadth-first search by moves, so the results should be a move-optimal solution.

#include <string>

#include <vector>

cout << level << endl << endl << b.solve() << endl;

return 0;

 

Output:

{{works with|GCC 4.6}}

Alternative version, about twice faster (about 2.1 seconds runtime), same output.

#include <string>

#include <vector>

cout << board.solve() << endl;

return 0;

 

=={{header|D}}==

{{trans|C++}}

This version uses the queue defined in the Queue/Usage task.

import queue_usage2; // No queue in Phobos 2.064.

 

immutable b = immutable(Board)(level.splitLines);

writeln(level, "\n\n", b.solve);

{{out}}

<pre>#######

{{trans|C}}

This code is not idiomatic D, it retains most of the style of the C version.

import core.stdc.stdlib: malloc, calloc, realloc, free, alloca, exit;

 

 

return 0;

 

=={{header|Elixir}}==

{{works with|Elixir|1.3}}

{{trans|Ruby}}

defp setup(level) do

{leng, board} = normalize(level)

"""

IO.puts level

 

{{out}}

{{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.

 

import (

}

return string(buffer)

{{out}}

<pre>

 

=={{header|Haskell}}==

import Data.Array

import Data.List (transpose)

mapM_ putStrLn exampleA

putStrLn ""

{{out}}

<pre>#######

Translation of [[Sokoban#C++|C++]] via [[Sokoban#D|D]]

{{works with|Java|7}}

 

public class Sokoban {

System.out.println(new Sokoban(level.split(",")).solve());

}

 

<pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>

=={{header|Julia}}==

{{trans|Go}}

board::String

csol::String

#######""")

println("For sokoban level:\n$testlevel\n...solution is :\n$(solve(testlevel))")

For sokoban level:

#######

=={{header|Kotlin}}==

{{trans|Java}}

 

import java.util.LinkedList

println()

println(Sokoban(level).solve())

 

{{out}}

We have chosen to use a double queue (deque) instead of a linked list.

 

 

type

echo Level.join("\n")

echo()

 

{{out}}

{{trans|Python}}

This uses a breadth-first move search, so will find a move-optimal solution.

type move_t = Move of dir | Push of dir

 

"#.# @#";

"#######"] in

Output:

<pre>luULLulDDurrrddlULrruLLrrUruLLLulD</pre>

would still be a valid solution. I could fix it, but at the cost of speed and memory.

 

use strict;

use warnings qw(FATAL all);

}

__END__

{{out}}

<pre>Solution found!

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.

integer w, h -- (set from parsing the input grid)

sequence moves -- "", as +/-w and +/-1 (udlr)

printf(1,"solution of %d pushes (%s)\n",{pop,elapsed(time()-t0)})

plays(level,pushset)

{{out}}

Note that a full solution in LURD format would show as 48 moves, as opposed to

 

Other tests:

#############

# # #

#....... #

#############

{{out}}

<pre>

</pre>

Test #3

####

##. ##

###### ##

####

{{out}}

<pre>

</pre>

Test #4

#############

#... # #

#... #

#############

{{out}}

<pre>

</pre>

Test #5

#####

# #

# #########

#######

{{out}}

<pre>

=={{header|PicoLisp}}==

This searches for a solution, without trying for the push-optimal one. The player moves between the pushes, however, are minimized.

 

# Display board

(pushes) )

(display) # Display solution

Test:

(quote

"#######"

"#######" ) )

(prinl)

Output:

<pre> 8 # # # # # # #

{{works with|Psyco}}

{{works with|Python 2.6}}

from collections import deque

import psyco

psyco.full()

init(level)

Output:

<pre>#######

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.

 

#lang racket

(require data/heap

(pushes s clear))

(bfs)])))

 

{{out}}

(formerly Perl 6)

{{trans|Go}}

my $level = q:to//;

#######

}

return "No solution";

{{out}}

<pre>Level:

 

=={{header|Ring}}==

#--------------------------------------------------#

# Sokoban Game #

UpdateGameMap(oGame)

lPlayerWin = False

 

Output image:

===Simple Version===

{{trans|Python}}

 

class Sokoban

"No solution"

end

'''Test:'''

#######

# #

#######

EOS

 

{{out}}

When a box is pushed there, it doesn't process after that.

 

def initialize(level)

board = level.lines.map(&:rstrip)

"No solution"

end

Runtime: about 0.20 seconds.

 

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 -->

 

proc solveSokoban b {

}

error "no solution"

Demonstration code:

"#######"

"# #"

"#######"

}

Output: <pre>ulULLulDDurrrddlULrruLLrrUruLLLulD</pre>

Runtime with stock Tcl 8.5 installation: ≅2.2 seconds<!-- on what is now a fairly old machine -->

{{libheader|Wren-set}}

This works but at a rather sedate pace - 26.7 seconds.

 

var Board = Tuple.create("Board", ["cur", "sol", "x", "y"])

System.print(level.join("\n"))

System.print()

 

{{out}}