He spent the next month coming up with an algorithm to solve it, not knowing if such an algorithm was even possible.

After he sold the puzzle, he traveled around to various conferences, to prove it could be solved.

The above makes everything sound very intentionally done towards the end result. He came about making the cube for finding ways to tackle the engineering challenge of building a device which moves in such levels if freedom, ended up scrambling it, and then spent a month figuring out how to treat the scrambled state as a puzzle to be solved. Messing with it gave him insight into just how complex a puzzle it was and the rest goes from there.