Society of Robots - Robot Forum

General Misc => Robot Videos => Topic started by: Admin on October 16, 2006, 10:06:53 PM

Title: Rubiks cube solving robot
Post by: Admin on October 16, 2006, 10:06:53 PM
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
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 17, 2006, 12:47:37 AM
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. ;)
Title: Re: Rubiks cube solving robot
Post by: JesseWelling on October 18, 2006, 02:42:41 AM
yea but do you have any ideas for sudoku?
My AI outlab.........sooooo fun  :P
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 18, 2006, 08:48:13 AM
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.
Title: Re: Rubiks cube solving robot
Post by: Admin on October 18, 2006, 09:39:15 AM
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!
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 18, 2006, 01:04:47 PM
:D

I left the whole robot part for others to solve; my software'll give you a list of the right values for each square, but making a bot that can read, write, and smoke is a whole different matter.

One of my metrics for quantifying where we are in robotics is what I call the "Bender Test." When we can build an autonomous humanoid robot, fueled by alcohol, which can survive indefinately by committing petty thefts, pawning the loot,  and begging to keep itself in "fuel,"  we'll be able to make a robot do anything. We've got a ways to go, but I have faith that we'll get there.  ;D
Title: Re: Rubiks cube solving robot
Post by: JesseWelling on October 18, 2006, 01:28:48 PM
you could use rollers with numbers and encoders on them... :P
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 18, 2006, 02:53:20 PM
Well, if you're just making it a robotic sudoku board capable of solving itself, I'd say it's better just to make it pure software.  The board would be cooler, perhaps, but only marginally so, and not enough to justify the extra effort.  It sounded like this was a school project, but is it a programming project or a robotics project?
Title: Re: Rubiks cube solving robot
Post by: Admin on October 18, 2006, 03:03:49 PM
hardware based looks cooler, and offers other unique challenges outside of just software . . .

if you want simplicity, you could just solve it paper and pencil  :P
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 18, 2006, 03:23:37 PM
Granted, but there are far more interesting robots to be built I think; then again, I wasn't terribly impressed with the cube solving bot either; in both cases, the mechanical challenges are certainly educational, but they don't strike me as particularly impressive. Now, if they built the solver inside-out, by making a rubik's cube into a bot capable of solving itself, that would impress me! As would a sodoku solver that actually sat solving sudoku puzzles from a book, filling in the answers with pencil. Naturally, building the bot would be an educational challenge, but no more or less than any number of other robot projects. It's just not that interesting to me, but that's entirely subjective, and others no doubt feel the same about my roachbot project.

I actually do find the idea of writing a pure software sudoku solver interesting, and might play around with it some time; I'm sure there would be some delightfully subtle complexities I completely missed in my high-level algorithm above. But that would be a weekend project with no cost, where building the bot would take many weeks and \$\$\$. Plus, people could use a software sudoku solver (if I try it, I'll probably make it web-based), while the bot would just be a novelty.
Title: Re: Rubiks cube solving robot
Post by: JesseWelling on October 18, 2006, 06:08:17 PM
Teacher just added the constraint of being "jigsaw" sudoku......

This is a clisp (maybe Ruby or Python ) AI program for an undegrad AI class.
I'll post my sloppy clisp solution when I get it done (due November 13th).
Title: Re: Rubiks cube solving robot
Post by: Gopher on October 18, 2006, 07:14:36 PM
The fact that it's a jigsaw sudoku doesn't seem to complicate things to me; it might make it trickier for a human, but I don't see how it would make things significantly harder on a computer algorithm. Unless I'm mistaken about what a "Jigsaw Sudoku" is; I think it's just a sudoku puzzle where you go by rows, columns, and irregularly-shaped "regions" instead of sub-sqares/rectangles, am I correct?

Of the options I'd go with clisp, because it is a beautiful language, but I'm wierd;  you should go with whatever language you're most comfortable with, of the options.
Title: Re: Rubiks cube solving robot
Post by: JesseWelling on November 14, 2006, 10:52:56 PM
I chose Ruby because it seemed like a good language to learn. And if you like the functionality of lisp but don't like all the parenthisis you should check it out.
And without further ado here is the ruby code using Back Tracking CSP Search and AC3
Note that the regions just defines the jigsaw regions as the rows and columns are implied as regions.

Code: [Select]
class Cell
def initialize (n)
@possible_values = Array.new(n) { |i| i + 1 }
@value = nil
end
def deep_copy
end
def is (value)
@value = value
@possible_values.clear
end
def remove_possible (number)
temp = @possible_values.delete number
throw :violation if @possible_values.length < 1 && @value == nil
return temp
end

def to_s
puts "value: #{value}"
puts "possible: #{possible_values}"
end
end

class Region
@cells_contained

def initialize
@cells_contained = Array.new
end
@cells_contained << cell
end
def cell_is_member? (cell)
@cells_contained.include? cell
end
def remove_value (value)
count = 0
@cells_contained.each { |cell| count += 1 if cell.remove_possible value }
count
end

def remove_value_plus (value)
the_cells = Array.new
count = 0
@cells_contained.each do |cell|
if cell.remove_possible value
count += 1
the_cells << cell
end
end
return count, the_cells
end

def remove_value_plus_plus (value, keep_cell)
the_cells = Array.new
count = 0
@cells_contained.each do |cell|
unless keep_cell == cell
if cell.remove_possible value
count += 1
the_cells << cell
end
end
end
return count, the_cells
end

def find_forced_values (n)
count = Array.new(n, 0)
@cells_contained.each do |cell|
cell.possible_values.each { |value| count[value - 1] += 1 }
end
i = 1
count.each do |value|
if value == 1
@cells_contained.each do |cell|
if cell.possible_values.include? i
return cell, i
end
end
end
i += 1
end
return nil, nil
end

def any_nils?
@cells_contained.each { |cell| return true if cell == nil }
nil
end

def to_s
puts @cells_contained
end
end

class Snapshot

def initialize (cells, remaining_count, index, cells_solved_count, regions, n)
@cells = Array.new

@regions = Array.new(3*n) {Region.new}
#find which regions the current cell is in.
#put the new cell in those same regions
cells.each do |cell|
@cells << new_cell = cell.deep_copy
i = 0
regions.each do |region|
if region.cell_is_member? cell
#puts "region: #{i}\t#{@cells.index(new_cell)+1}"
end
i += 1
end
end
@remaining_count = Array.new(remaining_count)
@index = index
@remaining_psbl = Array.new(@cells[index].possible_values)
#@remaining_psbl = @cells[index].possible_values
@cells_solved_count = cells_solved_count
end
def best_guess
max = 0
guess = nil
@remaining_psbl.each do |value|
if @remaining_count[value - 1] > max
max = @remaining_count[value - 1]
guess = value
end
end
guess
end
def last_choice?
@remaining_psbl.length <= 1
end
def rollback
@remaining_psbl.delete best_guess
return @cells, @remaining_count, @index, @cells_solved_count, @regions
end

def to_s
puts "remaining count: ", @remaining_count << "\nindex: " << @index
end
end

class Board
@n
@nxn
@cells
@remaining_count
@regions
@cells_solved_count

def initialize (n)
@n = n
@nxn = n * n
@cells = Array.new(@nxn) { Cell.new n }
@remaining_count = Array.new(@n, @nxn)
@regions = Array.new(@n * 3) { Region.new }
@cells_solved_count = 0
@snapshots = Array.new
end

def solved?
@cells_solved_count >= @nxn
end

def cell_is (index, value)
@cells[index].possible_values.each do |decrement_value|
@remaining_count[decrement_value - 1] -= 1
end

@cells[index].is value
ac3 index, value
@cells_solved_count += 1
end

def next_cell_to_solve
min = @n
min_cell_index = nil
running_index = 0
degree_max = 0
@cells.each do |cell|
unless cell.value
if cell.possible_values.length == 1
return running_index
elsif cell.possible_values.length < min
min_cell_index = running_index
min = cell.possible_values.length
elsif cell.possible_values.length == min
cell.possible_values.each do |value|
if @remaining_count[value - 1] > degree_max
degree_max = @remaining_count[value - 1]
min_cell_index = running_index
end
end
end
end
running_index += 1
end
min_cell_index
end

def take_snapshot (index)
@snapshots.push(Snapshot.new(@cells, @remaining_count, index, @cells_solved_count, @regions, @n))
end

def has_snapshot? (index)
unless @snapshots.empty?
return index == @snapshots.last.index
end
false
end

def rollback
@snapshots.pop if @snapshots.last.last_choice?
@cells, @remaining_count, index, @cells_solved_count, @regions = @snapshots.last.rollback
#pop the snapshot if it is the last guess
#@snapshots.pop if @snapshots.last.last_choice?
index
end

def next_guess (index)
unless @snapshots.empty?
return @snapshots.last.best_guess if @snapshots.last.index == index
end
max = 0
guess = nil
@cells[index].possible_values.each do |value|
if @remaining_count[value - 1] > max
max = @remaining_count[value - 1]
guess = value
end
end
guess
end

def find_forced
@regions.each do |region|
cell, value = region.find_forced_values @n
if cell
return @cells.index(cell), value
end
end
return nil, nil
end

def possibilities_remaining (index)
@cells[index].possible_values.length
end

def ac3 (index, value)
queue = Array.new
@regions.each do |region|
if region.cell_is_member? @cells[index]
count, modified_cells = region.remove_value_plus value
@remaining_count[value - 1] -= count
unless count == 0
queue = queue + modified_cells
end
end
end
super_pp
#puts "Moddified_cells: #{queue}"
queue.each do |d_cell|
puts "index: #{cells.index(d_cell)}"
end
until queue.empty?
cell = queue.shift
if cell.possible_values.length == 1
value = cell.possible_values.first
@regions.each do |region|
if region.cell_is_member? cell
count, modified_cells = region.remove_value_plus_plus value, cell
@remaining_count[value - 1] -= count
unless count == 0
queue = queue + modified_cells
end
end
end
end
super_pp
end
end

def remove_inconsistant (checkcell, rootcell)
if rootcell.possible_values.length == 1
if checkcell.remove_possible(rootcell.possible_values.first)
#decement count of rootcell.possible_values.first
#return true
end
end
nil
end

def neighbors (index)
queue= Array.new
@regions.each do |region|
if region.cell_is_member? @cells[index]
queue | region.cells_contained
end
end
#queue.flatten!
#queue.uniq!
queue.delete @cells[index]

queue.each do |checkcell|
checkcell << @cells[index]
end
queue
end

#puts "#{index+1}\t#{region}"
end

def to_s
i = 1
@cells.each do |cell|
if cell.value then print cell.value
else print '?'
end
if i % @n == 0 then puts
else print ' '
end
i = i.next
end
end

def super_pp
display = Array.new(35) { String.new }
col = row = 0
@cells.each do |cell|
if value = cell.value
display[row] << "   "
display[row+1] << " #{value} "
display[row+2] << "   "
else
(1..9).each do |value|
if value > 6
disp_row = row + 2
elsif
value > 3
disp_row = row + 1
else
disp_row = row
end

if cell.possible_values.include? value
display[disp_row] << "x"
else
display[disp_row] << " "
end
end
end
display[row] << "|"
display[row+1] << "|"
display[row+2] << "|"
col += 4
if col > 35
col = 0
display[row+3] ="-------------------------------------"
row += 4
end
end
display.each {|x| puts x}
end
end

def create_puzzle (board, known_file, region_file)

#strip off the other junk so you only have a space seperated list of numbers
contents.gsub!(/\n/, ' ')
contents.gsub!(/\)|\(/, '')

n = board.n
(0..n*n - 1).each do |i|
board.add_cell_to_region(i, n + (i % n))
end

n = board.n
region_index = 2 * n
contents.each_line do |line|
line.gsub(/\)|\(/, '').chomp.each(' ') do |cell_index|
end
region_index += 1
end

contents.gsub!(/\n/, '')
cell = 0
contents.each(' ') do |current|
board.cell_is(cell, current.to_i) unless current.strip == '?'
cell += 1
end
board
end

def solve_puzzle (board)
cell_index = nil
until board.solved? do
catch :violation do
until board.solved? do
still_easy_stuff = true
while still_easy_stuff && !board.solved?
cell_index, value = board.find_forced
while cell_index && !board.solved?
puts "index: #{cell_index} :forced choice"
board.cell_is(cell_index, value)
cell_index, value = board.find_forced
end
cell_index = board.next_cell_to_solve
while !board.solved? &&board.cells[cell_index].possible_values.length == 1
puts "index: #{cell_index} :only possibility"
board.cell_is(cell_index, board.next_guess(cell_index))
cell_index = board.next_cell_to_solve
end
temp_index, temp_value = board.find_forced
if !board.solved?
unless board.cells[cell_index].possible_values.length == 1 || temp_index
still_easy_stuff = false
end
end
end
if !board.solved? && board.cells[cell_index].possible_values.length > 1
#take a snapshot
unless board.has_snapshot? cell_index
board.take_snapshot cell_index
puts "snapshot pushed on index #{cell_index}"
end
#then pick a value to guess
guess = board.next_guess cell_index
puts "guess value: #{guess} at index: #{cell_index} :guessed choice"
#then assign that value
board.cell_is(cell_index, guess)
#then run ac3
end
end
end
unless board.solved?
puts "a violation has occurred."
board.super_pp
cell_index = board.rollback
puts "number of snapshots: #{board.snapshots.length}"
puts "roll back on index #{cell_index}"
end

#next cell to solve needs to be the one returned from rollback
end
#puts board
end

solve_puzzle(create_puzzle(Board.new(9), 'diabol_problem.dat', 'diabol_region.dat'))

Here is diabol_problem.dat
Code: [Select]
? ? 5 4 ? 9 8 ? ?
2 ? ? ? ? ? ? ? ?
6 ? ? ? 5 1 ? ? 7
? ? 7 ? ? ? ? ? ?
? ? ? 3 ? ? ? ? ?
? ? ? ? 1 ? 4 ? ?
7 4 ? ? 3 ? ? ? 6
? ? ? ? ? ? ? ? ?
? ? 1 8 ? ? ? ? ?

Here is diabol_region.dat
Code: [Select]
((1 2 3 4 10 11 12 13 21)
(5 6 7 8 9 15 16 17 25)
(14 23 24 33 34 35 43 44 52)
(18 26 27 36 45 53 54 62 63)
(19 20 28 29 37 46 55 56 64)
(22 31 32 40 41 42 50 51 60)
(30 38 39 47 48 49 58 59 68)
(57 65 66 67 73 74 75 76 77)
(61 69 70 71 72 78 79 80 81))

Here is a useful link for understanding the region.dat:
http://www.cs.montana.edu/courses/436/handouts/Daily_Jigsaw_060928.html

And I can't take all the credit, my partner Drake showed me alot about Ruby while I mostly worked on nuances of AC3 and other algorithms. and be warned this is the rough copy. it prints out alot of stuff for debug purposes.