Солверы для игры Сокобан. Конкурс.

[lepetrandr]

2193, 3575

[svb]

Не понял...
10_40i

(Оффтоп)

#######
##  ###
## *@##
##   ##
##** ##
## **##
##   ##
##*  ##
##  *##
##* * #
#     #
# * # #
##    #
#######

dllDurrdDuulldRDrUdlDlUrdDrUdlDDDrrddlllUluRddrrruuuLUllDDRUrrdddllUUluRdlldRdrrruuLLulDrrruLdlluuUrurDDDLUrdrdddllUUlldRdrrruuulullDDrUrrdddllUUlldRdrrruuuluuululDDDRUdlDDrUrrdddllUUluRdlldRdrrruuLLulDrrruLdlluuurrDDLUrdrdddllUUlldRdrrruuulullDDrUrrdddllUUluRdlldRdrrruuLLulDrrruLdlluuuuururDDDLUrdDDLUrdrdddllUUlldRdrrruuulullDDrUrrdddllUUlldRdrrruuuluuullDDRUdlDDrUrrdddllUUluRdlldRdrrruuLLulDrrruLdlluuurrDDLUrdrdddllUUlldRdrrruuulullDDrUrrdddllUUlldRdrrruuuluuuuululuurDrDulldDrUdlDDRUdlDDRUdlDDrUrrdddllUUluRdlldRdrrruuLLulDrrruLdlluuurrDDLUluuurrDDLUluuurrDulldddrddlUrddrrdddllUUlURuulDrddddrruuLrddlluUUUluUrrdLulU

-- Пн июл 13, 2015 11:49:00 --

Дошло

[lepetrandr]

Да, там сокобан слегка организаторские правила нарушил :) И кстати этот уровень я тоже уже улучшил. Кажется, автор контеста обещал продолжение банкета уже скоро...

[svb]

Совсем недавно, в 1750 году, Эйлер в письме Гольдбаху сообщил о своей знаменитой формуле $N-E+F=2$. Строгое доказательство этой формулы нашел 20-летний Коши в 1813 году. Пуанкаре обобщил формулу в 1893 году. Про "недавно" это не шутка. Кому то и 3 месяца кажется много, но многие задачи тысячелетиями ждали своего решения.

Гипотеза Эйлера о том, что не существует ортогональных латинских квадратов $N \times N$ при $N \ne 2(\bmod 4)$ была опровергнута только в 1959 году, но получение конкретных решений подобных проблем не под силу современным компьютерам.

Что же привлекало Эйлера в задачах, которые сейчас относят к комбинаторике? Он даже к математике эти задачи не относил.

Глядя на игру Сокобан, что вы видите? Забавную игрушку? Но ведь она в этом смысле не отличается от Кёнигсбергских мостов.

Гаусс в предисловии к своей работе "Арифметические исследования" употребляет следующие слова:
"... я случайно наткнулся на изумительную арифметическую истину... прелесть этих исследований настолько увлекла меня, что я уже не мог их оставить..."

...

[svb]

Hello all.

The site has now been re-opened to submit your new/better record  levels (Serge, Peter, are you there ?)

The official competition is over, however, you can submit levels just for fun, or try
and improve on  the current podium records.

So Basically what happens when you submit a level now, is that it does not enter any database
(including also regrettably My Raw Scores) Except a new database, that is called 'Current Records'

This is currently identical to the Final competition Podium, but will be updated when
and if any improvement on it is submitted  (And then your  newly submitted level, and its
full shortest solution will be shown)

Please tell me if you have any questions/requests about this .....

[svb]

Wes Sampson улучшил базовую область серии 4_L.

###############
#   ####  #####
#         #####
## #####  #####
## ##### ######
## #....  #   #
## ######$ $  #
## ### @# #$  #
## ### $    ###
## ###  #######
#  #### #######
#        ######
#  ###   ######
###############

Пример

[dimkadimon]

Отличные улучшения рекордов, так держать! Да сокобан интересная игрушка.

Почему то для B>=9 мы переходим в узор fibonacci и его варианты. Я не уверен что он оптимален. А что если для B>=9 использовать круговой узор который мы видим в B=5 и 6? Или нам просто не хватает места? Еще подозреваю что с улучшением обычных уровней можно еще улучшить несколько циклических.

[svb]

Немного изменил базовую область серии 3_L

##############
#######   #  #
#######      #
#####  # ##  #
####   #  # ##
##  $ $@  # ##
##    ##  # ##
###$####### ##
#   ####### ##
#  #  ##### ##
#  #         #
##.#  ####   #
# .## ########
#      #######
#. #   #######
##############

Соответственно все рекорды серии увеличились. Основой послужила базовая область Wes Sampson, чтобы выиграть всего одну клетку изменил соединение двух важных частей базовой области.
Для подсчета Score стал использовать найденную в интернете программу JSoko.

Для нахождения базовых областей вполне возможно использовать программы перебора - области не такие уж большие. Пока найдены такие области только для для $B<5$. Было бы интересно для продолжения найти хотя бы одну базовую область для $B=5$. Сейчас даже непонятно, существует ли такая.

Определение. Назовем базовой областью такую часть уровня игры, которая обладает следующими свойствами:
1. Все начальные и конечные позиции уровня принадлежат этой области.
2. Базовую область можно "замыкать" с помощью простой цепочки, состоящей из прямолинейных участков и простейших узлов.
3. Количество прохождения ящика по замыкающей цепочке равно B

Пока открыт вопрос о том, что количество прохождений ящика по замыкающей цепочке не может превышать B. Это чисто теоретическая проблема.

-- Вт июл 21, 2015 21:05:16 --

:!:
Посмотрел на работу уровней 3_L. Оказалось сложнее, чем мне казалось. Впервые увидел обратный ход ящика по замыкающей цепочке. Прямых проталкивания ящика -3 и дополнительно проталкивание одного ящика вперед-назад. Это должно повлиять на подсчет числа узлов для максимального Score.

[svb]

dimkadimon, выскажусь по поводу вашего разговора с Gil Dogon в группе SLDC-discussion о новых результатах после окончания конкурса. Я тоже случайно отправил какое-то решение, мне нужно было узнать Score, и, о ужас, вижу себя на втором месте.

После того, как стали известны решения-победители, не имеет смысла регистрировать решения ниже рекордных! Их же очень легко получить.

Мне, честно говоря, не очень удобно и за свою мелкую доводку имеющихся решений. Я об этом старался писать здесь с обязательной ссылкой на авторов уровней, которые я использовал. Но и слишком щепетильное отношение к приоритетам иногда выглядит излишним - люди все понимают .

[dimkadimon]

svb я с вами во всем согласен. Gil добавил проверку которую мы хотели и теперь нельзя случайно получить рекорд отправив чужое решение. Это хорошо.

У меня получилось немного улучшить циклические решения Алексея с двумя коробками. Приятно.

Кстати кто нибудь может объяснить замурованые комнаты Tom Sirgedas для обычных уровней 2_400 и 2_800?!? Выглядит как ошибка copy+paste. Значит можно улучшить!

[svb]

dimkadimon в сообщении #1039698 писал(а):

Кстати кто нибудь может объяснить замурованые комнаты Tom Sirgedas для обычных уровней 2_400 и 2_800?!? Выглядит как ошибка copy+paste. Значит можно улучшить!

Область, в которой "замурованные" комнаты, нерабочая и солверы такие области не замечают. Обычно рассматривается только связная область, в которой находится сокобан (грузчик). L считается только для этой связной области.

[dimkadimon]

svb в сообщении #1039699 писал(а):

Область, в которой "замурованные" комнаты, нерабочая и солверы такие области не замечают. Обычно рассматривается только связная область, в которой находится сокобан (грузчик). L считается только для этой связной области.

Проверил на сайте, вы правы - если эти пустые клетки заполнить то L не меняется.

[dimkadimon]

Петр классные новые решения! Особенно понравились мордочки - это верх искусства!

[svb]

По поводу критики Brian циклических уровней. Привязка к обычным правилам Сокобана проста и ценность находок конкурса для обычных любителей игры не уменьшается. Вот как выглядит находка Петра для этих любителей:

#######
##  ###
##$+ ##
## * ##
##   ##
## **##
## * ##
##   ##
##** ##
## *  #
#     #
#  ** #
##  ###
#######

[dimkadimon]

svb согласен, критика циклических уровней мне показалась слабой. Почему бы им не попробовать новые правила? Правильно вы отметили что эти уровни можно превратить в обычные. Написал свое мнение на форуме, надеюсь Brian поймет.