Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Писал ли кто-нить когда-нить программу решения сапера?

SergP © (2006-11-16 21:26:00)
Имеется ввиду виндовская игра "Сапер". Интересует алгоритм нахождения свободной клетки по имеющейся ситуации.

PHPDeveloper (2006-11-19 16:54:00) [1]
Помню, была такая олимпиадная задача. Поищите, может найдете на подобных сайтах(олимпиадных)

SergP (2006-11-18 18:22:00) [2]
> [9] Asteroid © (18.11.06 16:15)
> Где-то валялась программа, которая читала окно сапера, опознавала
> цифирьку и расставляла мины. При хороших обстоятельствах
> за три секунды эксперта решала. Кажется даже были исходники,
> но фиг знает где :)

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

Asteroid (2006-11-18 16:15:00) [3]
Где-то валялась программа, которая читала окно сапера, опознавала цифирьку и расставляла мины. При хороших обстоятельствах за три секунды эксперта решала. Кажется даже были исходники, но фиг знает где :)

SergP (2006-11-17 19:24:00) [4]
> [5] megabyte-ceercop © (17.11.06 13:49)
> Алгоритм простой, но можно сделать еще проще - читать из
> памяти расположение мин и тыкать только те клетки где мин
> нет :)

Шутку юмора я понял...
Но если нельзя прочесть расположение мин? т.е. например есть удаленный сервер, где расположение мин взять нельзя. Только играть с ним можно...

> [6] chemodan (17.11.06 14:19)
> хехе, ну тады можно сделать так:
> 1) Если количество мин по полученным от миноискателя данным,
> совпадает с количеством соседних квадратов, помеченных
> как содержащие мину, то соседние неразведанные квадраты
> помечаются как чистые.

Это понятно. До этого я и сам додумался...

> 2)Если количество мин по полученным от миноискателя данным,
> совпадает с количеством соседних квадратов, помеченных
> как содержащие мину или как неразведанные, то соседние неразведанные
> квадраты помечаются как содержащие мину.

Аналогично...

> 3)Если произошла какая-то пометка неразведанных квадратов,
> то процесс повторяется для каждого квадрата с самого начала.
> Это кусок из условия задачи, представленной для решения
> участниками четвертьфинала по Восточно-Сибирскому округу
> Чемпионата мира по программированию ACM. =)

Насчет этого я не понял...
Но есть пока такая идея:

Ищется ряд смежных разведанных клеток без мин (ограниченное число). Находятся все неразведанные клетки соседние с вышенайденными.(например до 16 штук).
Кодируются в word (16 бит) (наличие мины в каждой клетке соответствует 1 в одном из разрядов)
Перебираются все возможные варианты расположения мин. (которые не подходят - отбрасываются нафиг).
Все найденые варианты ORятся и ANDятся...
Если в результате OR в каком-то разряде есть 0 то значит там мины нет 100% и можно проверять эту клетку...
И если в результате AND в каком-то разряде есть 1, значит там 100% находится мина...

SergP. (2006-11-17 19:03:00) [5]

> chemodan (17.11.06 14:19) [6]

Это простейший алгоритм, до такаго я и сам уже давно додумался, и даже придумал белее эффективный...(но пока не реализовал) Но хотелось бы знать до чего "человечество" дошло на данный момент...

chemodan (2006-11-17 14:19:00) [6]
хехе, ну тады можно сделать так:
1) Если количество мин по полученным от миноискателя данным, совпадает с количеством соседних квадратов, помеченных как содержащие мину, то соседние неразведанные квадраты помечаются как чистые.
2)Если количество мин по полученным от миноискателя данным, совпадает с количеством соседних квадратов, помеченных как содержащие мину или как неразведанные, то соседние неразведанные квадраты помечаются как содержащие мину.
3)Если произошла какая-то пометка неразведанных квадратов, то процесс повторяется для каждого квадрата с самого начала.
Это кусок из условия задачи, представленной для решения участниками четвертьфинала по Восточно-Сибирскому округу Чемпионата мира по программированию ACM. =)

megabyte-ceercop (2006-11-17 13:49:00) [7]
Алгоритм простой, но можно сделать еще проще - читать из памяти расположение мин и тыкать только те клетки где мин нет :)

SergP (2006-11-17 09:55:00) [8]
> [3] chemodan (17.11.06 05:39)
> да-да, задача из класса NP! Решишь, и получишь миллион долларов
> и еще несколько миллиардов в придачу =)

Да Вы меня не совсем поняли. То что задача нерешаема - это понятно.Т.е. скажем так - алгоритма 100% решения не существует. Но мне интересен алгоритм который бы наиболее ближе был к идеальному. Т.е. хочу создать вариант с автоматическим решением, но в определенные моменты, когда алгоритм не может вычислить очередной ход, тогда уже человек принимает решение какой ход сделать.

ЗЫ Мне не для получения этих нескольких миллиардов... :-)

chemodan (2006-11-17 05:39:00) [9]
да-да, задача из класса NP! Решишь, и получишь миллион долларов и еще несколько миллиардов в придачу =)

Тыт (2006-11-17 02:17:00) [10]
Элементарно. Но игра в принципе не решаемая. Так, что бесполезно.

SergP (2006-11-16 21:27:00) [11]
Вот черт. Хотел в прочее запостить... Ладно. Может модератор перенесет...

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »