Игра

← →
STANT (2002-10-16 17:22) [0]

Подскажите алгоритм автоматической расстановки для игры "15". Или хотя бы URL. Через поисковики ничего внятного не нашел.

← →
MBo (2002-10-16 17:27) [1]

Что имеется в виду под расстановкой? Случайная?
Создай список или массив 1..15
Выбирай для каждого места число из случайной позиции списка и удаляй его оттуда.

← →
STANT (2002-10-16 17:30) [2]

>Что имеется в виду под расстановкой? Случайная?
Нет. Я имею ввиду приведение случайной расстановки к целевой (т.е. 1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 ) по правилам игры.

← →
MBo (2002-10-16 17:37) [3]

кажется, там есть
http://delphigfx.mastak.ru/

← →
STANT (2002-10-16 17:58) [4]

Я там уже смотрел. Там про пятнашки только одно предложение:
" Это зачастую используется для решения множества проблем, включая "пятнашки" и кубик Рубика, где состоянием является сочетание цифр или кубиков, и соседние состояния (или смежные узлы) посещаются путем перемещения цифр или поворота граней кубика. "
И все...

← →
Anatoly Podgoretsky (2002-10-16 18:02) [5]

Это очень ценное замечание, если ты еще ранее сомневался, то теперь ты точно знаешь что это пригодно для решения, включая " пятнашки"

← →
handra (2002-10-17 11:05) [6]

Журнал "Программист" http://www.programme.ru , там была серия статей об алгоритмах решения задач, возможно пятнашки там присутствуют.

← →
Dm9 (2002-10-17 18:13) [7]

>Подскажите алгоритм автоматической расстановки для игры "15"
Напиши игру, поиграй в неё - и поймёшь алгоритм.
Кстати, по-моему, не каждая начальная расстановка приводится к
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15...
Но, может, я ошибаюсь.

← →
Ketmar (2002-10-17 20:17) [8]

не ошибаетесь. поменяйте местами 13 и 14. а потом попробуйте. фиг сведется %-)

Satanas Nobiscum! 17-Oct-XXXVII A.S.

← →
Evgeny (2002-10-19 13:35) [9]

www.codemanual толи com, толи net
На этом сайте точно есть исходники пятнашек, правда на C, зато именно с алгоритмом решения расстановок. Перевести на Pascal, я думаю проблем не составит.

← →
Gandalf (2002-10-19 18:57) [10]

>Кстати, по-моему, не каждая начальная расстановка приводится к
Ты прав! Строго доказано, что все позиции в "15" сводятся к двум, одно - выигрышная, другая выиграшная, но с той разницей что "15" и "14" поменялись местами. Причем можно разанее сказать к какой из двух типов относится нынещняя ситуациа. В свое время - автор "15" (Америка - ФИО не помню, но известен в мире в области головолом-делания) предложил приз тому кто решит вариант два (1000$), т.е. покупаешь коробку в "15" за неск. баксов, а потом если смог выиграть из позиции два - то тебе приз. Причем, производитель боялся что это возможно, тогда автор сказал - что если это случится (выигрыш), то он заплатит из своего кармана. Вообщем математики "15" давно разобрали по косточкам (с шахматами все гораздо хуже), например популяризатор Перельман. Простите что увлекся, надеюсь это хоть кому-то было интересно.

← →
Inan61 (2002-10-19 22:02) [11]

Сейчас как раз делаю пятнашки. Будут вопросы - пиши.

← →
STANT (2002-11-11 14:53) [12]

>www.codemanual толи com, толи net
>На этом сайте точно есть исходники пятнашек
Почему-то поиска я там не нашел... (искать поиск... интерестная туфта :) это к слову...) и пятнашек тоже. Может уже убрали?

>Gandalf
А если автор так уверен в невозможности, то почему пообещал 1000, а не млн.? Видимо, не полностью уверен :)

>Inan61
Ну как сделал? Я попробывал сделать перебор всех вариантов. Ряботает. Только, если для выгрыша требуется больше 16-19 ходов, то обдумывание компьютера может затянутся на долгие годы... :)

А все-таки странно, почему так трудно найти алгоритм. Мне сказали что это классическая задача, даже математическая...

← →
Gandalf (2002-11-11 15:25) [13]

> А все-таки странно, почему так трудно найти алгоритм. Мне
> сказали что это классическая задача, даже математическая...

Задача классическая, а кто сказал, что решение классическое, вообще так на вскидку чем-то близко алгоритму поиска пути - тот что A*.

← →
mukha (2002-11-12 08:06) [14]

Отправил пятнашки по почте. Смотри.

← →
pasha676 (2002-11-12 09:08) [15]

2STANT

>>А если автор так уверен в невозможности, то почему пообещал
>>1000, а не млн.? Видимо, не полностью уверен :)

1. По тем временам 1000 $ - сумма весьма не маленькая.
2. Если б он назначил миллион, то народ не повелся бы. Сразу поняли, чт дело фуфло. Он же сделал гениальный маркетинговый ход: "первые два человека получат по 1000$". Что автоматически подразумевает, что решение очень возможно (первые ДВА человека) и тебе дадут вполне реальные деньги. Кстати объем продаж пятнашек и их клонов наверное самый большой в мире.

← →
STANT (2002-11-12 18:03) [16]

>mukha
Посмотрел. Неплохо. Но при первой же игре попалась неразрешимая расстановка :) Баг?
И еще в следующей версии твоей программы хотелось бы увидеть демонстрацию (чтобы из случайной расстановки компьютер сам играл(и выигрывал), собственно, на эту тему у нас сейчас идет дискуссия..)

PS. Лидер там серьезный...

>pasha676
Интересно, откуда ты все это знаешь? Реферат что ли писал по этой теме?
Я представляю себе человека, который купил эти пятнашки и пытался выиграть $1000 - это как шампунь от перхоти :) До сих пор сидит мучается... математики не знает.

← →
Gandalf (2002-11-13 12:17) [17]

> Посмотрел. Неплохо. Но при первой же игре попалась неразрешимая
> расстановка :) Баг?

Раз уж речь пошла о не разрешимых комбинация, могу рассказать способ об их определении, если кому интерсно.

> >pasha676
> Интересно, откуда ты все это знаешь? Реферат что ли писал
> по этой теме?

А что pasha676 такого интересного рассказал? Пусть нам тоже расскажет?

Насчет решения комбинации. Тут две задачи:
1) решение
2) самое быстрое решение (минимум ходов)

Насчет реализации 2) - незнаю, а вот первое...
Если не рассматривать общий случай (n-мерное дискретное пространство и т.д. и т.п.), а свести все к 4х4. То очевидно, что минимальный объем в котором можно менять относительно положение фишек, это 3х2 (или 2х3). Тогда совершенно очевидно. Что сначало надо вести фишку 1 на место, потом 2,3,4,5,6,7,8,9,13 (Это возможно всегда!). А потом крутить оставшиюся шестерку. Причем движение фишки по полю можно осуществить по нехитрому алгоритму.

← →
pasha676 (2002-11-14 13:51) [18]

2STANT
В каком то журнале советских времен (не то "наука и жизнь", не то "техника-молодежи") была статья о пятнашках и ее авторе. Почему то запомнилась. Кстати математическое доказательство того, что некоторые позиции в пятнашка в принцепе не разрешимы появилось гораздо позже начала продаж игры. Так что народ с энтузазизмом ее покупал и действительно пытался решить комбинации в надежде на штуку баксов. Ко времени, когда до того-то доперло, что это в принцыпе матеметически невозможно - была продана солидная партия и издатель и автор бабки получили. И куда больше 1000$.

2Gandalf
Рассказывать нечего - ты и сам все знаешь :).
Вопрос идет не об алгоритмах решения (тут как раз боле-менее все ясно), а об алгоритмах начальных расстановок фишек так чтоб не попасть в ситуацию неразрешимости игры. Имхо - самый поверхностный алгоритм - ставим все в нормальную позицию, в случайном порядке смещаем "дырку". Через n - итераций получим растановку имеющее решение и переставленную достаточно хаотично.
Число n подбирается эмпирическим путем :).

← →
Evgeny (2002-11-16 13:06) [19]

>STANT © (11.11.02 14:53)
>www.codemanual толи com, толи net
>На этом сайте точно есть исходники пятнашек
Почему-то поиска я там не нашел... (искать поиск... интерестная туфта :) это к слову...) и пятнашек тоже. Может уже убрали?

http://www.codemanual.net/windows/samples/r15src.zip

Кстати алгоритм в этом примере очень быстрый.

Игра Найти похожие ветки