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

← →
SergP © (2006-11-16 21:26) [0]

Имеется ввиду виндовская игра "Сапер". Интересует алгоритм нахождения свободной клетки по имеющейся ситуации.

← →
SergP © (2006-11-16 21:27) [1]

Вот черт. Хотел в прочее запостить... Ладно. Может модератор перенесет...

← →
Тыт (2006-11-17 02:17) [2]

Элементарно. Но игра в принципе не решаемая. Так, что бесполезно.

← →
chemodan (2006-11-17 05:39) [3]

да-да, задача из класса NP! Решишь, и получишь миллион долларов и еще несколько миллиардов в придачу =)

← →
SergP © (2006-11-17 09:55) [4]

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

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

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

← →
megabyte-ceercop © (2006-11-17 13:49) [5]

Алгоритм простой, но можно сделать еще проще - читать из памяти расположение мин и тыкать только те клетки где мин нет :)

← →
chemodan (2006-11-17 14:19) [6]

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

← →
SergP. (2006-11-17 19:03) [7]

> chemodan (17.11.06 14:19) [6]

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

← →
SergP © (2006-11-17 19:24) [8]

> [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% находится мина...

Где-то валялась программа, которая читала окно сапера, опознавала цифирьку и расставляла мины. При хороших обстоятельствах за три секунды эксперта решала. Кажется даже были исходники, но фиг знает где :)

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

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

← →
PHPDeveloper (2006-11-19 16:54) [11]

Помню, была такая олимпиадная задача. Поищите, может найдете на подобных сайтах(олимпиадных)

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