Дело в том, что я скачал в аппсторе набор головоломок Игры разума. И безнадежно застрял на уровне «Китайские шашки». Можно было найти прохождение в интернете, но это больше не наш метод. Теперь мы сами с усами. Мир никогда больше не будет прежним.
Китайские шашки
Есть поле, на поле стоят фишки. Одна из клеток — пустая. Мы можем перемещаться только съедая шашку на соседней клетке, перепрыгивая через нее. По диагонали кушать шашки нельзя. Исходное состояние:
o o o o o o o o o o o o o o o o . o o o o o o o o o o o o o o o o
Следующий ход возможен, например, такой:
o o o o o o o o o o o o o o . . o o o o o o o o o o o o o o o o o
Вот такая простенькая задача. Хе-хе, было подумал я, минуты три на решение. Через несколько дней я крепко чесал в затылке и пытался родить какую-нибудь действующую тактику. Задача, ****, не решалась. Придется применять питон.
Из курсов я вынес, что во всех поисковых задачах нужно решить всего три подзадачи (господи, кому я это рассказываю — это ж, наверное, азы):
- Закодировать состояние системы
- Проверить, является ли определенное состояние решением
- Сгенерировать следующие состояния
Что-то бился я, бился с кодированием состояния, и в итоге остановился на простой строке в 49 символов длинной:
initState = ' ooo '+' ooo '+'ooooooo'+'o..oooo'+'ooooooo'+' ooo '+' ooo ' Это сильно облегчает решение первого пункта, но грозит проблемами третьем. Ну и ладно. В общем, как нас и учили, пишем класс Problem:
class Problem(object): def __init__(self, initState): self.initState = initState def isGoal(self, state): if state.count('o') > 1: return False else: return True def generateSuccessors(self, state): res = [] idx = 0 for c in state: if c == '.': ##we can move here res += self.getValidMoves(state, idx) idx += 1 return res def getValidMoves(self, state, idx): res = [] ## get North: if idx in [16,17,18,23,24,25,28,29,30,31,32,33,34,37,38,39,44,45]: sN = state[:] if sN[idx-7] == 'o': if sN[idx-14] =='o': sN = sN[0:idx-14]+'.'+sN[idx-13:idx-7]+'.'+sN[idx-6:idx]+'o'+sN[idx+1:] res.append(sN) ## get South: if idx in [2,3,4,9,10,11,14,15,16,17,18,19,20,23,24,25,30,31,32]: sS = state[:] if sS[idx+7] == 'o': if sS[idx+14] =='o': sS = sS[0:idx]+'o'+sS[idx+1:idx+7]+'.'+sS[idx+8:idx+14]+'.'+sS[idx+15:] res.append(sS) ## get West: if idx in [4,11,16,17,18,19,20,23,24,25,26,27,30,31,32,33,34,39,46]: sW = state[:] if sW[idx-1] == 'o': if sW[idx-2] =='o': sW = sW[0:idx-2]+'..o'+sW[idx+1:] res.append(sW) ## get East: if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]: sE = state[:] if sE[idx+1] == 'o': if sE[idx+2] =='o': sE = sE[:idx]+'o..'+sE[idx+3:] res.append(sE) return res def printState(self, state): res = '' for x in range(7): for y in range(7): res += state[x*7+y]+' ' res+='\r\n' print res Фактически здесь мы определяем начальное значение системы при инициализации проблемы и определяем методы для решения пп 2 и 3. На наше счастье, проверить любое состояние на то, является ли оно решением, предельно просто — считаем, сколько фишек осталось на доске — если больше одной, то надо еще поработать.
А вот с генерацией валидных следующих ходов я немножко помучился, так как строка одномерна, а доска двумерна. И надо это как-то приводить друг к другу. Возможно, даже скорее всего, я набыдлокодил, но в свое оправдание хочу сказать, что я, кажется, смог применить принцип KISS, про который так много читал на хабре. А поэтому идем по доске, на каждой пустой клеточке смотрим по всем направлениям — есть ли две фишки в том направлении. Если да — то заменяем те фишки пустыми местами, а само пустое место — фишкой. И отдаем, как следующий ход.
Несколько наблюдений:
- В этой задаче решение находится всегда на дне графа. А значит breadth-first search всегда будет максимально долгим.
- В этой задаче невозможно прийти в одно из предыдущих состояний. Соответственно можно не париться проверкой на закольцовку графа (см.дальше, все на самом деле интереснее), но просто меня так учили и я это сделал
- К этой задаче не придумывается эвристика. По крайней мере она не придумывается просто. Любой ход приводит к уменьшению количества фишек на 1. Значит можно только по взаимному положению фишек оценить «хорошесть» или «плохость» состояния. А это нетривиально
Поэтому алгоритм будет простенький:
def dfs(p): fringe = [[p.initState]] tried = set() while fringe: cur = fringe.pop() tried.add(cur[-1]) for lm in p.generateSuccessors(cur[-1]): if p.isGoal(lm): return cur+[lm] else: if lm not in tried: fringe.append(cur+[lm]) return None Здесь p — это объект класса Problem
p = Problem(initState) Все готово, запускаем и уходим пить чай. Лет на 12-ть, так как копму предстоит перебрать в самом худшем случае 2^32 комбинаций. Тут я схитрил и сразу же уменьшил количество комбинаций вдвое, сделав первый ход за компьютер и задав начальным состоянием положение фишек уже после первого хода. Дальше я заметил, что доска — центрально симметричная, а значит всегда будет четыре дублирующихся состояния с учетом поворота доски на 90, 180 и 270 градусов. Чуть усложним проверку на расрытые ноды графа:
def rotateField(field): res = '' for i in range(7): for j in range(7): res += field[7*j+i] return res …
if lm not in tried: lmr = rotateField(lm) if lmr not in tried: if rotateField(lmr) not in tried: if rotateField(lm) not in tried: fringe.append(cur+[lm]) Ну и все-таки несколько веток я отрезал, включив проверку на состояние, когда на доске есть фишки, но они гарантированно далеко друг от друга и не смогут друг друга сожрать:
o o o o o o . . . . . . . . . . . . . . . . . . . . . o o o o o o
def checkDeadCombinations(state): ''' False = dead True - combination is OK''' if '.'*21 in state: if '.' in state[:14] and '.' in state[-15:]: return False if '.'*21 in rotateField(state): if '.' in state[:14] and '.' in state[-15:]: return False Ну вот, теперь есть надежда, что я доживу до того момента, как комп решит за меня эту задачку 🙂
Домино
Предыдущую задачку решил, чем привел жену в восхищение, и тут же уткнулся в следующую. Дана коробка костяшек домино (28 штук, стандартная). Надо выбрать 8 костяшек и сложить их в квадрат 4х4, так что получается два вертикально стоящих ряда по четыре костяшки в каждом.
HHHH HHHH
Суммы по строкам, столбцам и диагоналям должны быть равны шести:
Здесь можно применить поиск решения задачи с ограничениями, но, поняв принцип, я так и не научился реализовывать его в коде. Поэтому будем тупо брутфорсить.
Генерим костяшки:
dices = [] for i in range(7): for j in range(i,7): dices.append((i,j)) В итоге имеем лист пар типа (0,0), (1,0) и т.д. для каждой косточки домино.
Поскольку сумма в каждой строке равна шести, строк четыре, то нам нужны все комбинации фишек, дающих в сумме 24. Посидел я, поскрипел мозгами на тему того, как составить все эти комбинации, потом вспомнил, что python comes with batteries included и просто нажал на кнопку включения:
def iterWorkingSets(dices): for cmb in itertools.combinations(dices, 8): ds = 0 for dice in cmb: ds += dice[0] ds += dice[1] if ds == 24: yield cmb В итоге мы отсеяли все комбинации костяшек, которые гарантированно решения не дадут. Дальше я просто перебрал все комбинации и для каждой комбинации попереставлял костяшки, проверяя, нет ли решения:
def checkArr(arr): diag = 0 idx = 0 ##print arr for row in arr: diag += row[idx] idx += 1 if sum(row) != 6: #print 'row', idx, 'is not 6' return False if diag !=6: #print 'diag 1 is not 6' return False diag = 0 idx = 3 arr = arr.transpose() for row in arr: diag += row[idx] idx -= 1 if sum(row) != 6: #print 'column', idx, 'is not 6' return False if diag != 6: #print 'diag 2 is not 6' return False return True Решения не было. Я запустил еще раз. Решения не было опять. Если бы я курил, я бы пошел покурить. Что-то тут не то, подумал я. Брутфорсер так просто не заборешь, решение быть должно, а значит ошибка в брутфорсере. И стал искать ошибку. Ошибка не находилась. Выпив энное количество кофе, я пошел поиграть в саму игру, чтобы понять — что же я делаю не так. Запустил игру, покидал костяшек на поле и стал их двигать и перевора… ПЕРЕВОРАЧИВАТЬ! Брутфорсер не переворачивал костяшки!
Ой, а как же это, блин, написать? Опять itertools, генерим суперсет для range(6), потом для каждой комбинации прогоняем ее через суперсет, перевертывая костяшки. Ой, мама.
### Я бы никогда не смог так написать allsubsets = lambda n: list(itertools.chain(*[itertools.combinations(range(n), ni) for ni in range(n+1)]))
for wc in iterWorkingSets(dices): wc = list(wc) print 'I here loop through all set of dices that produce 24' print 'This is comb #', cmbNum, ':' print wc cmbNum += 1 for turn in allsubsets(6): tc = wc[:] for k in range(6): if k in turn: tc[k] = wc[k][::-1] else: tc[k] = wc[k] #print 'This is subcom of comb #', cmbNum, ':' #print tc for c in itertools.permutations(tc): ''' I here loop through all re-combinations of the same set''' allNum = [] for a in c: allNum+=list(a) arr = pylab.array(allNum).reshape(4,4) if checkArr(arr): print 'Solution:', arr break print 'Solution was not found' Запускаем. Сначала решений нет, так как в сетах присутствуют «тяжелые кости»:
This is comb # 3 : [(0, 0), (0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (1, 1), (2, 5)] Solution was not found Но потом, начиная с энной комбинации, начинают сыпаться решения.
Брутфорсер получился меееедленный, но рабочий.
Ну вот и все. Теперь, если вы спросите меня, пригодились ли мне курсы edx в жизни, я гордо отвечу «Да!» и дам ссылку на эту статью.
ссылка на оригинал статьи http://habrahabr.ru/post/166223/
Добавить комментарий