Супер си се сетил с матрицата да си следиш да не се захапе змията. :) Това, което остава е за всяка генерирана поредица да генерираш и нейните възможни варианти при ротации/флипове. Най-лесно това става като работиш със стрингове, а не да ротираш/флипваш цели матрици. Например, SRRD при хоризонтален флип става SRRU (просто обръщаш U с D и обратно). Ротация по часовниковата стрелка е на същия принцип, само че там посоките се променят така - R -> D, L -> U, D -> L, U -> R.

Всички възможни флипове/ротации на 1 поредица ги вкарваш в един HashSet<string>. Когато генерираш нова поредица и нейните флипове/ротации -> проверяваш дали вече няма такава в хешсета. И това работи, но дава само за 50/100, защото при достатъчно голямо n програмата заспива.

И тука идва моментът как да оптимизираме:

След достатъчно рисунки забелязваме, че за почти всяка 1 поредица генерираме още 8 чрез ротации/флипове. Почти всички от тях са дубликати по условие и е излишно да въртим през тях. Затова извикваме първоначално GenSnake от SR... нататък (змията SR е началото на рекурсията). Така си спестяваме генерирането на SU..., SL... и SD... змии, които и без това не ни трябват (задраскани са в картинката).

От тук нататък единствения друг вариант, който генерираме е хоризонтален флип на текущия (напр. SRRU -> SRRD). Защо? Защото само до него можем да достигнем, когато генерираме змии, започващи с SR...

До момента да обобщим: когато генерираме 1 редица, генерираме и флипнатия вариант. Ако в хешсета вече съществува 1 от двете -> редицата се дублира и нищо не правим. В противен случай, добавяме и вариантите на текущата редица в сета и я принтираме.
---------
Остана още едно нещо - възможно е да генерираме поредици като SRDD (дублира се с SRRU). Обаче от SRRU само с ротации/флипове не можем да стигнем до SRDD. Причината е, че взимаме предвид началото S и посоките, в които се движим. По условие обаче това са 2 еднакви поредици. 

• Как от SRRU получаваме SRDD тогава? Обръщаме реда на на SRRU и получаваме SDLL (виж картинката). След този reverse имаме вариант, получен в следствие на ротации на SRDD. Затова ротираме получената фигура надясно (по часовниковата стрелка), докато тя не започва с SR... (Защо? Защото само тогава ни интересува. Контрапример: ако я добавим като SDLL тя е недостижима от текущото генериране на змии).

И в крайна сметка, освен оригиналния и флипнатия, запазваме и този reversed вариант. Това са трите варианта, които ни интересуват за всяка една змия, когато тя започва с SR... Всички останали са ненужни.

Като цяло доста трябва да се порисува, за да се схване идеята. Ако не е станало ясно, пишете да доразяснявам. И ако някой има по-добър/оптимален алгоритъм, нека споделя. :)