29.07.2009
СОКОБАН
МЕНЮ
Начало
Краткий обзор 1
Краткий обзор 2
Краткий обзор 3
Краткий обзор 4
Краткий обзор 5
Краткий обзор 6
Солверы и генераторы 1
Солверы и генераторы 2
Алгоритмы

КОНКУРС

-------------‹ rbox - a SOKOBAN solver and problem generator ›---------------
Copyright c 2001 Andreas Stabel

Это был, пожалуй, первый солвер, с которым я познакомился. Правда, к этому времени у меня уже был собственный, но именно поэтому он меня заинтересовал. Работает программа под Windows 95/98/NT/2000 в режиме консоли. Ниже приведены некоторые цитаты из файла RBOX.DOC, который идет вместе с программой. Для запуска необходимо набрать строку:
rbox ‹input file› [‹option›]

В качестве параметра нужен текстовый файл с уровнем, например:
###########
#  #  #  @#
#   .*$ # #
#  ##     #
#     #####
###########


Можно использовать следующие опции:
   -b: Print the board after reading it
   -c : Compare with board in 
   -d: Print board and quit
   -f : Give file with 64-bit random values
   -h: Output all hash size info
   -i : Seed random function with hex value 
   -l : Set bucket size to 
   -m: Solve with a minimum of moves
   -p : Backsolve solved board to find boards with a maximum number of
              pushes from the given board. Save the boards to nnnn
   -q: Don't output progress
   -s : Try to solve the puzzle starting with ply 
      For option -p, give start level for saving boards
   -t: Don't output time used
   -v: Verbose
   -x : Set number of bits used for hash index to 

-b will cause the screen to be output after it has been read from the file
   and normalized (unused floors removed and redundant edges removed)
-c  will compare the normalized version of the screen in  with
   the normalized version of the screen given as an ordinary parameter.
   The comparison is done also with rotated and mirrored version of the boards
   and with boards where the Sokoban man has moved with pushing balls.
-d Will just print the board. This is useful for extracting and normalizing
   boards f.ex. from a .dat file.
-f  is just for testing of the hash function.
-h will give you a lot more information of the hash arrays allocated. This may
   be useful if you try to tune the program to solve a problem most efficiently
   on your computer.
-i  is used only to try to see if the program behaves differently with
   other hash values.
-l  is important if you have a Sokoban problem that the program has
   difficulties to solve or when you use the -p option to get the program to
   generate maps. The amount of memory allocated for the hash tables
   is equal to 2^ *  so redushing the hashbits by one
   and doubling the bucket size will cause the same amount of memory to be
   allocated, but the doubling of the bucket size will cause the program to
   use the hash table more efficiently, but will also slow down the program.
   The default value is 4 which will give you good speed, but not a very
   optimal use of the hash table.
-m solve the problem with a minimum of moves, not with a minimum of pushes
   which is the default.
-p This option is used to create your own maps. See chapter below.
-q Don't output the running counters, this is useful if you redirect the
   output of the program to a file.
-s  The program will usually try to solve the problem by doing only one
   push (or move), then with two pushes (moves) and so on. It is possible to
   get the program to start searching for a solution with  pushes (moves)
   at once. You may then miss the shortest solution. This option works with
   the default to solve in a minimum of pushes and with option -m.
   If this option is used together with thw -p option to generate maps, it
   will cause all maps found which needs  pushes or more to be output to
   files.
-t will skip the output of time used
-v will cause a lot of extra information to be output
-x  is use to increase (or decrease) the amount of memory used by the
   hash tables. The default value is 19.
С помощью оптии -p можно создавать собственные уровни:
Chapter 3 - Creating your own maps - option 'p':
You can create possibly very difficult maps only by specifying the solution
by using the -p option of the program. An example:
You make a solved map an put it into a file bsol.txt=
##############
###########  #
#   # @ #    #
#   #        #
#   ##*### ###
## ###*###  ##
#  **   ##  ##
#   # # ##   #
#   #   **   #
##############
(Note that all balls are on their goals)
Then you run the program with the following command:
rbox -p bsol bsol.txt -x21

The output of the program looks like this:
>  The hash table can store 8388608 positions, allocating 64 Mbytes for it !
>  An upper bound for the number of possible box configurations are 1344904 !
>  An upper bound for the number of possible configurations are 72624816 !
>  
>    Time used (Time diff) Pulls  Nodes      Inhash    Reused
>       66.832      1.594  89     21857132   229348    0
>  A maximum of 88 pushes can be done from the initial position giving 1 positions !
>  Clearing last level hash entries !
>  Cleared 1 entries !
>  Researching:
>  Saved 1 boards which can be reached with 88 pushes or more !
>  Clock: 70379, Time used: 1:10.379

The program found that the maximum number of box pushes to reach this
solutions is 88 for any possible configuration of the boxes and it has saved
this map into the file bsol0000.out=
##############
###########  #
#   #   #  $ #
#   #    $   #
#   ##.### ###
##$###.###$ ##
#  ..   ##@ ##
#   # #$##   #
#   # $ ..   #
##############

You may now check that this map really needs 88 pushes to solve by typing:
rbox -x 21 bsol0000.out

BOXSEARCH v.5.0
Author: Ge Yong

Один из лучших в настоящее время солверов. Интерфейс несколько специфический, но, в конце концов, для солверов это не главное. Имеется новая версия BOXSEARCH v.5.1 beta2 от 14 янв. 2007 г. Этот солвер решает и большинство стандартных уровней, но некоторые уровни, которые решает солвер Takaken -а, ему не поддаются. Имеется режим оптимизации решений, которого нет у Takaken-а. Оба солвера, и Takaken-а и Yong-а, очень шустрые.

Сравнение различных солверов я провел на уровне svb485
Программа step/box time
RBOX.EXE 846/160 3 m 58 s
SVB_SOLVER.EXE 666/160 5.27 s
BOXSEARCH.EXE 5.1 b2
Best push with best move
648/160 16.44 s
TakakenSolver.exe 7.2 1044/280 8 s
SVB485
 ####        
##  #########
#  $@$ ##   #
#  #...     #
## ##*#### ##
#  #   $ #  #
#   .* #    #
#  ### ###  #
##    $ #####
 ####   #    
    #####    


К сожалению мой солвер не предназначен для решения больших уровней, уже на стандартном наборе от Thinking Rabbit Inc. он спотыкается - есть над чем поработать :-)

MYSOL20
Author: Adolfo Ovalle

Как пишет чилийский автор Adolfo Ovalle (Santiago, Chile), этот солвер написан на основе алгоритма Takaken:
This program is only an improvement, as for the number of 'moves', of the published by Paul Voyer, based on the algorithm of the Japanese Takaken.
Программа лежит на сайте Paul Voyer, там же имеется программа MySol312. Тестирование этих программ на уровне svb485 дало следующие результаты:

Программа step/box time
MYSOL20 728/160 11.08 s
MYSOL312 648/160 31.05 s


Сайт управляется системой uCoz