?

Log in

No account? Create an account
доминошки - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

доминошки [июн. 23, 2018|04:42 pm]
Anatoly Vorobey
[Tags|]

Офигительная задачка от АП (ссылку поставлю позже, чтобы не спойлерить решение). Сложнее, чем может показаться на первый взгляд! Легко объяснить детям и подключить их к мучениям!



У Пети 8 доминошек. Он выложил их на столе в виде квадрата 4x4. Оказалось, что сумма очков в любом квадратике 2х2 равна одному и тому же числу. Нарисуйте, как лежат доминошки.

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

P.S. Режим бога: найдите кол-во фундаментально разных решений с точностью до поворотов и отражений. Эта часть опциональна и только для программистов.


Update. Раскрыл все решения. Источник задачи тут.
СсылкаОтветить

Comments:
[User Picture]From: net_smysla_net
2018-06-23 02:02 pm
в любой клетке 2х2 должна быть в сумме 14 точек
осталось разложить домино по клеточкам, чтобы соблюсти данное условие
это не сложно, простая арифметика


(Ответить) (Thread)
[User Picture]From: avva
2018-06-23 02:07 pm
Ну попробуйте.
(Ответить) (Parent) (Thread)
[User Picture]From: net_smysla_net
2018-06-23 03:02 pm
собственно вот:
хостинг для графики
на раскладывание ушло пару минут
остальные двадцать - организационные телодвижения, как то выискивание в интернете картинки с доминошками, распечатывание, разрезание, фото, заливка фото результата в сеть и вот это сообщение..))
п.с. немного ошибся, одну доминошку пришлось развернуть, в правом верхнем углу

Edited at 2018-06-23 15:09 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2018-06-23 03:23 pm
Неплохо, но нет, средний левый квадратик в сумме 12.
(Ответить) (Parent) (Thread)
[User Picture]From: net_smysla_net
2018-06-23 03:28 pm
верно
поправил
Разместить фото
(Ответить) (Parent) (Thread)
[User Picture]From: net_smysla_net
2018-06-23 03:43 pm
я не программист, вариантов решения насчитал шесть
но не особо старался, правда
их может быть больше
(Ответить) (Parent) (Thread)
[User Picture]From: vba_
2018-06-23 03:08 pm
Поскольку в каждом квадрате сумма очков 14, то задача довольно быстро решается простым подбором. Начнем выкладывать первые два столбца. Ясно, что косточка 6:3, которая отбирает сразу 9 очков, должна стоять в углу (причем, в углу дорогая шестерка) и к ней же должна примыкать пустышка. Положим 6:3 в верхний левый угол горизонтально (первый ряд). Пустышка примыкает к шестерке. Рядом с пустышкой должна быть (14-6-3) пятерка. Кости 5:0 нет, значит, надо ставить вертикально в крайнем левом столбце 0:6 и рядом (второй столбец) 5:3, чтобы сумма очков третьего ряда была равна сумме очков первого ряда. Дальше все довольно тривиально.

6:3 4 2
0 5 2 6
6 3 4 2
1:4 3 5

Все кости стоят вертикально, кроме кости 6:3 в верхнем левом углу и кости 1:4 в левом нижнем углу.
(Ответить) (Thread)
[User Picture]From: petrazmus
2018-06-23 03:12 pm
А имеет ли задача решение?
Всего очков в игре 56, количество квадратов 2Х2 в этом пространстве 9. Т.е. сумма в каждом квадрате 56/9=6.2222
Где-то ошибся?
(Ответить) (Thread)
[User Picture]From: avva
2018-06-23 03:21 pm
Да, квадраты пересекаются, поэтому это деление не имеет смысла. Возьмите четыре непересекающихся квадрата и получите сумму в каждом из них (и пяти остальных).
(Ответить) (Parent) (Thread)
From: karpion
2018-06-23 04:19 pm
Ну, часть задачи сделана: общая сумма очков известна.
Четыре непересекающихся квадрата дают нам "14 очков в каждом квадрате".

Дальше надо пронумеровать ячейки. Допустим, так:
A1 A2 A3 A4
B1 B2 B3 B4
C1 C2 C3 C4
D1 D2 D3 D4


Дальше пишем уравнения:
A1 + A2 + B1 + B2 = 14
A2 + A3 + B2 + B3 = 14
...

откуда следует
A1 + B1 = A3 + B3
и аналогично для других случаев.
(Ответить) (Parent) (Thread)
[User Picture]From: garconnumeroun
2018-06-23 03:25 pm
Например:

--------
6 3|4 2|
--------
0|5|2 6|
| |----
6|3|4|2|
---| | |
1 4|3|5|
--------
(Ответить) (Thread)
[User Picture]From: gray_bird
2018-06-23 03:30 pm
ЫЫЫЫ!
Из условия сначала не понял, имеется ввиду сумма действительно в ЛЮБОМ квадрате 4х4, а не в четырех квадратах прилежащих к углам.
Че та совсем сложно!
(Ответить) (Thread)
[User Picture]From: lu_in_pampas
2018-06-23 07:02 pm
(Ответить) (Thread)
[User Picture]From: kostya_h
2018-06-23 07:14 pm
(Если домино отсчитывать по горизонтали) 1 квадрат — 1 костяшка со второй; 2 квадрат — 3 с 7; 3 квадрат — 4 с 6; 4 квадрат — 5 с 8.
Или я неправ и есть какой-то подвох в условии, или задача довольно проста оказалася (без режима бога).
(Ответить) (Thread)
[User Picture]From: slonopas
2018-06-23 07:25 pm
(Ответить) (Thread)
From: sureguef
2018-06-23 07:56 pm

5 1-4 3
|     |
2 6 3 4
  | |
6 0 5 2
|     |
2 6-3 4


Хорошая задачка, спасибо. Помогает смотреть на четности.
(Ответить) (Thread)
[User Picture]From: _magvay_
2018-06-24 02:09 am
Хорошая задачка!

(Ответить) (Thread)
[User Picture]From: janatem
2018-06-24 10:20 am
> Эта часть опциональна и только для программистов.

Хм, почему только для программистов? Мне попадалась задачка, которая позиционировалась как для программистов, но по факту ее можно решить без утомительного перебора. Вот такая:
Найти число, состоящее из девяти цифр (все от 1 до 9 по разу), удовлетворяющее следующему свойству. Если взять первые n цифр числа, то полученное число должно делиться на n (для всех n от 1 до 9).
(Ответить) (Thread)
[User Picture]From: son_0f_morning
2018-06-24 01:55 pm

Что ж вы делаете-то!

Вчера вечером прочитал ваш пост -- три часа не мог уснуть!!!

Сегодня встал посмотрел:
- 16 чисел (связями в костяшках домино пока пренебрегаем).
- 9 независимых уравнений (9 квадратов)
- не хватает 7и.

Задаём 7 чисел (любых), для определённости
a4, b4, c4, d4, d3, d2, d1 (в шахматной нотации) -- они дадут недостающие 7 уравнений.

Тогда (мы пока не учитываем домино) у нас есть:
1. С(16, 7) = 16! / (7! * 9/!) = 11440 вариантов разложить стартовые 7 чисел.
57 657 600 -- вариантов выбрать 7 чисел из 16, с учётом порядка (без учёта связей внутри домино).
2. Они однозначно определяют остальные 9 чисел (проверка, что множество получаемых чисел совпадает с мн-ом на костяшках).
3. Если (2) совпало -- пытаемся разложить костяшки.

ПС
осталось написать программу.

Edited at 2018-06-24 14:33 (UTC)
(Ответить) (Thread)
[User Picture]From: lu_in_pampas
2018-06-25 07:00 pm
Опубликуйте, пожалуйста, ссылку на задачу про домино. Очень хочется посмотреть уже на правильное решение (точнее как до него догадаться).
(Ответить) (Thread)
[User Picture]From: avva
2018-06-26 07:50 am
Открыл все комментарии, тут есть много правильных ответов. Оригинал задачи был в Фейсбуке тут

https://www.facebook.com/photo.php?fbid=2212238878816617&set=a.410796888960834.91756.100000915789645&type=3&theater
(Ответить) (Parent) (Thread)
[User Picture]From: son_0f_morning
2018-06-25 07:03 pm

Нашёл 140 неуникальных, но похоже ответ не верный.

Полным перебором, с критерием отсечения, нашёл 140 решений.
Сейчас еду и не понимаю где ошибка (почему не делится на 8: 2_отражения * 4_поворота)

Искал, с точностью до земощений (т.е. индексировал половинки костяшек), а не цифр.


ПС
Делал как в комментарии выше -- из соображений производительности (т.к. было понятно, что будет "быстрое" с вычислительной точки зрения отсечение на ранних этапах).
Некоторые забавные цифры (заодно):

1. Выбираем 7 позиций "половинок" домино (из 16) и размещаем их на заведомо выбранные позиции:
- count = 16! / 7! = 57657600

2. Расставляем эти 7 чисел, и считаем остальные 9 (как на картинке выше).
- count_after_sum = 105120
требуем, чтобы число 0й, 1к, 2к, 3к...6к было ровно тем же что и в нашем наборе домино.

3. Делаем замощение доски "обязательными" доминошками (т.е. теми, которые содержат выбранные "половинки"). Тут сразу 2 фильтра:
- физическое замощение доминошками без наложений и "разрезов" -- 11676 (вариантов)
- цифры при замощении совпадают с предрассчётом (из п2) -- 508

4. Производим замощение оставшихся пустых клеток, и сразу смотрим на правильные цифры на костяшках
FIND = 140 (это число, включает 4 поворота 0, pi/2, pi, 3*pi/2)



Edited at 2018-06-25 20:05 (UTC)
(Ответить) (Thread)
[User Picture]From: avva
2018-06-26 08:03 am

Re: Нашёл 140 неуникальных, но похоже ответ не верный.

Нет сейчас времени вникать в ваш путь, извините, но могу рассказать, как моя программа работает. Она нашла 48 уникальных решений, точнее 48*8 неуникальных, а /8 из соображений поворотов и отражений я сделал сам, но программой не проверял. Я не уверен на 100%, что программа правильная и я все решения нашел.

Есть рекурсивный вызов iterate(board, tiles) где board - частично заполненная числами доска 4x4, пустые клетки -1, а tiles - набор еще не использованных доминошек. Вначале она сразу вызывает функцию partially_valid, которая проверят суммы всех 2x2 квадратов, которые уже полностью заполнены, и если где-то сумма не 14, вываливается. Далее, если доминошек не осталось, мы нашли решение, печатаем и выходим. Если остались, то функция находит набор пустых мест, куда можно поставить следующую доминошку (тут есть тонкость, см. ниже), и в цикле
пробует а) каждое место б) каждую из оставшихся доминошек в) две ее ориентации, и вызывает себя рекурсивно.

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

Набор пустых мест-кандидатов это тонкое место.
- Если пробовать все места, то будет очень долго, потому что мы кучу раз будем повторять одни и те же рассчеты (приходя к одинаковой позиции расстановкой двух доминошек в разном порядке).
- От этого можно избавиться хранением глобального хэша уже попробованных позиций, и не идти в них, но тогда обязательно надо расположение доминошек на доске сделать частью состояния доски, потому что одни и те же числа с разным набором - это две разные позиции. В принципе можно это сделать и возможно будет быстрее моего пути.
- Следующая идея - пробовать только одно, самое первое найденное, пустое место для доминошки - а все остальные попробуем внутри его рекурсии. Это пропускает решения, потому что если мы заняли место доминошкой, мы уже никогда не попробуем ставить доминошки в места, частично пересекающие это.
- Поэтому я в конце концов сделал так. Обходим доску и ищем все пустые пары клеток, горизонтальные и вертикальные. Добавляем каждую такую пару в список кандидатов, но каждый раз проверяем те, что уже есть в списке, и вновь найденная пара должна пересекать каждую из уже имеющихся в списке. Только тогда мы обязаны проверить ее на этом уровне рекурсии, и добавляем в список кандидатов. На практике это означает что в списке не более 2-4 кандидатов почти всегда.

Все программа на питоне работает где-то минуту.
(Ответить) (Parent) (Thread)
[User Picture]From: son_0f_morning
2018-06-26 08:26 am

RE: Re: Нашёл 140 неуникальных, но похоже ответ не верный.

Извините тоже несколько нет времени вникать. Поясните такой момент: зачем размещать доминошку во все свободные клетки, когда можно плмещать асе доминошки в 1 очередную свободную клетку?

На 1й взгляд этот путь предпочтительнее тем, что он чуть проще и можно ограничить перебор эффективнее
(Ответить) (Parent) (Thread)
[User Picture]From: son_0f_morning
2018-06-26 10:11 am

RE: Re: Нашёл 140 неуникальных, но похоже ответ не верный.



Чисто технически у нас есть структура path, описывающая вот такой путь:
struct one_step {
int x;
int y;
int need_check;
} path[COUNT + 1] = {{1, 1, false}, {2, 1, false}, {1, 2, false}, {2, 2, false},
{3, 1, true}, {3, 2, false},
{4, 1, true}, {4, 2, false},
{1, 3, true}, {2, 3, false},
{3, 3, true},
{4, 3, true},
{1, 4, true}, {2, 4, false},
{3, 4, true},
{4, 4, true},
{0, 0, true}};

И рекурсивная функция
void step(index) // на шаге index мы проверяем path[index]
/**
* Структура path[] -- задаёт путь, покрывыющий за 16 шагов всю достку.
* На каждом шаге path[index] у нас есть координаты клетки (x, y) и флаг need_check.
*
* 1. Если требуется проверка (т.е. на предыдущем шаге мы замостили новый квадратик 2х2) проверяем
* 2. Если у нас 17й шаг -- всё решение есть (check_all -- так на всякий случай).
* 3. Если у нас клетка path[index].(x,y) -- уже заполнена, переходим к следующему шагу
* 4. Пытаемся заполнить текущую клетку всеми возможными доминошками во всех возможных положениях
* (это по 4 положения на доминошку, т.к. левая и верхняя клетки по определению заполнены).
*/



Edited at 2018-06-26 11:16 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: son_0f_morning
2018-06-26 11:00 am

RE: Re: Нашёл 140 неуникальных, но похоже ответ не верный.

ПС.
Собственно да считает (правда это pure C, так что с питоном сравниваться нечестно).
count -- число вхождений в рекурсивную ф-ию step
count_put_domino -- число попыток "выложить" доминошку на достку.



FIND = 384; count=510428, count_put_domino=415364
step= 0: input_count= 1 (after_check= 1, left=100%
step= 1: input_count= 32 (after_check= 32, left=100%
step= 2: input_count= 464 (after_check= 464, left=100%
step= 3: input_count= 896 (after_check= 896, left=100%
step= 4: input_count= 11200 (after_check= 1600, left=14%
step= 5: input_count= 14336 (after_check= 14336, left=100%
step= 6: input_count= 99768 (after_check= 11812, left=11%
step= 7: input_count= 21668 (after_check= 21668, left=100%
step= 8: input_count= 51336 (after_check= 8730, left=17%
step= 9: input_count= 46702 (after_check= 46702, left=100%
step=10: input_count= 161252 (after_check= 20258, left=12%
step=11: input_count= 73353 (after_check= 9867, left=13%
step=12: input_count= 18836 (after_check= 2552, left=13%
step=13: input_count= 3860 (after_check= 3860, left=100%
step=14: input_count= 4322 (after_check= 1383, left=31%
step=15: input_count= 2018 (after_check= 384, left=19%
step=16: input_count= 384 (after_check= 384, left=100%


real 0m0.028s
user 0m0.024s
sys 0m0.004s
konstantin@konst:~/my/prog/domino$


Edited at 2018-06-26 13:16 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: son_0f_morning
2018-06-26 11:03 am

мат + программа vs программа.

Вывод из этой истории интересный:

Не всегда решение "матиматика + программирование" оказывается эффективным.
Решение "чисто программерское" -- оказалось намного эффективнее (в 3 раза по коду, примерно "в 10 раз проще", в 500 раз по производительности).

Причина -- ранние отсечения было намного проще вставлять в "программерскую" архитектуру, чем в "математическую"

(Ответить) (Thread)