{
    \parindent=1cm
    \begin{tabular}{l@{\extracolsep{1cm}}l}
         Идея: & Георгий Корнеев \\
         Разработка: & Нияз Нигматуллин \\
     \end{tabular}
}

Для решения задачи будем пытаться двигать кубик, в котором изначально неизвестны цвета по полю, постепенно раскрашивая стороны кубика.

Так как нам надо учесть все возможные варианты путей и раскрасок, построим следующий граф. Вершинами в нём будут тройки $\langle \mathit{cube}, i, j \rangle$, где $\mathit{cube}$~--- последовательность из шести цветов кубика, либо специального значения, которое обозначает, что цвет неизвестен, а $(i, j)$~--- координаты клетки, в которой мы находимся. Запретим вершины, в которых цвет нижней грани кубика неизвестен или не совпадает с цветом клетки $(i, j)$. Рёбра из вершины~--- движения вверх или влево. 

Далее можно запустить обход в ширину или в глубину из финишной клетки $(n, n)$, чтобы движениями влево и вверх добраться до клетки $(1, 1)$. 

Если с какой-то раскраской кубика мы смогли это сделать, то полученная раскраска~--- это ответ.

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

Можно доказать, что число вершин в таком графе~--- $O(n^4)$, так как можно показать, что число различных состояний кубика~--- $O(n^2)$. Если рассмотреть состояния, в которых только 4 грани из 6 с известным цветом:

\begin{enumerate}
\item \textit{(2 оставшиеся грани имеют общую сторону)} Используя только эти грани, можно посетить $O(1)$ клеток, вариантов для пятого цвета~--- $O(1)$, варианты для шестого цвета можно ограничить $O(n^2)$;
\item \textit{(2 оставшиеся грани противоположны)} Используя эти грани, можно добраться только до клеток одной строки или столбца. Вариантов для пятого цвета~--- $O(n)$, вариантов для шестого цвета в дальнейшем тоже $O(n)$.
\end{enumerate}