тетрис задачка
24. November, 2008 – 9:59 pmПреди няколко дни се зарибих по TetriNET, случайно подслушах един определен бургазлия да споменава за играта, реших да си изтегля клиент и да поцъкам – с две думи multiplayer версия на tetris =] може тия дни да напиша по-подробно за самата игра, но сега искам да обясня какво ме мъчи цял ден.
Сигурно повечето от вас са забелязали, че в класическия тетрис всички фигури се състоят от точно четри квадратчета. Има точно седем уникални фигури(и техните ротации по/срещу часовниковата стрелка). От тези седем три са по-интересни, защото нямат огледален вариант, такива фигури наричам автосиметрични(малко или повече си я измислих тази дума…).
Това което ме мъчи, колко уникални фигури могат да се направят с n квадратчета ? Предполагам, че въпроса вече е бил разискван, но все пак на мен ми стана бая интересно. Нарисувах си всички фигури до n = 5, имам и голяма част от тези за n = 6, може би всичките. За да открия някакви зависимости, почнах да деля фигурите на класове [k] спрямо това от колко квадрата се състои най-дългата линия в съответната фигура. Първите два класа се оказаха съвсем лесни – [n] винаги съдържа един елемент, а [n-1] съдържа n-1 елемента.
Ако някой може да открие някаква закономерност или да ми даде поне идеи, бих го оценил дълбоко. Мина ми през ума че мога да представя фигурите като n x n матрици, ама ме мързи и се надявам да има някакво по-лесно решение.
Това сега са всички класове, които съм събрал досега, първите няколко класа съдържат само автосиметрични фигури, след това съм боядисал въпросните в червено та да се отличават. Ако някой открие неточности, моля да си каже 
n = 1 :
[k=1]
n = 2 :
[k=2] 
n = 3 :
[k=3] 
[k=2] 
n = 4 :
[k=4] 
[k=3] 
[k=2] 
n = 5 :
[k=5] 
[k=4] 
[k=3] 
[k=2] 
n = 6 :
[k=6] 
[k=5] 
[k=4] 
[k=3] 
[k=2] 
Няколко месеца по-късно: http://en.wikipedia.org/wiki/Polyomino