Rubik solving with AI

MackeY · 2006-08-28T23:18:12

After numerous tries of trying to solve a Rubik's cube with A-star, i have given it up. The cube just has to many nodes to search (40 quintillion i believe). So I decided to come here. So here is the problem: I want to solve the Rubik's cube :) with AI. I myself can do it, but i can't seem to find a way to program it. I am not looking for a best solve (<20 moves) because that requires profile tables, etc.. and you need databases for that, which I have not learned about yet. Here is how i would like the cube to be solved: -Solve the white cross; -Solve the white layer; -Solve the second layer; -Orient the Yellow edges; -Permute the Yellow corners; -Orient the Yellow corners; -Permute the Yellow edges; ==> solved. This is a beginner method to solve the rubik's cube. Now i already have the classes to represent cubepositions and how to perform moves on them to get other cubepositions. Is there anyone here who can help me with some Pseudocode to solve the two first layers (white and the middle layer)? After that, I can manage because after that you only need do some (Well known) movesequences to get to the solved position. And preferably something that is executed really fast :) . Because theoretically i can solve the cube with Dijkstra's algorithm... but then i have to search 12^20 nodes :). I think you in advance.

Artificial Intelligence Programming

Started by MackeY August 25, 2006 01:19 PM

11 comments, last by kirkd 18 years, 3 months ago

kirkd

505

August 28, 2006 11:53 AM

Nice! Could you describe the search process you used? You mention A*, but did you use any lookup tables for end moves, etc?

The paper for solving the Rubik's Cube in the shortest number of possible moves used IDA* (Iterative Deepening A*) with extensive lookup tables. I think on average they get about 17 moves. There's also a freeware program out there (I have it but don't have the link handy) that can usually get it in about 20-25.

WeirdoFu - I would love to see a GA implementation for the Rubik's Cube. I've thought about it myself and just never got around to putting down some code. Maybe one of us will get around to it one day. 8^) My biggest concern goes to your statement "you'll get a solution." I'm not absolutely certain that to be the case as I think the search space is so massive that it'll have a hard time narrowing in on a solution. I could be totally wrong, and it will just take one of us breaking down and coding it up to find out.

-Kirk

MackeY

Author

130

August 28, 2006 12:47 PM

I updated my file on the internet. Apparently i had incorporated an old RubiksCube.dll file. I don't know if it caused problems, but now it shouldn't do it anymore.