Применяем на практике знания, полученные на курсе MIT 6.00x (edx.org)

    В комментариях к моему посту про курс 6.002x MITx мне задавали вопрос — пригодилось ли изученное в жизни. И я отвечал — да, конечно, вот тут утром пока зубы чистил, RC-константу посчитал… Но пруфов не было. С тех пор я закончил еще два курса — UC Berkeley CS188.1x Introduction to Artificial Intelligence (открыта регистрация на 18 февраля) и MITx: 6.00x Introduction to Computer Science and Programming. И если после CS188.1x я просто был полон эмоций и не знал, куда бы приткнуть свежеполученные знания (кроме как решить задачу о ходе коня), то после прохождения 6.00x подвернулся случай блеснуть.

    Дело в том, что я скачал в аппсторе набор головоломок Игры разума. И безнадежно застрял на уровне «Китайские шашки». Можно было найти прохождение в интернете, но это больше не наш метод. Теперь мы сами с усами. Мир никогда больше не будет прежним.

    Китайские шашки


    Есть поле, на поле стоят фишки. Одна из клеток — пустая. Мы можем перемещаться только съедая шашку на соседней клетке, перепрыгивая через нее. По диагонали кушать шашки нельзя. Исходное состояние:
        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 

    В итоге должен остаться только один(с). Вот такая простенькая задача. Хе-хе, было подумал я, минуты три на решение. Через несколько дней я крепко чесал в затылке и пытался родить какую-нибудь действующую тактику. Задача, ****, не решалась. Придется применять питон.

    Из курсов я вынес, что во всех поисковых задачах нужно решить всего три подзадачи (господи, кому я это рассказываю — это ж, наверное, азы):
    1. Закодировать состояние системы
    2. Проверить, является ли определенное состояние решением
    3. Сгенерировать следующие состояния

    Что-то бился я, бился с кодированием состояния, и в итоге остановился на простой строке в 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)
    

    Все готово, запускаем и уходим пить чай. Лет на двенадцать, так как компу предстоит перебрать в самом худшем случае 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
    

    Но потом, начиная с энной комбинации, начинают сыпаться решения:
    [[0 0 6 0]
     [1 4 0 1]
     [1 2 0 3]
     [4 0 0 2]]

    Брутфорсер получился меееедленный, но рабочий.
    Ну вот и все. Теперь, если вы спросите меня, пригодились ли мне курсы edx в жизни, я гордо отвечу «Да!» и дам ссылку на эту статью.
    Share post

    Similar posts

    Comments 36

      +1
      У вас в описании задачи про китайские шашки не написано, чего получить то надо:) По тексту статьи понял, что должна остаться только 1 фишка, правильно?
        +1
        Ага, сейчас допишу. Спасибо
          +1
          Странно, что это китайские, а не шотландские :)
            0
              0
              Английская вики говорит, что китайские — это игра на несколько человек на поле в виде звезды Давида. У нас она когда-то называлась «уголки». А то, что описано здесь — «Peg solitaire», на русский не переводится.
                0
                Да я не против, это просто фильмом «Горец» навеяло :)
            0
            прошу прощения, если что-то упустил, а какой это язык?
              +6
              [sarcasm]
              Статья написана на русском.
              Скрипты на английском.
              [/sarcasm]

              Код: Python
                +2
                спасибо! интересный язык
              0
              А что такое idx и что значат условия типа
              if idx in [2,9,14,15,16,17,18,21,22,23,24,25,28,29,30,31,32,37,44]:
              

              ?
                0
                Это значит, что на клетку, индекс которой в квадрате 7*7 равен idx, можно пойти. В данном случае, справа (на клетку 2 — прыжком с клетки 4 через клетку 3).
                  0
                  как-то не вполне ясно — откуда эти числа взялись и почему они повторяются в разных условиях?
                    0
                    В разные клетки можно попасть с разных сторон. В клетку 2 — справа и снизу (с 4 через 3 и с 16 через 9 соответственно), в клетку 3 — только снизу (с 17 через 10), в клетки центрального квадрата — со всех четырёх сторон. Поэтому в разных массивах находится разный набор клеток, но некоторые встречаются в нескольких массивах. Откуда взялись? Вероятно, получены методом пристального взгляда на игровое поле :)
                      0
                      рисуешь в екселе табличку 7х7 клеток, нумеруешь их, думаешь как можно попасть в клетку, сделав валидный ход.
                      >>> Откуда взялись? Вероятно, получены методом пристального взгляда на игровое поле :)
                      во-во
                  +3
                  Решение на C++ с кодировкой состяний битовой строкой (младшие 33 бита из int64) решает «китайские шашки» за 40 секунд. Безо всяких отсечений. Количество комбинаций, которые пришлось перебрать — около 110 миллионов.
                    +3
                    Заменил поиск в ширину на рекурсию — решила за секунду. Программа сократилась на треть.
                      0
                      А можно исходники куда-нибудь выложить?
                        +3
                        Пожалуйста.
                        Единственная проблема — что при выводе хода она первые две клетки выводит в случайном порядке.
                        #include<stdio.h>
                        #include<memory.h>
                        #include<time.h>
                        
                        int *Arr;   // 2^30 bytes, 2^28 ints
                        int L=1<<28;
                        long long Sit0=0x1fffeffffLL;
                        
                        int fld[49]={-1,-1,0,1,2,-1,-1, -1,-1,3,4,5,-1,-1, 6,7,8,9,10,11,12, 13,14,15,16,17,18,19, 20,21,22,23,24,25,26, -1,-1,27,28,29,-1,-1, -1,-1,30,31,32,-1,-1};
                        int nsteps=0;
                        long long Steps[80][2];
                        void AddStep(int a,int b,int c){
                        	if(a<0 || b<0 || c<0) return;
                        	Steps[nsteps][0]=(1LL<<a)+(1LL<<b);
                        	Steps[nsteps][1]=(1LL<<c);
                        	Steps[nsteps+1][0]=(1LL<<c)+(1LL<<b);
                        	Steps[nsteps+1][1]=(1LL<<a);
                        	nsteps+=2;
                        }
                        
                        void InitSteps(){
                        	for(int i=0;i<49;i++){
                        		if((i%7)<5) AddStep(fld[i],fld[i+1],fld[i+2]);
                        		if(i<35) AddStep(fld[i],fld[i+7],fld[i+14]); 
                        	}
                        }
                        
                        int Solution[33];
                        int LS=0;
                        
                        bool Solve(long long s){
                        	Arr[(int)(s>>5)]|=1<<((int)s&31);
                        	if((s&(s-1))==0) return true;
                        	for(int k=0;k<nsteps;k++){
                        		long long u=Steps[k][0],v=Steps[k][1];
                        		if((u&~s)==0 && (v&s)==0){
                        			long long s1=(s&~u)|v;
                        			if((Arr[(int)(s1>>5)]&1<<((int)s1&31))==0){
                        				if(Solve(s1)){
                        					Solution[LS++]=k;
                        					return true;
                        				}
                        			}
                        		}
                        	}
                        	return false;
                        }
                        
                        void main(){
                        	long c=clock();
                        	InitSteps();
                        	Arr=new int[L];
                        	memset(Arr,0,L*4);
                        	if(Solve(Sit0)){
                        		for(int m=LS;--m>=0;){
                        			int k=Solution[m];
                        			long long u=Steps[k][0],v=Steps[k][1];
                        			for(int i=0;i<33;i++) if(u&1LL<<i) printf("%d ",i);
                        			for(int i=0;i<33;i++) if(v&1LL<<i) printf("-> %d\n",i);
                        		}
                        	}
                        	printf("Time=%ld\n",clock()-c);
                        }
                        

                        Кстати, как выкладывать, чтбы оно было с вертикальным скроллбаром?
                          0
                          Уж простите, но код, решающий китайские шашки — как китайская грамота выглядит :) Расскажите народу, пожалуйста, что к чему.
                            +4
                            Что ж. Если вы не любите разгадывать головоломки…
                            На поле 33 клетки. Нумеруем их от 0 до 32 в любом порядке. После этого каждую позицию можно представить в виде 33-битного двоичного числа (1 в k-м разряде означает, что на k-м поле есть фишка). Поскольку в int 33-битное число не укладывается, приходится использовать long long.
                            Создаём массив возможных ходов. Каждый ход описывается двумя масками: в первой — 2 ненулевых бита, указывающие, на каких полях должны были находиться фишки до хода, во второй — 1 бит, указывающий, где будет фишка после хода. Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0, а после хода мы окажемся в позиции (F&~U)|V. Можно было бы проще, если вместо W взять 3-битную маску U|V, тогда ход возможен, если ((F^U)&W)==0, а новая позиция F1=F^W. Но уж как написал, так написал.
                            Для инициализации ходов берём карту поля (fld), просматриваем на ней все отрезки длины 3. Пусть отрезок состоит из клеток a,b,c. Если все клетки принадлежат игровому полю (номера неотрицательны), то такой отрезок даёт два хода. Для первого маска U=(1<<a)|(1<<b), V=1<<c, а для второго — U=(1<<b)|(1<<c), V=1<<a.
                            Заводим массив, в котором каждой возможной позиции соответствует 1 бит. Позиций у нас 2^33, и такой массив займёт 1 гигабайт, для которого найдётся место даже в 32-битном режиме. Этот массив нам понадобится, чтобы помечать уже обработанные позиции.
                            Выписываем маску Sit0, соответствующую стартовой позиции, и начинаем решение.
                            Решение рекурсивно, функции Solve передаётся единственный параметр — маска s позиции.
                            Сразу помечаем в битовом массиве, что решением этой позиции мы уже озабочены.
                            Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки. Если фишка одна, возвращаем true — позиция имеет решение.
                            Если фишек больше одной, то перебираем все ходы, и для каждого смотрим, возможен ли он (проверяя условие (U&~s)==0 && (V&s)==0). Если ход возможен, вызываем Solve для позиции, возникшей после этого хода, и смотрим результат. Если true — мы нашли решение, сохраняем наш ход в стеке Solution, и сами возвращаем true. Если же ни один из ходов не привел к результату, значит, позиция тупиковая — возвращаем false.
                            После того, как функция Solve(Sit0) вычислилась (и вернула true), в стеке Solution оказалась в точности та последовательность ходов, которая привела к решению. Осталось её распечатать.
                            Если бы на поле было хотя бы на одну клетку больше, дела (в 32-битной системе) были бы намного хуже — пришлось бы заводить hash-таблицу с масками просмотренных позиций и надеяться, что мы успеем закончить поиск до того, как таблица переполнится.
                              +1
                              Фразу "… если вместо W взять 3-битную маску U|V..." следует читать, как "… если вместо V взять 3-битную маску W=U|V.."
                                0
                                Я не «не люблю». Не умею, скорее. Возможно, для всех ваш код предельно ясен, но я попытался понять, но не смог. Спасибо за пояснения :)

                                Можно пару вопросов:

                                «Если первая маска равна U, вторая V, а текущая позиция F, то ход возможен, если выполняется условие (U&~F)==0 && (V&F)==0»
                                поясните, как (разберем, например, 0, 1, 2 как a,b,c) 11 (в двоичной) соотносится с «на каких полях находятся фишки до хода» и как прийти к проверке на возможность хода?

                                «Проверяем, не осталась ли на поле ровно одна фишка. Это делается проверкой условия (s&(s-1))==0 — оно выполняется только для s=0 и для степеней двойки.»
                                Ну а если на поле, скажем, осталось как раз 2^n фишек?
                                  +1
                                  F=3=00011 в двоичной записи значит, что фишки находятся на клетках 0 и 1, а на остальных клетках фишек нет. Если a=0, b=1, c=2, то для одного из ходов будет U1=00011, V1=00100 (прыжок из клетки 0 через 1 на клетку 2), а для другого — U2=00110, V2=00001 (прыжок из 2 через 1 на клетку 0).
                                  В первом случае U1&~F = 00011&11100 = 00000, V1&F = 00100&00011 = 00000 — ход возможен. После хода мы перейдем в ситуацию (F&~U1)|V1 = (00011&11100)|00100 = 00100 — на поле стоит одна фишка, на клетке 2.
                                  Во втором случае U2&~F = 00110&11100 = 00100 != 0 — ход невозможен: на клетке 2 нет фишки.

                                  Число s задано так, что каждый бит 1 в его двоичной записи показывает, что на данной клетке есть фишка. Если на поле 2^n фишек, где n>0, то в двоичной записи соответствующего числа s будет более одной единицы, а значит, само s не будет степенью двойки. И s&(s-1) не будет равно нулю.
                                    0
                                    Да, я вижу, что битовые операции дают верные результаты, но меня интересует, так сказать, как вы пришли к этому инварианту — откуда следует, что создав именно такие маски, для любого подходящего хода выражения будут верны?
                                      0
                                      Ох… я просто прикинул, что хочу получить, и написал.
                                      Сравнивать с нулём проще, чем с маской из единиц, поэтому 1 в маске результата должно означать, что «что-то не так». Что у нас может быть не так?
                                      — в маске U стоит 1, а в F — 0 (фишки, нужной для хода, нет в наличии)
                                      — в маске V стоит 1 и в F тоже 1.
                                      Нам нужно написать выражение, которое при выполнении любого из этих условий для какого-то бита запишет в этот бит 1, а если оба условия не выполняются — оставит там 0.
                                      Глядя на формулировку, видим, что итоговая формула имеет вид A|B, где A=«в маске U стоит 1, а в F — 0», а B=«в маске V стоит 1 и в F тоже 1».
                                      Формулу B записать проще: в ней явно видна формулировка операции «и»: B=(F&V). Формула A — это тоже «и», но вместо F надо взять ~F (чтобы 0 превратился в 1). Получаем условие
                                      ((U&~F)|(V&F))==0. Можно было бы с ним еще поиграться (и довести до ((U|V)&(F^U))==0), но это непросто и незачем.
                                        0
                                        Хм. Спасибо большое. Теперь все стало понятно.
                                        Учту на будущее, как можно рассуждать.
                                  0
                                  Я тут используя ваши идеи тоже написал код, он получился в чуть более «С++» стиле.
                                  Находит решение за 1.3 сек и 1.0 GB с использованием vector<bool> и за 1.7 сек и несколько MB с использованием std::unordered_set.
                            0
                            эээээ
                            логично же блин
                            :-(
                            не программист я
                              0
                              стоп
                              рекурсия — это тоже поиск
                              только более эффективный
                              0
                              Мне так кажется, что код на Python тоже будет работать быстрее например на pypy.
                              –2
                              Хм, алгоритм пришел в голову меньше чем за пол минуты, со 2 попытки. Или это программа для того, чтоб была программа?
                                +1
                                Я вообще недогадлив. Например, я не догадался одолжить у вас голову…
                                И, кстати, да. Программа, для того, чтобы была программа. Можно предположить, что на курсы по введению в прикладное программирование я пошел не от переизбытка знаний в области :-)
                                0
                                Ты программировал на чем-нибудь до прохождения этого курса?
                                  0
                                  C-embedded
                                  но фигово
                                  0
                                  Я чувствую себя таким глупым, потому что решал все эти головоломки без помощи программирования. :(
                                  А с ходом коня — на шамхматном поле оставалась 1 клетка. Польностью заполнить так и не получилось, но пробовал это дело ещё в 9 или 10 классе, потом как-то забылось и перестал пробовать.

                                  Пользуясь случаем, посоветуйте литературу по Python и C++, собираюсь в ближайшем будущем заняться (до этого немного программировал на Pascal и Delphi). Спасибо.
                                    0
                                    Я с радостью тебе помогу:

                                    Специально для habrahabr, накидал мою реализацию алгоритма на C#, забирать тут:

                                    github.com/hack2root/checkersolver.git

                                    Из особенностей:
                                    1) вывод дерева решения,
                                    2) возможность задания произвольной формы доски (т.к. есть матрица смежности)
                                    3) полностью реализация в объектно-ориентированном стиле
                                    4) возможность проигрывания решения (undo/redo)
                                    5) статистика использования ветвлений при поиска решения в пространстве решений

                                  Only users with full accounts can post comments. Log in, please.