General Misc > Robot Videos

Rubiks cube solving robot

(1/3) > >>

Admin:
Ok so solving the Rubiks cube is generally a boring nerdy thing, with few if any real life applications . . .

But this robot definitely gets full points for coolness factor!

Nice robot arm manipulation, computer vision, pneumatics and solenoids . . .

The robotic voice and music - a nice touch!

the video
http://www.youtube.com/watch?v=jkft2qaKv_o

Gopher:
Yeah, I saw that a few days ago; mechanically it is quite cool, though the software is far simpler than you'd probably expect. Solving the cube is mostly about patterns, with the fastest methods requiring a good amount of 3d visualization and pattern recognition. Tough for a human to do quickly, but the entire pattern is easily defined as an array of matrices, so in software it's fairly trivial.

I know how to solve a 3x3 and 4x4 cube myself; very nerdy, and proud of it. ;)

JesseWelling:
yea but do you have any ideas for sudoku?
My AI outlab.........sooooo fun  :P

Gopher:
Hmm, never thought about a sudoku solver before, lemme think....

I'd probably represent the grid with a group of cells. Each cell contains some set of information. Each grid square is represented with an array of every possible number for that square. To start with, I'd create a complete 9x9 grid with every square containing an array from 1 to 9. Then every given value is added one at a time. When fixing a cell to a given value, the following process is followed:

1) go to that cell and remove all values but the known value
2) for each cell in the same row, column, and 3x3 square...
2.1) remove the number from their list, if it is present
2.2) if the cell has only one number remaining, add it to the end of the Known Value queue


While there are numbers in the "known queue," pop the top one and repeat the above process. When the known queue is empty, you use other rules to solve for more cells. The above rules will ensure that no rows, columns, or cells have only one empty cell (or 2.2 would have added them to the KVQ), so no need to recheck that.

Next thing to do seems to me to be looking for the most limited possibilities. ex: If a row, col, or cube contains only one cell with 9 as a possibility, then that cell must be a nine and can be added to the KVQ. 
When no more cells meat that criteria, we extend that rule. If a row/col/box contains only two cells which have 8 and 9 as possibilities, those cells must be 8 and 9, and all other possibilities can be removed from them.

This would probably solve most puzzles by itself; some of the hardest puzzles would probably break it, though. So at that point, I'd start an exhaustive brute-force solution.

Generate a list of cells, sorted with the cells with the lowest number of possibilities first. Staring from the top, just make a guess, pushing the current status to a stack before inserting each guess. Apply the effects of each guess the same way you applied items from the KVQ. If a guess leads to an impossible situation (no possibilities remain for any single cell) then pop the previous state back off the stack, remove the failed guess from the cell's possibilities and try the next guess.  Otherwise resort the remaining cells and make the next easiest guess.

That's a rather high-level explanation, but with a good foundation in dynamic data structures it could be implemented without too much difficulty.

Admin:
The sudoku robot must also have red eyes and steam that comes out of its ears when it solves the problem.  :P

Its all about the cool-ness factor!

Navigation

[0] Message Index

[#] Next page