6 игр за 6 недель — игра третья

[Beltoev]

Хоть это и уточнялось, но и вправду какой-то расширенный режим игры «4 комнаты» получился.
Но идея интересная :)

[KwI]

А можно ссылку на браузерную версию? :)

[PapaBubaDiop]

Beg your pardon, как говорил Бильбо, ссылка откроется только тем, кто решит пасьянс номер 2015.

[FuN_ViT]

Для меня интерес к логической игре сильно падает, если она очень сильно напоминает сортировку. Тратить своё время на поиск наиболее успешного варианта по сортировке цветных квадратиков? Увольте…

[PapaBubaDiop]

Приношу свои извинения.

[matiouchkine]

Согласен, это вам не блеснуть интеллектом в стрип-покере.

[zikher]

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

лемма неверна, вот контрпример:

  111111

2  33333 4
2  11112 4
2  11112 4
2  11112 4
2  11112 4
2        4

  333333  

[PapaBubaDiop]

Три клеточки остаются, хоть ты дерись.

Сейчас еще подумаю.

[PapaBubaDiop]

Ха-ха-ха!
Я решил!!!
Моя лемма снова в силе!

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

Отличная задача! Я Вас заплюсую.

[Mrrl]

Хотя бы цепочку ходов до уничтожения первой клетки — было бы интересно.

[PapaBubaDiop]

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

[Mrrl]

Я так понял, что был предложен квадрат 5*5 на поле 6*6. Который можно расположить в любом из 4 углов, но квадратом он от этого быть не перестанет, и ни одна клетка не исчезнет.
Возможно, к «степеням свободы» надо добавить какое-то уточнение (на случай прямоугольной исходной конфигурации).

[PapaBubaDiop]

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

[Mrrl]

Похоже, что если в какой-то момент конфигурация ограничена некоторым прямоугольником, то её дальнейшее поведение будет таким же, как если бы всё поле имело размер этого прямоугольника. То же относится к обобщённому прямоугольнику (пересечение некоторого — не обязательно непрерывного — множества столбцов и некоторого множества строк).

[ApmeM]

У меня возникло подозрение, что поменяв цвет всего у 2х клеточек на вашей картинке задачу решить уже не получится (она просто станет задачей, которую на самом деле предложил zikher



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

Вроде так.

[Mrrl]

Основное условие леммы надо сформулировать так: существует хотя бы одна последовательность ходов, после которой занятые клетки перестанут образовывать прямоугольник.

[PapaBubaDiop]

поправка — инвариантный прямоугольник, то есть не меняющийся от движения в любом направлении.

[Mrrl]

Если прямоугольник на каждом этапе может измениться, то через несколько ходов он либо перестанет быть прямоугольником, либо полностью исчезнет. Поскольку измениться он может только за счёт исчезновения клеток.

[PapaBubaDiop]

Кстати, есть комбинации похожие на флаер из игры Жизнь — они несъедаемые, не четырехугольники, и повторяются каждые четыре хода, если двигаться по кругу типа влево-вверх-вправо-вниз.

[PapaBubaDiop]

Этот расклад решается.

[PapaBubaDiop]

Прошу прощения, я как обычно, забыл правый нижний квадратик сделать синим (был красным)
Спасибо за найденный пример — он не решается.

[zigzag8312]

Когда под андроид ждать? Заинтриговали вы меня!

[DarkVedmakl]

Очень надо на андройд! Будет большой успех у определенной аудитории.

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

Ресурсов на такую генерацию будет затрачиваться значительно больше, но она будет случайной, её можно будет повторить и она должна быть «сходимой»… В теории)

[morgreek]

Спасибо вам за статьи, приятно и весело читать вас)

[AndersonDunai]

Отличный автор, снова вспомнилось детство и задачи Я. И. Перельмана :)

[Mrrl]

Вот контрпример к любой формулировке леммы, которую я 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 |
+-----------+

[PapaBubaDiop]

Да, этот расклад не сходится. Но в начальных условиях есть только 1 степень свободы, а в лемме — по условию, должно быть две.

[Mrrl]

Пусть будет две:

+-------------+
| 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 |
+-------------+

Квадраты всё равно не разбить.

[PapaBubaDiop]

Блестяще! Три магических квадрата не убиваемы.