Решение игры типа сапера.Интересная. Для умных)

Сейчас на форуме: asfa, _MBK_ (+6 невидимых)

Посл.ответ	Сообщение
shifty Ранг: 0.2 (гость) Активность: 0=0 Статус: Участник	Создано: 06 марта 2010 20:10 · Личное сообщение · #1 Всем привет! Я, к сожалению, крэком не занимаюсь,но случайно на вашем форуме нашел пост, что есть люди, интересующиеся написанием программ для решения логических задач. Собственно, есть ли у кого какие мысли, как можно решить следующую задачу? Задача- симбиоз змейки и сапера)) Дано поле с ячейками. вы находитесь в центре поля, вас окружают 8 ячеек. В каждой ячейке есть цифра.Щелкая на любую из ячеек, вы продвигаетесь на кол-во клеток,равное числу в ячейке, в выбранном направлении.Там вас опять окружают 8 ячеек. Задача пройти по всему полю, не врезаясь в себя и не вылетая за границы поля. Если идти по диагонали, то потом себя можно перепрыгнуть в определенных местах. Ребята, очень надо решить задачу. За актуальную помощь готов даже вознаградить=)) Скрин поля прикреплю, могу выложить и саму игру. Спасибо, если дочитали до сюда. p.s.: модерам. извините, если запостил не той ветке.

Archer Ранг: 2014.5 (!!!!), 1278thx Активность: 1.34↘0.25 Статус: Модератор retired	Создано: 06 марта 2010 20:25 · Личное сообщение · #2 Стоило бы отправить в запросы, но скину в новички. Вдруг, кому-то интересно будет.
BoRoV Ранг: 533.6 (!), 232thx Активность: 0.45↘0 Статус: Uploader retired	Создано: 06 марта 2010 20:25 · Личное сообщение · #3 это ты наверное хочешь чтоб за тебя кто-то курсач сделал... ----- Лучше быть одиноким, но свободным © $me
shifty Ранг: 0.2 (гость) Активность: 0=0 Статус: Участник	Создано: 06 марта 2010 20:26 · Личное сообщение · #4 Нет, это не курсач. Это игра такая)
Coderess Ранг: 355.4 (мудрец), 55thx Активность: 0.32↘0 Статус: Uploader 5KRT	Создано: 06 марта 2010 23:01 · Личное сообщение · #5 Сапер уже много кто пробовал решить, использовалось внедрение в память процесса и все методы, которые мне попадались были с исходными кодами ----- Gutta cavat lapidem. Feci, quod potui. Faciant meliora potentes
Archer Ранг: 2014.5 (!!!!), 1278thx Активность: 1.34↘0.25 Статус: Модератор retired	Создано: 06 марта 2010 23:10 · Личное сообщение · #6 В принципе можно читать память процесса, считывать всё поле. Ползти в любое рандомное направление. Если застрял, откатывать на шаг назад и идти в другое рандомное. Типа брута поля. Кому не лень-прогайте.
shifty Ранг: 0.2 (гость) Активность: 0=0 Статус: Участник	Создано: 06 марта 2010 23:28 · Личное сообщение · #7 Coderess пишет: Сапер уже много кто пробовал решить, использовалось внедрение в память процесса и все методы, которые мне попадались были с исходными кодами это не сапер...внедрения в память не надо, т.к. тут решать надо чисто через комбинаторику..ну это как я вижу..хотя я в таких вопросах не особо разбираюсь. Archer пишет: В принципе можно читать память процесса, считывать всё поле. Ползти в любое рандомное направление. Если застрял, откатывать на шаг назад и идти в другое рандомное. Типа брута поля. да, я так и думаю. но опять же, ПОЛЕ СТАТИЧНО(!!), т.е. оно не меняется от раза к разу. а очень ли сложно будет выполнить то, что вы описали? если есть 8 направлений в каждой точке, а длина перемещения может варьироваться от 1 до 12 клеток. Вот сама игра: wc3acc.narod.ru/game.swf
tex32 Ранг: 9.0 (гость), 1thx Активность: 0.01↘0 Статус: Участник	Создано: 09 марта 2010 21:49 · Личное сообщение · #8 Не понятна цель задачи, так как и зачем это нужно тс, отсюда нет интереса.
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 09 марта 2010 23:42 · Личное сообщение · #9 что возможно заполнить всё поле где сказано? игра на очки и не обязательно что поле возможно заполнить, если это не учтено алгоритмом генерации Брут сделать можно, насколько реально будет время выполнения сложно оценить, но думаю нормально главное заинтересовать программиста, а если бы было чем, думаю цена бы светилась уже в первом посте ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
tundra37 Ранг: 310.8 (мудрец), 29thx Активность: 0.43↘0 Статус: Участник	Создано: 12 марта 2010 10:57 · Личное сообщение · #10 время выполнения сложно оценить, Здесь у дерева куча тупиковых веток будет, т.ч. время вполне реальное. Есть другой вариант : по правилам игры построить все ходы из всех клеток - получим граф. Далее будет известная задача коммивояжера или что-то в этом роде.
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 12 марта 2010 16:18 · Личное сообщение · #11 tundra37 вот с графом реализацию я бы тоже глянул... это намного быстрее будет работать ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 13 марта 2010 13:30 · Личное сообщение · #12 3047 очков! Кто больше? Получено с помощью нижеприлогаемой программы (алго на базе рекурсии). Пилит варианты очень долго, до конца не дождался. Так что это вероятно далеко не максимум. f450_13.03.2010_CRACKLAB.rU.tgz - Saper.rar ----- 127.0.0.1, sweet 127.0.0.1
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 13 марта 2010 22:27 · Поправил: OKOB · Личное сообщение · #13 Версия с полным логом поиска. SaperFullLog.exe > Log.txt !!! Осторожно скорость формирования лог файла 1,5 гига в минуту Формат лога: Level 003( 23, 4) -> NORD ; VALID; SUCCESS (2) ####### Level 004( 23, 2) -> NORD ; VALID; DON'T SUCCESS (11) Level 003 - номер хода (уровень вложенности рекурсии) ( 23, 4) - координаты текущей базовой точки NORD... - направление хода VALID/ DON'T VALID - статус возможности хода в данном направлении SUCCESS / DON'T SUCCESS - результат хода (2) - длина текущего хода c3f8_13.03.2010_CRACKLAB.rU.tgz - SaperFullLog.exe ----- 127.0.0.1, sweet 127.0.0.1
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 14 марта 2010 00:17 · Личное сообщение · #14 OKOB пишет: Версия с полным логом поиска. лучший вариант рекорда то был наёден? ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 14 марта 2010 01:25 · Поправил: OKOB · Личное сообщение · #15 Isaev пишет: лучший вариант рекорда то был наёден? Лучше вариант есть. На скрине вариант на 139 ходов и 539 поинтов, следующий который находится 135 ходов на 543 поинта, но из-за буферизации виндой вывода в логфайл до нахождения следующего возможного рекорда в нем (логе) видны не все ходы. А так времени жалко. Вариантов слишком много при 139-ти ходах и 8-ми направлениях это 8**139 = 3,3846065602060728266338063771278e+125 вариантов. Так что максимум локальный, а поиск глобального мало реален. Видно что со стартовой точки направление СЕВЕР (т.е. первое из восьми) (перебор направлений от СЕВЕРА по часовой стрелке). PS: Заставил программу при нахождении максимума на 543 поинта вытолкнуть лог. Вот результат ходов. Видно что оптимизируется укладка только ближе к голове "змеики", а хвосты совпадают полностью. Так что поле для улучшения результата есть. PSS: Ручками-глазками немного уплотнил в начале. А вообще топ не имеет отношения к реверсу, да и исчерпал себя ибо задача поставленая топикстартером решена - алго реализовано. Топ полноправный кандидат на закрытие. ----- 127.0.0.1, sweet 127.0.0.1
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 14 марта 2010 04:25 · Личное сообщение · #16 Ну раз начали рекордить, то зачем закрывать? ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
tundra37 Ранг: 310.8 (мудрец), 29thx Активность: 0.43↘0 Статус: Участник	Создано: 14 марта 2010 12:19 · Личное сообщение · #17 Вариантов слишком много при 139-ти ходах и 8-ми направлениях это 8139 = 3,3846065602060728266338063771278e+125 вариантов** И что там для 139 ходов мало отсекается? Да и направлений всего 7 Писать лог кстати сильно замедляет поиск. Даю идею. Строим матрицу NxN, где N - число полей. В ячейке (i,j) очки/расстояние (лень условие перечитывать). Далее делается хитрое умножение(складываем содержимое ячеек) на транспонированную матрицу и получаем оценку "двухходовок". И т.д и т.п. Матрицы придется хранить, но это меньше чем лог и можно придумать экономную запись. Если в ячейки писать больше инфы, то можно сразу отловить запрещенные пути. Уже охота прогу написать, но пока лень.
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 14 марта 2010 13:50 · Поправил: OKOB · Личное сообщение · #18 tundra37 пишет: Да и направлений всего 7 Если учитывать что из одного из восьми направлений мы пришли, то исходящих направлений действительно 7. ----- 127.0.0.1, sweet 127.0.0.1
EugenCr Ранг: 4.1 (гость) Активность: 0.01↘0 Статус: Участник	Создано: 15 марта 2010 01:29 · Личное сообщение · #19 OKOB пишет: f450_13.03.2010_CRACKLAB.rU.tgz - Saper.rar А можно исходник глянуть? Очень интересно.
SER[G]ANT Ранг: 147.7 (ветеран), 50thx Активность: 0.12↘0 Статус: Участник sv_cheats 1	Создано: 15 марта 2010 01:42 · Личное сообщение · #20 OKOB эээм.. а там, как бы, "game over", если "змея" себя пересечет, а на скрине она пересекается и ни раз.
Isaev Ранг: 756.3 (! !), 113thx Активность: 0.61↘0.05 Статус: Участник Student	Создано: 15 марта 2010 03:09 · Личное сообщение · #21 SER[G]ANT shifty пишет: Если идти по диагонали, то потом себя можно перепрыгнуть в определенных местах. ----- z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh
OKOB Ранг: 527.7 (!), 381thx Активность: 0.16↘0.09 Статус: Участник Победитель турнира 2010	Создано: 15 марта 2010 11:35 · Личное сообщение · #22 Поменял порядок обхода направлений (стартанул на восток) ----- 127.0.0.1, sweet 127.0.0.1

Для печати