Компания
32,19
рейтинг
19 декабря 2014 в 13:50

Разработка → 6 игр за 6 недель — игра третья

В пятницу должны быть котики. Их есть у меня.

image

Игра третья — B4.
Это — настоящий пасьянс. Сложный, как запрос в Perl.
Потому успехом будет пользоваться только у математиков с Хабра и командировочных в поезде Москва-Екатеринбург.

В своем докладе я коротенько (строк на 40) расскажу о генерации раскладов, выдвину лемму о сходимость любого расклада, имеющего две степени свободы и продемонстрирую как я был сапогом, а стал дедушкой.

К комментариях zikher предложил контр-пример, вроде бы опровергающий лемму. Но пример решили.



Правила


Правила такие же, как в игре Четыре комнаты. В комнате лежит цветной мусор. Мусор можно гонять по комнате движениями пальца по экрану — либо по горизонтали, либо — по вертикали.
Красный мусор можно выбросить через красную стенку. Желтый мусор — через желтую. Синий- через синюю. Голубой — голубую. Больше правил нет.

Поонятненько? Перейдем к примерам.

Посмотрите на рисунок 1. Необходимо очистить комнату от цветного мусора.

image
Рисунок 1. Простейший расклад

Решение для расклада на рисунке 1 состоит из двух ходов.
  1. сдвинуть фишки вправо (исчезнет красный мусор через красную стенку)
  2. сдвинуть фишки вверх (исчезнет синий мусор)

Пасьянс решен.

На рисунке 2 пример сложнее.

image
Рисунок 2. Если первый ход сделать вверх — пасьянс не сойдется.

Решение для расклада на рисунке 2 состоит из пяти ходов.
  1. сдвинуть фишки вправо
  2. сдвинуть фишки вниз
  3. сдвинуть фишки влево(исчезнет желтый мусор)
  4. сдвинуть фишки вверх(исчезнет синий мусор)
  5. сдвинуть фишки вправо

Пасьянс решен.

Пример номер 66




Генерация раскладов


В пасьянсах очень важна генерация раскладов. С одной стороны они должны быть случайными, с другой стороны всегда должна быть возможность повторить случайный расклад — либо подкинуть его приятелю на слабо!, либо сыграть заново самому.

Проблема в том, что моя игра универсальная — есть игра под iPhone, а есть интернет вариант. Как добиться одного и того же расклада на Objective C и JavaScipt?

Как ни странно — решение лежит в Visual Studio от Microsoft.

Я залез в math библиотеки VS и вытащил код функции псевдо-случайной генерации чисел.

- (int)microsoft_rnd {
    holdrand = holdrand * 214013  + 2531011;
    return ((holdrand >> 16)  & 0x7FFF);
}




Задавая начальное значение в глобальной переменной holdrand — я могу повторить случайную последовательность столько раз, сколько захочу. Для удобства я завел 1 000 000 начальных раскладов и расширил функционал своего класса.

- (int) microsoft_rand:(int) number{
    return [self microsoft_rnd] % number;
}

// Пример использования функции - получение случайного числа в диапазоне 1 - 4
...
  int k = 1 + [self microsoft_rand:4];
...


На JavaScript данная функция выглядит чуть иначе
function microsoft_rnd()
{
	var r;
	var big = 4294967295+1;
	microsoft_rnd.seed = (microsoft_rnd.seed * 214013 + 2531011)%big;
	r = microsoft_rnd.seed;
	r = Math.floor(r/65536);
	r = r%32768;
	return r;
}

function microsoft_rand(number)
{
	return (microsoft_rnd())%number;
};



Экспериментально проверено, что результат работы функции во всех системах идентичен.

Таким образом задавая holdrand равным, например 2015, я получаю один и тот же расклад как на iPhone, так и в браузере.

Как я проверял игру



Первый раз запустив игру я расстроился. Выбранный мной расклад не сошелся. Я завелся. То есть завел большую картинку с симпатичной теткой, закрыл ее кнопками от 256 первых раскладов и начал играть с умом. При правильном решении очередного расклада — кнопка исчезала и тетка оголялась.
В результате на третий день я решил 255 из 256 раскладов. Не смог решить лишь один — в котором изначально не было движения по горизонтали.

Отсюда родилась лемма, которую не смог доказать — при наличии двух степеней свободы собирается любой полный пасьянс на доске 5 на 5 и выше.

Всем удачных выходных


Спасибо за внимание, анимация котиков танцы нанайских мальчиков — исключительно мудрецам, сложившим пасьянс.
Автор: @PapaBubaDiop
Papa Buba Diop
рейтинг 32,19
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Похожие публикации

Комментарии (29)

  • +3
    Хоть это и уточнялось, но и вправду какой-то расширенный режим игры «4 комнаты» получился.
    Но идея интересная :)
  • +1
    А можно ссылку на браузерную версию? :)
    • +2
      Beg your pardon, как говорил Бильбо, ссылка откроется только тем, кто решит пасьянс номер 2015.
  • +2
    Для меня интерес к логической игре сильно падает, если она очень сильно напоминает сортировку. Тратить своё время на поиск наиболее успешного варианта по сортировке цветных квадратиков? Увольте…
    • +4
      Приношу свои извинения.
    • +2
      Согласен, это вам не блеснуть интеллектом в стрип-покере.
  • +8
    Отсюда родилась лемма, которую не смог доказать — при наличии двух степеней свободы собирается любой полный пасьянс на доске 5 на 5 и выше.

    лемма неверна, вот контрпример:
      111111
    
    2  33333 4
    2  11112 4
    2  11112 4
    2  11112 4
    2  11112 4
    2        4
    
      333333  
    
    • 0
      Три клеточки остаются, хоть ты дерись.
      image
      Сейчас еще подумаю.
    • +1
      Ха-ха-ха!
      Я решил!!!
      Моя лемма снова в силе!

      Какое решение предпочитаете — видео или ходами?

      Отличная задача! Я Вас заплюсую.
      • +1
        Хотя бы цепочку ходов до уничтожения первой клетки — было бы интересно.
        • +1

          1 — налево
          2 — направо
          3 — вверх
          4 — вниз

          Решение
          2014-12-19 18:34:39.008 b4[39286:13053487] Received ad successfully
          2014-12-19 18:35:15.586 b4[39286:13053487] Ort = 2
          2014-12-19 18:35:19.075 b4[39286:13053487] Ort = 1
          2014-12-19 18:35:20.260 b4[39286:13053487] Ort = 4
          2014-12-19 18:35:21.324 b4[39286:13053487] Ort = 2

          2014-12-19 18:35:24.103 b4[39286:13053487] Ort = 3
          2014-12-19 18:35:35.949 b4[39286:13053487] Ort = 1
          2014-12-19 18:35:40.854 b4[39286:13053487] Ort = 2
          2014-12-19 18:35:46.187 b4[39286:13053487] Ort = 4

          2014-12-19 18:35:52.824 b4[39286:13053487] Ort = 1
          2014-12-19 18:36:01.970 b4[39286:13053487] Ort = 2
          2014-12-19 18:36:03.354 b4[39286:13053487] Ort = 3
          2014-12-19 18:36:04.322 b4[39286:13053487] Ort = 1

          2014-12-19 18:36:05.379 b4[39286:13053487] Ort = 4
          2014-12-19 18:36:07.080 b4[39286:13053487] Ort = 2
          2014-12-19 18:36:09.432 b4[39286:13053487] Ort = 3
          2014-12-19 18:36:10.284 b4[39286:13053487] Ort = 1
          2014-12-19 18:36:27.384 b4[39286:13053487] Ort = 4

          2014-12-19 18:36:33.605 b4[39286:13053487] Ort = 2
          2014-12-19 18:36:37.666 b4[39286:13053487] Ort = 1
          2014-12-19 18:36:52.651 b4[39286:13053487] Ort = 3
          2014-12-19 18:36:57.553 b4[39286:13053487] Ort = 4

          2014-12-19 18:36:58.839 b4[39286:13053487] Ort = 2
          2014-12-19 18:37:02.720 b4[39286:13053487] Ort = 3
          2014-12-19 18:37:05.071 b4[39286:13053487] Ort = 1
          2014-12-19 18:37:12.440 b4[39286:13053487] Ort = 4
          2014-12-19 18:37:13.441 b4[39286:13053487] Ort = 2

          2014-12-19 18:37:17.221 b4[39286:13053487] Ort = 1
          2014-12-19 18:37:17.903 b4[39286:13053487] Ort = 3
          2014-12-19 18:37:18.752 b4[39286:13053487] Ort = 2
          2014-12-19 18:37:19.471 b4[39286:13053487] Ort = 4

          2014-12-19 18:37:20.221 b4[39286:13053487] Ort = 1
          2014-12-19 18:37:21.057 b4[39286:13053487] Ort = 3
          2014-12-19 18:37:21.912 b4[39286:13053487] Ort = 2
          2014-12-19 18:37:22.740 b4[39286:13053487] Ort = 4

          2014-12-19 18:37:23.991 b4[39286:13053487] Ort = 1
          2014-12-19 18:37:36.245 b4[39286:13053487] Ort = 2
          2014-12-19 18:37:45.110 b4[39286:13053487] Ort = 3
          2014-12-19 18:37:46.425 b4[39286:13053487] Ort = 1

          2014-12-19 18:37:51.095 b4[39286:13053487] Ort = 4
          2014-12-19 18:37:53.694 b4[39286:13053487] Ort = 2
          2014-12-19 18:37:54.699 b4[39286:13053487] Ort = 3
          2014-12-19 18:37:55.766 b4[39286:13053487] Ort = 1


          • 0
            Я так понял, что был предложен квадрат 5*5 на поле 6*6. Который можно расположить в любом из 4 углов, но квадратом он от этого быть не перестанет, и ни одна клетка не исчезнет.
            Возможно, к «степеням свободы» надо добавить какое-то уточнение (на случай прямоугольной исходной конфигурации).
            • 0
              Вы правы — я решал другую задачу. Добавлю условие в лемму — раскладом считается поле, все клетки которого не пустые. Этого достаточно.
              Кстати, в оригинале это отражено — полный квадрат подразумевает отсутствие пустых клеток при начальном раскладе. Так что все в порядке.
              • +1
                Похоже, что если в какой-то момент конфигурация ограничена некоторым прямоугольником, то её дальнейшее поведение будет таким же, как если бы всё поле имело размер этого прямоугольника. То же относится к обобщённому прямоугольнику (пересечение некоторого — не обязательно непрерывного — множества столбцов и некоторого множества строк).
      • +1
        У меня возникло подозрение, что поменяв цвет всего у 2х клеточек на вашей картинке задачу решить уже не получится (она просто станет задачей, которую на самом деле предложил zikher

        image

        Центральный квадрат будет двигаться целиком, а 2 крайних ряда уйдут без влияния на остальные клетки.

        Вроде так.
        • 0
          Основное условие леммы надо сформулировать так: существует хотя бы одна последовательность ходов, после которой занятые клетки перестанут образовывать прямоугольник.
          • 0
            поправка — инвариантный прямоугольник, то есть не меняющийся от движения в любом направлении.
            • 0
              Если прямоугольник на каждом этапе может измениться, то через несколько ходов он либо перестанет быть прямоугольником, либо полностью исчезнет. Поскольку измениться он может только за счёт исчезновения клеток.
              • 0
                Кстати, есть комбинации похожие на флаер из игры Жизнь — они несъедаемые, не четырехугольники, и повторяются каждые четыре хода, если двигаться по кругу типа влево-вверх-вправо-вниз.
        • 0
          Этот расклад решается.
          • –1
            Прошу прощения, я как обычно, забыл правый нижний квадратик сделать синим (был красным)
            Спасибо за найденный пример — он не решается.
  • +1
    Когда под андроид ждать? Заинтриговали вы меня!
  • +1
    Очень надо на андройд! Будет большой успех у определенной аудитории.

    И по поводу «нерешаемых» уровней: можно написать алгоритм обратной генерации. 4 направления, шаг 6, вполне комфортные условия для простого алгоритма:
    Генерируем псевдослучайную последовательность цифр в десятеричной системе счисления (а0,..., аN), представляем ее в виде числа A10=a0a1...aN, переводим число в 4-х систему счисления — B4, далее представляем B4 в виде последовательности цифр, берем первую, b0 — это направление, берем а0, отнимаем 4 — это кол-во мусора, (а0-b0)+i++) — шаг растущий шаг, для определение позиции мусора. Дальше так же до аN, если не хватит итераций можно увеличить кол-во знаков или наоборот уменьшить и поставить цикличный проход по массиву.
    Тонкости. Если а(0 — N)<4, то направление «пропускается», по этому отнимать b можно всегда. Головоломки будут проще, т.к. при генерации будет больше движение «туда-обратно», что создаст больше «цельных» полей. Для усложнения можно использовать изменение направления «прогона» кубиков: 0 — гоним по часовой, 1 — против, можно добавить 2 — поперек «цифербалата»…

    Ресурсов на такую генерацию будет затрачиваться значительно больше, но она будет случайной, её можно будет повторить и она должна быть «сходимой»… В теории)
  • +1
    Спасибо вам за статьи, приятно и весело читать вас)
  • +1
    Отличный автор, снова вспомнилось детство и задачи Я. И. Перельмана :)
  • 0
    Вот контрпример к любой формулировке леммы, которую я cмог себе представить:
    +-------------+
    | B B L B B L |
    | B B L B B L |
    | R R T R R T |
    | B B L R R R |
    | B B L R R R |
    | R R T R R R |
    +-------------+
    

    Здесь B,T,L,R — цвета нижней, верхней, левой и правой стенок соответственно.
    Первый ход возможен только вправо, после чего на поле остаются 3 одинаковых квадрата, разрушить которые уже не получится.
    Для поля 5*5 пример выглядит так:
    +-----------+
    | B L B L R |
    | R T R T R |
    | B L R R R |
    | R T R R R |
    | R R R R R |
    +-----------+
    

    • 0
      Да, этот расклад не сходится. Но в начальных условиях есть только 1 степень свободы, а в лемме — по условию, должно быть две.
      • +1
        Пусть будет две:
        +-------------+
        | B L B L R R |
        | R T R T R R |
        | B L R R R R |
        | R T R R R R |
        | B B B B R R |
        | B B B B R R |
        +-------------+
        

        Квадраты всё равно не разбить.
        • 0
          Блестяще! Три магических квадрата не убиваемы.

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка