Ответ 1
Несколько лет назад я написал решение для Minesweeper, но, увы, я, похоже, потерял код с тех пор. Я помню, что это был метод грубой силы, который скомпилировал множество потенциальных минов, а не оставлял комбинации, собранные так, как вы.
Я считаю, что этот алгоритм был более способным, чем алгоритм, с которым вы работаете. Ваш подход может "решить" условие, если он полностью заполнен или пуст минами, или если он является подмножеством другого условия. Тем не менее, есть некоторые выводы, которые это не будет обрабатывать. Например, рассмотрите эту небольшую плату размером 7x2, где плитки a через h неизвестны:
a 2 1 2 1 2 i
b c d e f g h
Ваши условия будут:
[2, {a, b, c, d}],
[1, {c, d, e}],
[2, {d, e, f}],
[1, {e, f, g}],
[2, {f, g, h, i}]
Если я правильно понял, ваш алгоритм не может делать никаких выводов об этом. Однако, если вы опытный игрок Minesweeper, вы поймете, что шаблон 1 2 1 в центре имеет только одно решение с минами ниже 1 s:
a 2 1 2 1 2 i
b 2 * 2 * 2 h
До сих пор неизвестные, с миной под a или b, а другая - под h или i, но если это было частью более крупной головоломки, вы могли бы увидеть их позже ( или вам, возможно, придется догадаться).
Я считаю, что мой подход к минам работал следующим образом:
Для каждого фрагмента, который был расширен, соберите один набор всех его нерасширенных соседей ("area") и список, содержащий все наборы мины, которые могут встречаться в этой области. Так, например, 5 известных фрагментов в приведенном выше примере генерируют (слева направо):
({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}])
({c, d, e}, [{c}, {d}, {e}])
({d, e, f}, [{d, e}, {d, f}, {e, f}])
({e, f, g}, [{e}, {f}, {g}])
({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}])
Во всяком случае, чтобы совместить два условия, я должен сначала проверить, что они перекрываются, путем пересечения наборов областей. Если не было перекрытия, условия не могут быть скомбинированы.
Если бы произошло перекрытие, новое условие охватывало бы объединение их областей. Что касается наборов мины, я бы сделал декартово произведение внешних множеств, чтобы получить пары внутренних множеств, а затем проверить, было ли противоречие. Противоречие было бы, если бы в пределах пересечения областей два набора не имели ровно одинаковых шахт. Если бы не было никакого противоречия, новый союзный набор был бы сформирован из союза шахт. Здесь как первые две строки выше будут объединяться:
Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d}
New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e}
Cartesian product of mine sets (with X marking contradictions):
| {a, b} {a, c} {a, d} {b, c} {b, d} {c, d}
---+-------------------------------------------------
{c}| X {a, c} X {b, c} X X
{d}| X X {a, d} X {b, d} X
{e}| {a, b, e} X X X X X
New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}])
Вы можете рассчитать шансы любой плитки в области условий, являющейся мином, просто подсчитав, сколько из наборов она является частью, относительно того, сколько наборов есть общее. Поэтому, учитывая комбинированное условие выше, вы можете понять, что a является миной 3/5-й секунды, тогда как e - только 1/5 раз. Эта информация важна, когда программа должна угадывать местоположение, которое нужно развернуть, когда нет никаких безопасных плиток. Я думаю, что я также сделал некоторые сложные комбинаторики, чтобы учесть количество используемых мин (так что вышеприведенный случай {a, b, e} был бы взвешен немного иначе, чем другие случаи, поскольку он использует три мины, а не два), но я боюсь, что не помню подробностей.
Minesweeper - довольно сложная игра. Я считаю, что моя программа смогла разрешить доски, эквивалентные "трудным" трудностям примерно в 50-60% случаев, причем большая часть потерь происходит либо в начале (когда вы должны угадывать с небольшим количеством информации для работы), либо конец (когда часто есть несколько неразрешимых областей, которые необходимо угадать). Обычно это было довольно быстро, хотя изредка существовал узор плиток, который заставлял его болеть в течение 10 или 15 секунд, прежде чем сделать следующий шаг. (Minesweeper NP-complete, поэтому неудивительно, что некоторые входы не могут быть решены быстро!)
