Игра 15


    В начале 1880 года, некий Чарльз Певи, дантист из Вустера, привлёк внимание общественности предложив $1000 (тогда это были неплохие деньги), за решение следующей задачи: пятнадцать шашек были размещены в квадратной коробочке в правильном порядке, и только шашки 14 и 15 были переставлены, как показано на рисунке. Задача состояла в том, чтобы, последовательно передвигая шашки, привести их в нормальное положение, причем, однако, порядок шашек 14 и 15 должен быть исправлен.

    У нас в компании каждый сотрудник может 5 часов в неделю заниматься самообразованием (читать/писать на «Хабр», учить F# или читать SICP). Со временем данная практика эволюционировала в создание мини-проектов. Так, например, Максим, опытный JavaScript-разработчик, решил попробовать себя в создании приложений под iOS, и, примерно, за полтора месяца выпустил пятнашки, которые, без всякой рекламы, за неделю продаж вошли в TOP 10 русского App Store в категории игры.

    Далее код проверки на Objective-C и принцип прохождения пятнашек из книги Якова Исидоровича Перельмана «Живая математика».

    Для многих из нас стало неожиданностью, что ровно половина из всех возможных (1 307 674 368 000) комбинаций, не имеет решений. Для проверки на решаемость мы взяли формулу из википедии: пусть квадратик с числом i расположен до (если считать слева направо и сверху вниз) k квадратиков с числами меньшими i. Будем считать ni = k, то есть если после костяшки с i-м числом нет чисел, меньших i, то k = 0. Также введем число e — номер ряда пустой клетки (считая с 1). Если сумма



    является нечётной, то решения головоломки не существует.

    Код проверки на Objective-C


    #import "GamePositionValidator.h"
    @interface GamePositionValidator(){
    	NSInteger  emptyCellRowNumber;
    }
    @property (nonatomic, retain) NSArray* validPosition;
    @property (nonatomic, retain) NSArray* currentPosition;
    @end
    @implementation GamePositionValidator
    @synthesize validPosition;
    @synthesize currentPosition;
     
    -(id) initWithValidPosition:(NSArray *) _validPosition emptyCellRowNumber:(NSInteger ) _emptyCellRowNumber{
    	if(self = [super init]){
            self.validPosition = _validPosition;
            emptyCellRowNumber = _emptyCellRowNumber;
    	}
    	return self;
    }
    -(NSInteger) positionOfChipInValidPosition:(NSInteger) chipNumber{
    	for(NSInteger i=0; i<self.validPosition.count; i++){
        	NSNumber* number = [self.validPosition objectAtIndex:i];
            if(number.intValue == chipNumber){
            	return i;
        	}
    	}
    	return -1;
    }
     
    -(NSInteger) countOfDisordersInPosition:(NSInteger) position{
    	NSInteger chipNumber = ((NSNumber*)[self.currentPosition objectAtIndex:position]).intValue;
    	NSInteger chipPosition = [self positionOfChipInValidPosition:chipNumber];
    	NSInteger countOfDisorders = 0;
     
    	for( NSInteger i= position+1; i<15; i++){
        	chipNumber = ((NSNumber*)[self.currentPosition objectAtIndex:i]).intValue;
        	NSInteger nextChipPosition = [self positionOfChipInValidPosition:chipNumber];
        	if( nextChipPosition < chipPosition){
                countOfDisorders ++;
       	 }
    	}
     
    	return countOfDisorders;
    }
     
    -(BOOL) isPositionCanBeTransformedToValidPosition:(NSArray*) position{
        self.currentPosition = position;
    	NSInteger totalDisorders = 0;
    	for(NSInteger i=0; i<self.currentPosition.count; i++){
        	totalDisorders+=[self countOfDisordersInPosition:i];
    	}
        self.currentPosition = nil;
    	return (totalDisorders + _emptyCellRowNumber) % 2 == 0;
    }
    @end
    
    

    Это первое приложение Макса на Objective-C так что его можно смело критиковать.

    На последок, принцип прохождения «пятнашек» в книге Я.И.Перельмана «Живая математика»:
    «Представьте расположение, при котором 15 шашек размещены в пестром беспорядке. Рядом передвижений всегда можно привести шашку 1 на место. Точно так же возможно, не трогая шашки 1, привести шашку 2 на соседнее место вправо. Затем, не трогая шашек 1 и 2, можно поместить шашки 3 и 4 на их нормальные места: если они случайно не находятся в двух последних вертикальных рядах, то легко привести их в эту область и затем рядом передвижений достичь желаемого результата.
    Теперь верхняя строка 1, 2, 3, 4 приведена в порядок, и при дальнейших манипуляциях с шашками мы трогать этого ряда не будем.

    Таким же путем стараемся мы привести в порядок и вторую строку: 5, 6, 7, 8; легко убедиться, что это всегда достижимо. Далее, на пространстве двух последних рядов необходимо привести в нормальное положение шашки 9 и 13; это тоже всегда возможно. Из всех приведенных в порядок шашек 1, 2, 3, 4, 5, 6, 7, 8, 9 и 13 в дальнейшем ни одной не перемещают;



    остается небольшой участок в шесть полей, в котором одно свободно, а пять остальных заняты шашками 10, 11, 12, 14, 15 в произвольном порядке. В пределах этого шестиместного участка всегда можно привести на нормальные места шашки 10, 11, 12. Когда это достигнуто, то в последнем ряду шашки 14 и 15 окажутся размещенными либо в нормальном порядке, либо в обратном». Удачи!
    Taucraft Limited
    33.48
    Company
    Share post

    Comments 40

      +17
      Небольшой коммент, почему формула работает. Достаточно убедиться, что любой ход не меняет четность N. Следовательно, играя по правилам, нельзя перевести «четную» позицию в «нечетную». У правильной позиции (где все костяшки идут строго по номерам) N будет четным, а у непавильной (где, например, 14 и 15 переставлены) — нечетной.
        +3
        У себя я решил это иначе. Формула — математически корректное решение. Но лично я перед игрой перетасовываю все пятнашки на глазах у пользователя. Имхо, в этом дополнительный плюс — пользователь заранее знает, что комбинация — точно решаемая.
          0
          В начале мы сделали так же, но для пользователя достаточно долго ожидать старта игры, поэтому мы отказались от такого решения. Фишки просто перелетают сразу на позиции.
            0
            Совершенно верно, ведь пользователь может запомнить решение!
              +5
              100 ходов? Крутой. Думаю, он может получить за это вознаграждение!
          • UFO just landed and posted this here
            • UFO just landed and posted this here
                0
                Там справа-сверху есть количество ходов до конца)
                0
                Спасибо, приятно)
                Ну… Это всё-таки демонстрация фреймворка, мне надо было показать плавную анимацию, а не проработанную игру =)
              +1
              Всё хорошо, но данный алгоритм является обычной имитацией среднестатистического игрока. И поэтому достаточно примитивен.
              Просто вариант превращения позиции не представляет никакого интереса. Алгоритм решения за минимальное количество ходов более ценен для подобных задач.
                0
                Алгоритм достаточно прост, решается обычным перебором.
                  +1
                  И сколько же по времени будет работать перебор решения на 40 ходов? O(4^40)?
                    0
                    Навскидку трудно сказать, но если делать перебор в ширину с запоминанием позиции, которые уже были, алгоритм выглядит достаточно простым и быстрым. Только может возникнуть проблема с памятью.
                      +1
                      Насчёт быстроты — зависит от реализации, ну а использование ресурсов — та самая причина, почему данная трактовка на несколько порядков сложнее наивного алгоритма без ограничений.
                        0
                        Можно попробовать ввести в перебор ограничения, чтобы каждая следующая позиция вела к уменьшению количества беспорядков, а так же эта комбинация еще не посещалась.
                      +1
                      когда-то реализовывал поиск решения используя алгоритм А*(эвристика — к-во не правильно расположенных пятнашек).
                      для 15 ходов ищет 0.035 сек.
                      для 39 ходов ищет 31 сек.

                    0
                    Думаю, альфа-бета отсечения спасут мир. Надо будет попробовать как-нибудь)
                    +7
                    Принцип: «хороший дизайн и вы продадите любую тривиальность!» — в действии.
                      0
                      tiler
                      простите, что похоже на рекламу, но принцип, описанный egormerkushev работает уже третий год :)
                        +2
                        Принцип чертовски эффективен, потому что я купил после одного взгляда на скриншот.
                        +1
                        Помню на втором курсе института написал пятнашки на прологе. Там был выбор размер поля и автоматическое прохождение, правда алгоритм был довольно примитивным.
                          0
                          Писал на 3ем курсе тоже (12 лет назад), только задание было по теме «сетевые технологии» или как-то так… Добавил в свободном поле видимость как играет удаленный пользователь. Можно на скорость с другом играть например. Вот, может идея вашему Максиму пригодится :)
                            +3
                            Вот за что я люблю скриптовые и не люблю компилируемые языки…
                            from itertools import chain
                            from operator import gt
                            def is_valid(field):
                              permutation = chain(*field)
                              return len(filter(None, [gt(permutation[i], a) for i in xrange(len(permutation)) for a in permutation[i+1:]])) % 2 == 0
                            
                              –8
                              Для многих из нас стало неожиданностью, что ровна половина из всех возможных (1 307 674 368 000) комбинаций, не имеет решений.

                              Студенты-математики смотрят на вас с недоумением. Это чистый матан. Теория групп, циклы и все такое. Проходили курсе на втором или третьем.
                                +5
                                Не всеж математики. Есть еще физики и прочие…
                                  +2
                                  На физфаке как раз в базовом курсе теория групп куда жестче, чем в базовом курсе мехмата:)
                                    0
                                    В МГУ — может быть, в ПетрГУ — нет.
                                      0
                                      У нас не было на физфаке теории групп. Вам повезло.
                                        0
                                        Или, возможно, меня дезинформировали. Теперь надо вспомнить, кто из физваковцев мне рассказывал про курс теории групп на 3 семестра)
                                          0
                                          На 3 семестра? Точно обманули. Не так уж глубоко на физфаке дают математику.
                                    +13
                                    Студенты-математики смотрят на Ваш комментарий с недоумением. Когда это теория групп и циклы успели попасть в курс матана? Алгебра это, алгебра!
                                      0
                                      И в самом деле, непонятно. Из статьи можно сделать вывод, что авторы перебрали пару триллионов комбинаций, и каждую проверили (пусть даже проверка велась аналитически, а не поиском решения). Сколько же это заняло времени?
                                      А если результат про нерешаемые перестановки был получен из общих соображений, то в чем неожиданность? Или неожиданностью было увидеть в Вики или где-нибудь еще сам факт, что есть нерешаемые перестановки?
                                        0
                                        Не так все просто. Чему учат на алгебре? Что у перестановки есть четность и что она меняется при транспозиции.
                                        Если мы возьмем позицию, как перестановку из 16 элементов, то каждый ход будет транспозицией, и четность будет меняться. «Ну и что?». Так что надо еще догадаться, что при каждом ходе меняется еще и четность суммы координат пустой клетки, и что в сочетании они дают инвариант. А поиску таких инвариантов (особенно без предварительных знаний/подозрений об его существовании) в общем курсе не учат. Вообще, найти число элементов подгруппы с данными образующими — очень нетривиальная задача. Спросите любого, кто собирал много различных многогранников Рубика (и самостоятельно искал алгоритмы).
                                        –4
                                        Эта игра… Гори в аду!
                                          +4
                                          Мне кажется, вам надо с кем-то поговорить об этом…
                                            +2
                                            И за что человека заминусовали?
                                            Многие игры настолько хороши, что отбирают чрезмерное количество свободного времени. И многие игроки не в силах совладать со стремлением поиграть подольше. Очевидно же.
                                              0
                                              А вот и нет — я эту игру ненавижу именно за то, что ее просто обожают вставлять в полноценные игры в качестве миниквеста, например. А поскольку в эти игрульки играет девушка моя, то тут просто challenge accepted — пройди девушке игру, надейся на хорошее настроение вечером!
                                            0
                                            Скачал ее пару дней назад, отличная реализация! Только немного отвлекает таймер, слишком он яркий. Вот если бы был режим на весь экран, было бы совсем круто :)
                                              0
                                              Попробуем сделать в след апдейте
                                              0
                                              Максим, опытный JavaScript-разработчик, вполне может превратиться в инди-разработчика. Старт хороший.

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