Задача наверное многим знакома. Да и вряд ли сложна для вас (в отличие от меня). Взято из книги А. Левитина. Интересно, сколько у вас времени ушло на решение этого задания.

Триомино. Триомино — элемент мозаичного заполнения в форме L, образованный тремя квадратами шахматной доски. Задача состоит в покрытии триомино шахматной доски размером 2^n (2 в степени n) на 2^n с одной вырезанной в произвольном месте клеткой. Триомино должны покрывать все клетки, за исключением вырезанной, без пропусков и перекрытий. Разработайте декомпозиционный алгоритм для решения этой задачи.

В книжке был рисунок. Так, на всякий случай, как выглядит триомино:
. . . .
. O . .
. O O .
. . . .
. . . .

Здравствуйте, kurel, Вы писали:

Без ограничения общности можно утверждать, что дырка живёт в левой нижней четверти доски (этого можно всегда добиться простым поворотом).
Для 4x4 берём заготовку

xxuu
xzzu
  zv
  vv

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

xxuu    xxuu    xxuu    xxuu
xzzu    xzzu    xzzu    xzzu
wwzv     wzv    w zv    wwzv
 wvv    wwvv    wwvv    w vv

Для 8x8 (и выше) масштабируем идею индуктивно. Берём 3 доски 4x4 (предыдущего размера) с дыркой в углу и склеиваем так

aaaabbbb
aaaabbbb
aaaabbbb
aaa  bbb
     ccc
    cccc
    cccc
    cccc

А потом запихиваем в центр ещё одну триоминку,

aaaabbbb
aaaabbbb
aaaabbbb
aaaoobbb
    occc
    cccc
    cccc
    cccc

сводя оставшуюся дырку к 4x4 (предыдущему), которую мы уже умеем заполнять с дыркой в любом месте.

Здравствуйте, kurel, Вы писали:

K>Интересно, сколько у вас времени ушло на решение этого задания.

K> декомпозиционный алгоритм.

Слишком явная подсказка. За 3-5 минут получилось так:
Разделить доску на четыре квадратных размером 2^n-1×2^n-1. Три из них полные, а одна содержит вырезанную клетку. Последнюю доску решить рекурсивным алгоритмом. У трёх полных досок вырезать по одной угловой клетки в том углу, который является общим для всех трёх досок. Вырезанное место заполняется одной фигурой триомино, а доски-без-клетки-в-углу опять же решаются рекурсивно. Ну и доска 2×2, например, решается единственным возможным способом в зависимости от положения отсутствующей клетки.

Здравствуйте, deniok, Вы писали:

если я правильно понял, то мое решение совпадает с вашим примерно.

Понимаю, что не интересно, но на всякий случай мое решение (к-ый рекурсивно "вызывает" самого себя):

Заполнить доску размером 2^n на 2^n триомино
Если размер доски 2x2,
----- то задача решается элементарно.
Иначе:
----- Делим доску на 4 части. Одна из четвертей будет иметь вырезанную клетку, три остальные не будут ее иметь.
----- Располагаем 1 триомино в центре нашей доски так, чтобы все три клетки этого триомино лежали по одной на каждой из 3 четвертинок, на которых нет вырезанной клетки.
----- Теперь мы имеем 4 под-доски (четвертинки данной доски), каждая размером 2^(n-1) на 2^(n-1) и на каждой (условно) по одной вырезанной клетке. (Условно будем считать, что клетки триомино, которое мы расположили в центре, это тоже "вырезанные" клетки).
----- Применим рекурсивно к каждой из 4 под-досок данный алгоритм



Т.е. для доски 8x8:

[-] [-] [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]
[-] (|) [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]
[-] [-] [-] [-] [-] [-] [-] [-]

--------------------------------

[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
----------------------------------
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] (|) [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]

---------------------------------

Расположим триомино в центре доски следующим образом:

[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] (|) | (|) [-] [-] [-]
----------------------------------
[-] [-] [-] [-] | (|) [-] [-] [-]
[-] (|) [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]
[-] [-] [-] [-] | [-] [-] [-] [-]


ну и для каждой из под-досок рекурсивно

Здравствуйте, watch-maker, Вы писали:

WM>Здравствуйте, kurel, Вы писали:

K>>Интересно, сколько у вас времени ушло на решение этого задания.

WM>

K>> декомпозиционный алгоритм.

WM>Слишком явная подсказка. За 3-5 минут получилось так:
WM>Разделить доску на четыре квадратных размером 2^n-1×2^n-1. Три из них полные, а одна содержит вырезанную клетку. Последнюю доску решить рекурсивным алгоритмом. У трёх полных досок вырезать по одной угловой клетки в том углу, который является общим для всех трёх досок. Вырезанное место заполняется одной фигурой триомино, а доски-без-клетки-в-углу опять же решаются рекурсивно. Ну и доска 2×2, например, решается единственным возможным способом в зависимости от положения отсутствующей клетки.

У меня точно такое же решение.
Но, к сожалению, даже с такой явной подсказкой ушло чуть ли не пару часов (решал пару месяцев назад).

K>Задача наверное многим знакома. Да и вряд ли сложна для вас (в отличие от меня). Взято из книги А. Левитина. Интересно, сколько у вас времени ушло на решение этого задания.

K>

K>Триомино. Триомино — элемент мозаичного заполнения в форме L, образованный тремя квадратами шахматной доски. Задача состоит в покрытии триомино шахматной доски размером 2^n (2 в степени n) на 2^n с одной вырезанной в произвольном месте клеткой. Триомино должны покрывать все клетки, за исключением вырезанной, без пропусков и перекрытий. Разработайте декомпозиционный алгоритм для решения этой задачи.

K>В книжке был рисунок. Так, на всякий случай, как выглядит триомино:
K>. . . .
K>. O . .
K>. O O .
K>. . . .
K>. . . .

таже штука работает и в n-мере (предыдущий вариант, n = 2). Триомино = куб 2^n без одной клетки. Требуется разбить n-мерный куб размером 2^k, в котором также нет одной клетки.
Решается аналогично.

Здравствуйте, 67108864, Вы писали:

6>Триомино = куб 2^n без одной клетки.
Только неправильно их так называть. Ведь к случаю n > 2 не подходит ни одно из двух слов, из которых состоит «триомино». Уже в трехмерном случае это будет гептакубом

Здравствуйте, kurel, Вы писали:

K>В книжке был рисунок. Так, на всякий случай, как выглядит триомино:
K>. . . .
K>. O . .
K>. O O .
K>. . . .
K>. . . .
рисунок явно не со стороной 2^n

Здравствуйте, Vain, Вы писали:

V>Здравствуйте, kurel, Вы писали:

K>>В книжке был рисунок. Так, на всякий случай, как выглядит триомино:
K>>. . . .
K>>. O . .
K>>. O O .
K>>. . . .
K>>. . . .
V>рисунок явно не со стороной 2^n

Да, вы правы. Простите, что-то тупанул тогда.