Fact I learned today: the question of whether an nxnxn Rubik's cube in a scrambled state can be solved in fewer than k moves is NP-complete. If you don't know or remember what it means to be NP complete, I wrote a post here in the math thread about it. Short version: if someone hands you a scrambled cube and tells you "here's how to solve it in fewer than k moves", you can verify that easily. But to figure out whether there is a solution in fewer than k moves is hard. So there is a formal, mathematical sense in which solving a Rubik's cube is in fact hard, although like with many NP-complete problems, you're usually not looking at the general case so the NP-completeness is irrelevant. This is an interesting problem, given that there is a method that will solve a Rubik's cube in O(n2/log(n)) time, i.e. there is some fixed positive constant C such that it never takes more than Cn2/log(n) moves to solve an nxnxn Rubik's cube. But telling whether a Rubik's cube can be solved in fewer moves than that is NP-complete.