The Python Challenge

November 6th, 2008

Python Challenge A student in my programming languages class pointed me to the Python Challenge site. It looks like a great way for someone new to Python to test her skills and learn new ones.

It’s a riddle site in the style of notpron, but one where solving each riddle requires a little bit of Python programming. The solutions are entered by changing the URL of the current page to take you to the next riddle page. The problems are “designed to be solvable by Python newcomers and yet challenging even for Python experts.”

This type of site could be a good educational tool for many subjects.

Solving Rubik’s Cube requires 25 or fewer moves

March 29th, 2008

Tomas Rokicki has written up a proof that any Rubik’s Cube configuration can be solved in 25 or fewer moves. In his paper, Twenty-Five Moves Suffice for Rubik’s Cube, Rokicki proves that there are no configurations that can be solved in exactly 26 moves. Taken with earlier results, this means that 25 movies should suffice for any solution.

“How many moves does it take to solve Rubik’s Cube? Positions are known that require 20 moves, and it has already been shown that there are no positions that require 27 or more moves; this is a surprisingly large gap. This paper describes a program that is able to find solutions of length 20 or less at a rate of more than 16 million positions a second. We use this program, along with some new ideas and incremental improvements in other techniques, to show that there is no position that requires 26 moves.”

KFC writes on the the physics arXiv blog that

“Rokicki’s proof is a neat piece of computer science. He’s used the symmetry of the cube to study transformations of the cube in sets, rather than as individual moves. This allows him to separate the “cube space” into 2 billion sets each containing 20 billion elements. He then shows that a large number of these sets are essentially equivalent to other sets and so can be ignored. Even then, to crunch through the remaining sets, he needed a workstation with 8GB of memory and around 1500 hours of time on a Q6600 CPU running at 1.6GHz.”

Rokicki is working to establish a bound of 24 moves and thinks that a bound of 20 can eventually be proved.