powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм расстановки мин в "Сапер"е?
52 сообщений из 52, показаны все 3 страниц
Алгоритм расстановки мин в "Сапер"е?
    #34300422
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
В игре "Сапер", которая с виндой идет. Или случайно?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300556
Den_di
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
На случайно совсем непохоже. Точнее на равномерное. Тут какое-то распределение, при котором они кучнуются по 2-3. Реже по 1. Если рядом,то и до 6+. Тут что-то вроде вероятность поставить на линию зависит от наличия на ней других значений. Вроде как части равномерно, а другие расписывают под них. Притом почти все расклады имеют решение. Значит есть какая-то априорная зависимость, участвующая в генерации. Не всё так просто.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300581
Фотография ScareCrow
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
тыб хоть смайлики поставил


Posted via ActualForum NNTP Server 1.3
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300640
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Den_diНа случайно совсем непохоже. Точнее на равномерное. Тут какое-то распределение, при котором они кучнуются по 2-3. Реже по 1. Если рядом,то и до 6+. Тут что-то вроде вероятность поставить на линию зависит от наличия на ней других значений. Вроде как части равномерно, а другие расписывают под них. Притом почти все расклады имеют решение. Значит есть какая-то априорная зависимость, участвующая в генерации. Не всё так просто.
Ух, как все сложно!
В игре есть такая фишка - "Особые", где можно задать размеры поля и количество мин. Допустим, в "Новичке" размер 9 * 9. Если поставить количество мин, например, 100, то будет ограничено до 64. При этом расклад не будет иметь решения, т.е. до части мин просто не добраться! Т.е. по ходу нормального алгоритма там нет: есть ограничение на количество мин в зависимости от размеров поля, и эти мины, возможно, просто "раскидываются" случайным образом.

ScareCrowтыб хоть смайлики поставил
Зачем? :) То есть вы тоже думаете, что расстановка случайная?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300834
SnowMan2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Он их раставляет после первого хода. Первый ход никогда на мину не попадает.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300843
^ozzy^
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300858
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SnowMan2Он их раставляет после первого хода. Первый ход никогда на мину не попадает
а точно, как-то и не думал об этом :)

^ozzy^]В тему winmine
спасибо, почитаю!
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300948
Фотография SeaGate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SnowMan2Он их раставляет после первого хода. Первый ход никогда на мину не попадает.
Не верно, я попадал
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34300975
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SeaGateНе верно, я попадал
Поставил поле 9 * 9, 64 мины - с первого раза никак не смог попасть :)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34301023
Фотография SeaGate
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
winmine SeaGateНе верно, я попадал
Поставил поле 9 * 9, 64 мины - с первого раза никак не смог попасть :)
О, точно, проверил - не прав - беру слова обратно ,
давно не запускал "Сапера", что-то с чем-то перепутал явно...
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34301938
kolobok0
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SnowMan2Он их раставляет после первого хода. Первый ход никогда на мину не попадает.

БРЯХНЯ...
замечательно мона попасть... Хотя давно не играл - возможно в последних форточках и подправили (типа висты, или хрюши)...

с уважением
(круглый)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34302011
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
winmineВ игре "Сапер", которая с виндой идет. Или случайно?
Хорошая задача. Когда я читал курсы по программированию, первым заданием был именно "Сапер". В частности, люди часто резались именно на этом алгоритме; типичные ошибки

Алгоритм мог засандалить несколько мин в одну клетку

Алгоритм раскидывал мины неравномерно и мог поставить меньше мин, чем требовалось.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34302135
SnowMan2
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kolobok0БРЯХНЯ...
замечательно мона попасть... Хотя давно не играл - возможно в последних форточках и подправили (типа висты, или хрюши)...

Сначала попади, потом пиши.

Во всех форточках одинаково.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34302423
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
kolobok0БРЯХНЯ...
замечательно мона попасть
Как ни пытался, с первого раза не попасть

softwarerАлгоритм мог засандалить несколько мин в одну клетку
Алгоритм раскидывал мины неравномерно и мог поставить меньше мин, чем требовалось
Странно, а вроде ничего сложного..
Пусть X, Y - размеры поля, С - количество мин.
Делаем X = random, Y = random. Ставим мину в клетке (X, Y), если в ней еще нет мины, уменьшаем C на 1. В цикле while С > 0 расставляем все мины.
Другой вопрос - это оптимальность этого алгоритма
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34302633
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
кликаешь первый раз по полю, затем расстановка.

НЕ ВСЕГДА ЕСТЬ РЕШЕНИЕ.

например у углу две соседние клетки и 1 мина и никто не признается... :)

аффтопитезь: объект либо именован, либо не существует
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34302868
winmine
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aklinкликаешь первый раз по полю, затем расстановка.
Да это уже понятно

AklinНЕ ВСЕГДА ЕСТЬ РЕШЕНИЕ.

например у углу две соседние клетки и 1 мина и никто не признается... :)
А здесь уже как повезет :)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34303009
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
winmineА здесь уже как повезет :)

мне почему-то везет редко...
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34303751
Фотография eNose
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
[не активирован]
[не одобрен]
Aklin winmineА здесь уже как повезет :)

мне почему-то везет редко...
любимая игра? :)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34304174
Фотография Aklin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
eNose Aklin winmineА здесь уже как повезет :)

мне почему-то везет редко...
любимая игра? :)

часто играл раньше. втыкает... (8,51,150)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34317753
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
kolobok0БРЯХНЯ...
замечательно мона попасть... Хотя давно не играл - возможно в последних форточках и подправили (типа висты, или хрюши)...
Мой личный рекорд на профессионал - 75 секунд. Понятно что такое достигается только постоянными тренировками. Так вот -ни разу не попадал на 1м ходе на мину
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34317755
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Мне вот горздо более интересно было бы придумать прогу которая бы нажимала и правильно выводы делала куда нажимать:-)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34319138
ыыы
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SxakМне вот горздо более интересно было бы придумать прогу которая бы нажимала и правильно выводы делала куда нажимать:-)
Такие проги есть уже.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34319645
xxman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
SxakМой личный рекорд на профессионал - 75 секунд. Понятно что такое достигается только постоянными тренировками. Так вот -ни разу не попадал на 1м ходе на мину
75 - что-то с трудом верится :) Вам бы в игру как на картинке сыграть. А на 1-ом ходу чтобы не попасть - это легко делается.

ыыыТакие проги есть уже.
Где они есть?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34319901
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
xxman
75 - что-то с трудом верится :) Вам бы в игру как на картинке сыграть. А на 1-ом ходу чтобы не попасть - это легко делается.
И тем не менее 75 сек когда много играл было. Причем 1 утверждал что унего рекорд 71
Когда много играл в 80% случаях проходил быстрее 100 сек

ДА я и говорю чтобы на 1м ходу попасть на мину я росто не знаю даже как...
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34319949
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Картинку заценил. Я сейчас уде не на время играю в сапера, просто ставлю поле с плотностью мин 1 на 3 поля... такое очнеь долго проходится... А поп оаоду как повысить рекор дам пару советов
1 . Открыватьнезаминированные поля нажатием 2х кнопок мыши сразу же по возможности - тогда и соседние открываются
2. (немного конфликтует с 1 ,надо опытом найти золотую середину) как можно меньше тратить время на расстановку самих мин -только открыватьполя и поменьше метить заминированное (вариант с конечным когда число мин все решает бывает нечасто и уж по кр мере хочешь рекорд - пожертвуй этим временм и этим вариантом)
3. Пункт 1 из всех возможных применять так, чтобы открылись поля находящиеся как можео дальше от известной открытой области

Теперьнемного потренироваться втч в скорости работы мышью и рекорды пойдут...

Кстати на новичке мой рекорд еще более невероятен :-) Раз нажал так осталось только 1 или 2 неоткрытое.. в эту же секунду и ее нажал :-) получилось 1 сек (сапер сразу начинает с 1 сек, 0 у него не бывает, по кр мере так было на NT 4.0 на которой я сидел когда много в него играл)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34320874
Фотография andrey_anonymous
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Sxak xxman
75 - что-то с трудом верится :) Вам бы в игру как на картинке сыграть. А на 1-ом ходу чтобы не попасть - это легко делается.
И тем не менее 75 сек когда много играл было. Причем 1 утверждал что унего рекорд 71
Когда много играл в 80% случаях проходил быстрее 100 сек
Хе-хе... 62 - попался как-то удачный расклад ;)
Что до рекомендаций... Пометки (которые вопросик) надо сразу отключать, чтобы не мешались.
По теме. Сколько ни бился, а какойлибо внятной зависимости не обнаружил. Обычный ГПСЧ, срабатывающий после первого клика. Подозреваю, что координаты первой точки используются для инициализации генератора :)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34320935
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
andrey_anonymousХе-хе... 62 - попался как-то удачный расклад ;)
Крт, крут:-) 71 это минимум о котором я до етого слышал. Теперь такой 62:-)
andrey_anonymous
Что до рекомендаций... Пометки (которые вопросик) надо сразу отключать, чтобы не мешались.
Согласен полность.ю. Но об етом неудобно както даже писать было:-) Должно быть очевидно
andrey_anonymous
По теме. Сколько ни бился, а какойлибо внятной зависимости не обнаружил. Обычный ГПСЧ, срабатывающий после первого клика.
Тоже полностью согласен. Насчет того что там писали что они группируются кучками по 3-4 - так это пусть посчитают веротяность того, чтобы в равномерноом распределении не было таких кучек
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34343483
Юрий Р.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Никогда не достигал таких сногсшибательных результатов, как тут встречаются. Минимум 185 сек. на матрице 16 х 30. Но одно время частенько поигрывал и заметил, что первый ход не попадает в мину только в верхнем левом углу (квадрат 1:1). Клик в любом другом месте на первом ходу не гарантирует отсутствия мины.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34343768
madvet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Юрий Р.Никогда не достигал таких сногсшибательных результатов, как тут встречаются. Минимум 185 сек. на матрице 16 х 30. Но одно время частенько поигрывал и заметил, что первый ход не попадает в мину только в верхнем левом углу (квадрат 1:1). Клик в любом другом месте на первом ходу не гарантирует отсутствия мины.
Да нельзя с первого хода попасть на мину
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34343951
Фотография softwarer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Юрий Р.Но одно время частенько поигрывал и заметил, что первый ход не попадает в мину только в верхнем левом углу (квадрат 1:1). Клик в любом другом месте на первом ходу не гарантирует отсутствия мины.
Хм. Думаю, десяти минут хватит Вам для того, чтобы скачать HyperCam , запустить ее, начать сапера столько раз, сколько хватит для того, чтобы первым ходом попасть на мину, и выложить результат на любой файлообменник, например на narod.ru. В то же время для качественного монтажа времени, пожалуй, маловато, если у вас нет под рукой необходимых инструментов.

Итого, либо через десять минут после публикации мы видем avi-шку, в которой Вы первым ходом попадаете на мину, либо гипотеза о возможности этого переходит в разряд.... сомнительных.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34344175
Юрий Р.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Виноват, наверное погорячился, давно упражнялся. По-крайней мере сейчас ни разу с первого хода не "наступил". Беру свои слова обратно.

Модератор:
я порядка сотни попыток тоже сделал. кажется даже 0 не выпадало, только 1 и 2.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34344688
Фотография FasterHarder
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
I started in 1983, in 2007 i still on a case!

А я вот баг в пауке нашел. Там в правилах написано, чтобы была возможность разложить новый ряд, необходимо, чтобы все столбики были заполнены. А у меня получилось так, что я собрал столбик от короля до туза, он естесно "вышел" и у меня осталось 3 стопки (игральных), в одной 2, во второй 2 и в третьей 1 карта, всего 5 карт, а столбиков должно быть толи 8 то ли 9 не помню. И все, дальше играть не могу, так как не могу сделать новую раздачу, хотя там колоды 2 или 3 осталось. Я даже эту игру сохранил, на всякий чп, вдруг кто захочет поспорить. Вот такой баг.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34345118
xxman
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
FasterHarderI started in 1983, in 2007 i still on a case!

А я вот баг в пауке нашел. Там в правилах написано, чтобы была возможность разложить новый ряд, необходимо, чтобы все столбики были заполнены. А у меня получилось так, что я собрал столбик от короля до туза, он естесно "вышел" и у меня осталось 3 стопки (игральных), в одной 2, во второй 2 и в третьей 1 карта, всего 5 карт, а столбиков должно быть толи 8 то ли 9 не помню. И все, дальше играть не могу, так как не могу сделать новую раздачу, хотя там колоды 2 или 3 осталось. Я даже эту игру сохранил, на всякий чп, вдруг кто захочет поспорить. Вот такой баг.
Причем здесь паук, тема же про сапера?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34345290
Фотография FasterHarder
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: plaintext
I started in 1983, in 2007 i still on a case!

авторПричем здесь паук, тема же про сапера?

Ну нечем мне похвастаться про сапера :-), а вот в паучке бак есть. Да и тему новую, про всякую чушь открывать нехохота.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34345325
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
))
я в следствие ведут колобки,
в сейфе учился поворачивать точно одну ручку недели две чистого времени.
Пока понял алгоритм испотелся весь.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34351290
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingiz))
я в следствие ведут колобки,
в сейфе учился поворачивать точно одну ручку недели две чистого времени.
Пока понял алгоритм испотелся весь.
Ну щас еще и про квак начнем хвастаться:-)
Про сапера - есть нестандартные варианты сапера По кр мере в одной из них которая у меня где-то валяется можно запороться и 1м ходом.
Про колобков - увидел на работе, дома компа тогда не было, просто посидел с ручкой и бумажкой. 1 ручку там поворачиватьнеобязательнено:-0 Там надо все собрать А для етого алгоритм следующий:
Для каждой жмякалки считаешь число неправильно стоящих жмякалок на кресте из 7ми штук (то есть у всех жмякалок стоящих на одной вертикали или горизонтали) ,Если число нечетное, то жмякаешь, если четное то не жмякаешь. Не более 16ти жмяканий и из любой позиции он собирается
Просто четность неправильно стоящих жмякалок на таком кресте - инвариант при жмякании не точно на ту
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34352497
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ну, наверно. проверять лень.
чето очень зациклился на повороте именно одной ручки, и решалась тяжело. ))
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34352714
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingizну, наверно. проверять лень.
чето очень зациклился на повороте именно одной ручки, и решалась тяжело. ))Когда я тогда решал с ручкой все решилось за 1 вечер без наличия компа. Сначала заметил что если
A*a*b=B то и A*b*a=B (коммутативность операции жмякания) и что A*a*a=B (порядок любой опреации жмякания=2)
Отсюда если
A*a1*a2*a3*...*an=B то A*b1*b2*b3*...*bm=a где m<=n и b(i) - различные операции. Новая более короткая последовательность получается так: среди a(i) выбираются все различные операции и те что повторяются четное число раз просто выбрасываются а те что нечетное -от них остается только 1 опреация в b(i)
Далее замечаем что каждое жмякание меняет четность общего числа неправильно стоящих выключателей.
ДАлее в принципе несложно догадаться подбором о ппоследовательности опреаций, переворачивающих только одну фигню не трогающи остальные . Можно догадаться о 8ми группах переключателей, жмяканием на которые ето должно произойти. Условием на нечетность их числа бракуем половину, остальные внимательно смотрим и находим нужное.
Вспоминаем про вышеупомянутую теорему о том, как сделать чтобы из нужной последовательности жмяканий получить более короткую. Применяем ее. Получаем почти то что нужно. Чтобы было полное счастье несложно доказываем инвариантность функции "четность неправилньо стоящих на данном кресте" по отношению к операции "жмякание не в чентр того креста" И получаем вобще щастье + теорему о том, что с меньшим числом жмяканий чем по етому алгоритму открыть сейф невозможно.
Все ето справедлио не только к сейфу 4 на 4 но и к любому прямоугольнику у которого обе стороны четные.
Для нечетных (у которого хоть 1 сторона нечетные) (кроме 1 на 1) можно доказать что в принципе невозможно собрать когда только 1 жмякалка стоит не на месте
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34352715
Sxak
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
\Пардон опечатка
Sxak и что A*a*a=B (порядок любой опреации жмякания=2)

треба читать как A*a*a=А
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34352929
madvet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сапер был взломан ! :)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34353163
Фотография tchingiz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SxakКогда я тогда решал с ручкой все решилось за 1 вечер без наличия компа.

кстати, это штрих к пользе применения дебагерров и интерактивной работы за компом, вообще.
Даешь карандаш и бумагу в широкие массы программистов.
)))))))))))))))))))


ну, Вы доктор и загадки задается. Вы еще пару теорем из теории конечных групп не
упомянули.
))))

у меня получилось, что после прохода по кресту из 7 ручек,
поворачивается только центральная, все остальные возвращаются в первоначальное
положение
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34353608
Локшин Марк
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А в сапере есть cheat-код. Если набрать xyzzy <enter> <shift>+<enter>, то в верхнем левом углу будет загораться белая точка если мины нет и черная, если есть. Если нажать на кнопку закрытия окна мышью и удерживать ее, то остановится время (потом, чтобы не закрыть окно достаточно отжать кнопку мыши вне кнопки закрытия окна).
А еще в старых ОС (до Win98 ???) был глюк, если минимизировать/максимизировать сапера, то стартовал отсчет времени.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34364757
Kulavert
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Локшин МаркА в сапере есть cheat-код. Если набрать xyzzy <enter> <shift>+<enter>, то в верхнем левом углу будет загораться белая точка если мины нет и черная, если есть.
Не работает :(
madvetСапер был взломан ! :)
У кого-нибудь получилось?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34364786
Локшин Марк
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
KulavertНе работает :(
У меня все работает, еще с Win 3.1. Верхний левый угол экрана .
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34364913
madvet
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
KulavertУ кого-нибудь получилось?
Получилось, почему нет?
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34374416
Kulavert
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
madvetПолучилось, почему нет?
Ну уж не знаю почему... при дебаге из указанных областей памяти считываются нули, функция ошибок не возвращает... Может это только для конкретной версии Winmine.exe? У меня 5.0.2135.1 96528 байт.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34989827
tokumo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
Aklinкликаешь первый раз по полю, затем расстановка.

в winmine подругому реализованно, там уже изначально мины расставлены, а если первый раз ты тыкаешь и попадаешь на мину то она переносится в левую верхнюю ячейку, если та не занята уже миной, если занята, то правее от неё, тоже, если та незанята, и.т.д. короче она переносится в начало или лучше сказать в ближайшую к началу свободную ячейку )))
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34989988
рест
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
насколько понял из статьи , при любом алгоритме расстановки мин задача решения сапера не тривиальна и сводима к задаче на миллион P=?NP
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34996140
pizmon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Позвольте свои 5 копеек в общее дело?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
172.
173.
174.
175.
176.
177.
178.
179.
180.
181.
182.
183.
184.
185.
186.
187.
188.
189.
190.
191.
192.
193.
194.
195.
196.
197.
198.
199.
200.
201.
202.
203.
204.
205.
206.
207.
208.
209.
210.
211.
212.
213.
214.
215.
216.
217.
218.
219.
220.
221.
222.
223.
224.
225.
226.
227.
228.
229.
230.
231.
232.
233.
234.
235.
236.
237.
238.
239.
240.
241.
242.
243.
244.
245.
246.
247.
248.
249.
250.
251.
252.
253.
254.
255.
256.
257.
258.
259.
260.
261.
262.
263.
264.
265.
266.
267.
268.
269.
270.
271.
272.
273.
274.
275.
276.
277.
278.
279.
280.
281.
282.
283.
284.
285.
286.
287.
288.
289.
290.
291.
292.
293.
294.
295.
296.
297.
298.
299.
300.
301.
302.
303.
304.
305.
306.
307.
308.
309.
310.
311.
312.
313.
314.
315.
316.
317.
318.
319.
320.
321.
322.
323.
324.
325.
326.
327.
328.
329.
330.
331.
332.
333.
334.
335.
336.
337.
338.
339.
340.
341.
342.
343.
344.
345.
346.
{ *********************************************************************** }
{                                                                         }
{ Суперпрограмма автоматизирует деятельность любого секретаря.            }
{ Посвящается всем секретарям, которых я любил, и которых не успел.       }
{                                                                         }
{ *********************************************************************** }

program Sweeper;

uses
  Windows;

const
  cDefault = - 1 ;
  cFoundBomb = - 2 ;
  cRealBomb = - 3 ;
  cError = - 4 ;

  //отступы собственно шашечек
  cVerticalOffset =  55 ;
  cHorizontalOffset =  12 ;
  cBackOffset =  8 ;
  cCellSize =  16 ;

  //не рекомендуется ставить мало. Окно должно прорисовать СЯ, да и вообще...
  cStandardDelay =  300 ;

  //окно и приложение
  cWindowClass = 'Minesweeper';
  cExecutable = 'winmine.exe';

var
  FMainWindow: HWND =  0 ;
  FWindowInfo: TWindowInfo;
  FFieldWidth: Integer =  0 ;
  FFieldHeight: Integer =  0 ;
  FDC: HDC =  0 ;
  FBitmap: HBitmap =  0 ;
  FBitmapDC: HDC =  0 ;
  FField: array of record
    Value: ShortInt;
    VMul: Byte;
    VDiv: Byte;
  end;

procedure ClickSweeper(X, Y: Integer; RightButton: Boolean);
const
  CDownButtons: array[Boolean] of DWORD = (MOUSEEVENTF_LEFTDOWN, MOUSEEVENTF_RIGHTDOWN);
  CUpButtons: array[Boolean] of DWORD = (MOUSEEVENTF_LEFTUP, MOUSEEVENTF_RIGHTUP);
var
  LInput: TInput;
begin
  if IsWindow(FMainWindow) then
  begin
    with FWindowInfo.rcClient do
      SetCursorPos(Left + X, Top + Y);
    ZeroMemory(@LInput, SizeOf(LInput));
    LInput.Itype := INPUT_MOUSE;
    LInput.mi.dwFlags := CDownButtons[RightButton];
    SendInput( 1 , LInput, SizeOf(TInput));
    Sleep(cStandardDelay div  10 );
    LInput.mi.dwFlags := CUpButtons[RightButton];
    SendInput( 1 , LInput, SizeOf(TInput));
  end;
end;

procedure ClickSweeperCell(X, Y: Integer; RightButton: Boolean);
begin
  ClickSweeper(cHorizontalOffset + X * cCellSize + (cCellSize div  2 ),
    cVerticalOffset + Y * cCellSize + (cCellSize div  2 ), RightButton);
end;

procedure DoneSweeper;
begin
  if (FDC <>  0 ) and IsWindow(FMainWindow) then
  begin
    ReleaseDC(FMainWindow, FDC);
    FDC :=  0 ;
  end;
  if FBitmapDC <>  0  then
  begin
    DeleteDC(FBitmapDC);
    FBitmapDC :=  0 ;
  end;
  if FBitmap <>  0  then
  begin
    DeleteObject(FBitmap);
    FBitmap :=  0 ;
  end;
end;

procedure InitSweeper;
var
  LStartInfo: TStartupInfo;
  LProcessInfo: TProcessInformation;
begin
  FMainWindow := FindWindow(cWindowClass, nil);
  if FMainWindow =  0  then
  begin
    ZeroMemory(@LStartInfo, SizeOf(LStartInfo));
    LStartInfo.cb := SizeOf(LStartInfo);
    CreateProcess(nil, cExecutable, nil, nil, False,  0 , nil, nil, LStartInfo, LProcessInfo);
    Sleep(cStandardDelay);
    FMainWindow := FindWindow(cWindowClass, nil);
  end;

  Sleep(cStandardDelay);

  FDC := GetDC(FMainWindow);

  GetWindowInfo(FMainWindow, FWindowInfo);

  with FWindowInfo.rcClient do
  begin
    FBitmap := CreateCompatibleBitmap(FDC, Right - Left, Bottom - Top);
    FBitmapDC := CreateCompatibleDC(FDC);
    SelectObject(FBitmapDC, FBitmap);
    FFieldWidth := (Right - Left - cHorizontalOffset - cBackOffset) div cCellSize;
    FFieldHeight := (Bottom - Top - cVerticalOffset - cBackOffset) div cCellSize;
  end;

  SetLength(FField, FFieldWidth * FFieldHeight) ;
  
  SetWindowPos(FMainWindow, HWND_TOPMOST,  0 ,  0 ,  0 ,  0 , SWP_NOMOVE or SWP_NOSIZE);

end;

function GameFinished: Boolean;
var
  I: Integer;
  LDefaultCount: Integer;
begin
  LDefaultCount :=  0 ;
  Result := False;
  for I :=  0  to FFieldHeight * FFieldWidth  -  1  do
  begin
    Inc(LDefaultCount, Ord(FField[I].Value = cDefault));
    Result := FField[I].Value = cRealBomb;
    if Result then
      Break;
  end;
  Result := Result or (LDefaultCount =  0 );
end;

function SweeperValue(X, Y: Integer): Integer;
begin
  if (X <  0 ) or (Y <  0 ) or (X >= FFieldWidth) or (Y >= FFieldHeight) then
    Result := cError
  else
    Result := FField[X + Y * FFieldWidth].Value;
end;

procedure SkipSweeperGreetings;
var
  LInput: TInput;
  I: Integer;
begin
  ZeroMemory(@LInput, SizeOf(LInput));
  LInput.Itype := INPUT_KEYBOARD;
  for I :=  1  to  2  do
  begin
    LInput.ki.wVk := VK_ESCAPE;
    LInput.ki.dwFlags :=  0 ;
    SendInput( 1 , LInput, SizeOf(TInput));
    LInput.ki.dwFlags := KEYEVENTF_KEYUP;
    SendInput( 1 , LInput, SizeOf(TInput));
  end;
end;

procedure ShotSweeper;
var
  I, J: Integer;
begin
  Sleep(cStandardDelay);

  with FWindowInfo.rcClient do
    BitBlt(FBitmapDC,  0 ,  0 , Right - Left, Bottom - Top, FDC,  0 ,  0 , SRCCOPY);

  //парсинг поля. Кто знает, какого цвета семерка и восьмерка - пусть возьмет с полки пирожок.
  for J :=  0  to FFieldHeight -  1  do
    for I :=  0  to FFieldWidth -  1  do
      with FField[I + J * FFieldWidth] do
    begin
      VMul :=  0 ;
      VDiv :=  1 ;
      case GetPixel(FBitmapDC, cHorizontalOffset + cCellSize * I + (cCellSize div  2 ),
        cVerticalOffset + cCellSize * J + (cCellSize div  2 )) of
          $00C0C0C0:
            case GetPixel(FBitmapDC, cHorizontalOffset + cCellSize * I +  1 ,
              cVerticalOffset + cCellSize * J +  1 ) of
               $00C0C0C0:
                 Value :=  0 ;
               else
                 Value := cDefault;
            end;
          $00FF0000:
            Value :=  1 ;
          $ 00008000 :
            Value :=  2 ;
          $000000FF:
            if GetPixel(FBitmapDC, cHorizontalOffset + cCellSize * I +  13 ,
              cVerticalOffset + cCellSize * J +  13 ) = $000000FF then
                Value := cRealBomb
            else
              Value :=  3 ;
          $ 00800000 :
            Value :=  4 ;
          $ 00000080 :
            Value :=  5 ;
          $00FFFF00:
            Value :=  6 ;
          $ 00000000 :
            if GetPixel(FBitmapDC, cHorizontalOffset + cCellSize * I +  8 ,
              cVerticalOffset + cCellSize * J +  3 ) = $000000FF then
                Value := cFoundBomb
            else if GetPixel(FBitmapDC, cHorizontalOffset + cCellSize * I +  3 ,
              cVerticalOffset + cCellSize * J +  8 ) = $ 00000000  then
                Value := cRealBomb
            else
              Value := cDefault
          else
            Value :=  0 ;
      end;
    end;
end;

procedure StartSweeperGame;
begin
  // клик в смайл, он же "чмок в розовый".
  ClickSweeper((FWindowInfo.rcClient.Right - FWindowInfo.rcClient.Left) div  2 ,
    cVerticalOffset div  2 , False);
end;

procedure SweeperMove(out X, Y: Integer; out RightButton: Boolean);
var
  I, J: Integer;
  LCurMul, LCurDiv: Integer;
  LVar: Double;

  function UpdateVariety(dX, dY : Integer): Boolean;
  begin
    if SweeperValue(dX, dY) = cDefault then
    begin
      X := dX;
      Y := dY;
      if LCurMul =  0  then
      begin
        //стопудово пустая клетка
        RightButton := False;
        Result := True;
      end
      else if LCurMul >= LCurDiv then
      begin
        //стопудово бомба
        RightButton := True;
        Result := True;
      end
      else
        with FField[dX + dY * FFieldWidth] do
        begin
          //запишем вероятности - пригодится воды напиться.
          VMul := VMul * LCurDiv + LCurMul * VDiv;
          VDiv := VDiv * LCurDiv;
          Result := False;
        end
    end
    else
      Result := False;
  end;

begin
  for J :=  0  to FFieldHeight -  1  do
    for I :=  0  to FFieldWidth -  1  do
      if SweeperValue(I, J) >  0  then
      begin
        LCurMul := SweeperValue(I, J) -
          Ord(SweeperValue(I -  1 , J -  1 ) = cFoundBomb) -
          Ord(SweeperValue(I -  1 , J) = cFoundBomb) -
          Ord(SweeperValue(I -  1 , J +  1 ) = cFoundBomb) -
          Ord(SweeperValue(I, J -  1 ) = cFoundBomb) -
          Ord(SweeperValue(I, J +  1 ) = cFoundBomb) -
          Ord(SweeperValue(I +  1 , J -  1 ) = cFoundBomb) -
          Ord(SweeperValue(I +  1 , J) = cFoundBomb) -
          Ord(SweeperValue(I +  1 , J +  1 ) = cFoundBomb);

        LCurDiv :=
          Ord(SweeperValue(I -  1 , J -  1 ) = cDefault) +
          Ord(SweeperValue(I -  1 , J) = cDefault) +
          Ord(SweeperValue(I -  1 , J +  1 ) = cDefault) +
          Ord(SweeperValue(I, J -  1 ) = cDefault) +
          Ord(SweeperValue(I, J +  1 ) = cDefault) +
          Ord(SweeperValue(I +  1 , J -  1 ) = cDefault) +
          Ord(SweeperValue(I +  1 , J) = cDefault) +
          Ord(SweeperValue(I +  1 , J +  1 ) = cDefault);

        if UpdateVariety(I -  1 , J -  1 ) or
          UpdateVariety(I -  1 , J) or
          UpdateVariety(I -  1 , J +  1 ) or
          UpdateVariety(I, J -  1 ) or
          UpdateVariety(I, J +  1 ) or
          UpdateVariety(I +  1 , J -  1 ) or
          UpdateVariety(I +  1 , J) or
          UpdateVariety(I +  1 , J +  1 ) then
            // всё точно!
            Exit;
      end;

  //точно ничего не ясно. Значить, берем с минимальной вероятностью. Метод тыка.
  LVar := MaxInt;
  RightButton := False;

  for I :=  0  to FFieldWidth * FFieldHeight -  1  do
    with FField[I] do
      if (Value = cDefault) and (VDiv <>  0 ) and (VMul / VDiv < LVar) then
        begin
          X := I mod FFieldWidth;
          Y := I div FFieldWidth;
          LVar := VMul / VDiv;
        end;
end;

var
  X, Y: Integer;
  R: Boolean;
begin
  InitSweeper;
  try
    repeat
      ShotSweeper;
      if GameFinished then
      begin
        Sleep(cStandardDelay);
        SkipSweeperGreetings;
        Sleep(cStandardDelay);
        StartSweeperGame;
      end
      else
      begin
        SweeperMove(X, Y, R);
        ClickSweeperCell(X, Y, R);
      end;
    until not IsWindow(FMainWindow);
  finally
    DoneSweeper;
  end;
end.
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34996175
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Den_diНа случайно совсем непохоже. Точнее на равномерное. Тут какое-то распределение, при котором они кучнуются по 2-3. Реже по 1. Если рядом,то и до 6+. Тут что-то вроде вероятность поставить на линию зависит от наличия на ней других значений. Вроде как части равномерно, а другие расписывают под них. Притом почти все расклады имеют решение. Значит есть какая-то априорная зависимость, участвующая в генерации. Не всё так просто.

SnowMan2Он их раставляет после первого хода. Первый ход никогда на мину не попадает.

Да! После первого хода игрока, компьютер разгадывает его стратегию , и расставляет мины максимально трудным образом!

;)
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34996217
tokumo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Гость
S.G.
SnowMan2Он их раставляет после первого хода. Первый ход никогда на мину не попадает.

Да! После первого хода игрока, компьютер разгадывает его стратегию , и расставляет мины максимально трудным образом!

;)

ха-ха-ха, только что выше написал что расстановка уже готова перед первым ходом!
...
Рейтинг: 0 / 0
Алгоритм расстановки мин в "Сапер"е?
    #34997742
Серый Волчок Argutus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
tchingiz))
я в следствие ведут колобки,
в сейфе учился поворачивать точно одну ручку недели две чистого времени.
Пока понял алгоритм испотелся весь.

Я понял тока половину алгоритма. Но справился за два часа. :0)X
...
Рейтинг: 0 / 0
52 сообщений из 52, показаны все 3 страниц
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Алгоритм расстановки мин в "Сапер"е?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]