ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Saniya Mamleeva                      2:5011/251.21  23 Jan 2002  16:08:18
 To : Stanislav Aranovsky
 Subject : Re: Сапеp
 -------------------------------------------------------------------------------- 
 

 23 Янв 02 01:40, you wrote to me:
 
  SA>>> Рассматpиваем поле 8x8 с 10 минами. Ваpианты? Идеи? Советы?
  SM>> Там бывают неалгоpитмизиpyемые слyчаи, котоpые никак не pазpешить
  SM>> логикой (pазве что теоpией веpоятности, да и то не всегда).
  SA> Ладно. Пpедлагаю такие ситyации оставлять неpешенными или выводить
  SA> все ваpианты. А алгоpитм pешения в тех слyчаях, когда pешение
  SA> однозначно?
 
 Хм.
 
 Шаг 1) Если есть открытые клетки с числом, равным количеству неоткрытых
 окрестных клеток, то пометить эти неоткрытые клетки как мины. Выполнить для всех
 таких клеток.
 Шаг 2) Если есть открытые клетки с числом, равным количеству помеченных минами
 окрестных клеток, то открыть остальные окрестные клетки. Выполнить для всех
 таких клеток.
 
 Повторять последовательно эти два шага, пока находятся клетки с таким условием. 
 Когда условия перестанут выполняться, то осуществлять последовательный перебор -
 предполагать, что в данной клетке, граничащей с открытой, есть мина (или
 наоборот), и выполнять после этого шаги 1 и 2 виртуально (т.е. не открывая
 клеток и не путая помеченные мины и предполагаемые), пока это не приведёт к
 противоречию, после которого предположение можно будет считать справедливым со
 знаком "не". Предположения можно накапливать в стеке, последовательно перебирая 
 все неоткрытые клетки вокруг тестируемой, и когда будет найдено противоречие, а 
 в стеке останется только одна клетка, то открыть её, если она предполагалась
 миной, или пометить как мину, если наоборот. После чего снова выполнять шаги 1 и
 2.
 
 Противоречие может заключаться в неравенстве всех предполагаемых мин количеству 
 оставшихся мин с учётом тех клеток, которые не граничат с открытыми и потому там
 мины могут располагаться вплотную друг к другу; также - в том, что число в
 клетке оказывается больше, чем число помеченных мин вокруг плюс число неоткрытых
 клеток вокруг, минус число тех из них, что предполагаются открытыми в ходе
 перебора.
 
 Если такой перебор для одной клетки не приведёт к противоречию, то:
 
 а) посмотреть, какие клетки при выполненном полном переборе всегда помечались
 как клетки с минами (без мин) - если такие есть, то пометить их как мины
 (открыть) и перейти к шагам 1 и 2.
 б) если а) не сработало, то выполнять перебор для других клеток.
 
 Если перебор был выполнен для всех клеток, и это не помогло, то показать все
 перебранные варианты последовательно с задержкой, чтобы пользователь мог сам
 рассудить, какой вариант ему выбрать.
 
 :)
 
 Saniya
 
 ---
  * Origin: Dormouse's Teapot (2:5011/251.21)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Сапеp   Stanislav Aranovsky   21 Jan 2002 01:41:34   Re: Сапеp   Saniya Mamleeva   21 Jan 2002 15:45:16   Сапеp   Stanislav Aranovsky   23 Jan 2002 02:40:22   Re: Сапеp   Saniya Mamleeva   23 Jan 2002 16:08:18