Understand the complexity of the Rubpix game

It took me about 2 weeks to complete the Rubpix puzzles of the dimension 3x3 and 4x4 (the first 100 level), with the best move solutions. However, I immediately realize that it would probably take months to complete the rest - 6x6 and even 8x8. Why?

At first sight, this Rubpix game is indeed deceptively simple, with simply Up, Down, Left and Right movements. For the first few puzzles, you may find them solve-able, as long as you make some additional movements. However, after considering the possible sample sizes more seriously, you will immediately realize that the complexity of these kinds of puzzles has the potential to grow exponentially!
 
To start with a simpler picture, let's consider the simplest form of the Rubpix game - 3x3. Here, assume that there are 9 unique colors in the puzzle (worst case scenario), with some high school maths, you will come out with an answer that it has basically a total of "9 factorial" permutations - aka 362880 patterns! Yep. You are seeing it right - MORE THAN 300 thousands! In a worst case scenario, the solution of the puzzle could be only obtained after a total of 300 thousands moves! (with a naive move)

Of course, the developer of the Rubpix game isn't that brutal. Most of the time (from observation), the unique colors of the puzzle are usually lesser than 6. Hence, with some human's non-naive filtering, the answer can still be found after not more than 50 moves (Alright, if you take more than that, something is really wrong).

Now, back to the harder question. What if it is a puzzle of 6x6 (not to mention, the horrible 8x8 as well). Taking the example of the Rubpix puzzle Level 101, it has 36 blocks with six unique colors. So... can you guess how many unique permutations are there? There are MILLIONS! Playing this kind of game naively would claim your life!

Anyway, I will only play the rest of the Rubpix puzzles when I am free. If you have solved all of them, you have my respect!