### Author Topic: Rubiks cube solving robot  (Read 9846 times)

0 Members and 1 Guest are viewing this topic.

#### Admin  ##### Rubiks cube solving robot
« 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

#### Gopher ##### Re: Rubiks cube solving robot
« Reply #1 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. #### JesseWelling ##### Re: Rubiks cube solving robot
« Reply #2 on: October 18, 2006, 02:42:41 AM »
yea but do you have any ideas for sudoku?
My AI outlab.........sooooo fun #### Gopher ##### Re: Rubiks cube solving robot
« Reply #3 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.

#### Admin  ##### Re: Rubiks cube solving robot
« Reply #4 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. Its all about the cool-ness factor!

#### Gopher ##### Re: Rubiks cube solving robot
« Reply #5 on: October 18, 2006, 01:04:47 PM » 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. #### JesseWelling ##### Re: Rubiks cube solving robot
« Reply #6 on: October 18, 2006, 01:28:48 PM »
you could use rollers with numbers and encoders on them... #### Gopher ##### Re: Rubiks cube solving robot
« Reply #7 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?

#### Admin  ##### Re: Rubiks cube solving robot
« Reply #8 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 #### Gopher ##### Re: Rubiks cube solving robot
« Reply #9 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.

#### JesseWelling ##### Re: Rubiks cube solving robot
« Reply #10 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).

#### Gopher ##### Re: Rubiks cube solving robot
« Reply #11 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.

#### JesseWelling ##### Re: Rubiks cube solving robot
« Reply #12 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  attr_reader :value, :possible_values  def initialize (n)    @possible_values = Array.new(n) { |i| i + 1 }    @value = nil  end  def deep_copy    Marshal::load(Marshal.dump(self))  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}"  endendclass Region  @cells_contained     attr_reader :cells_contained    def initialize    @cells_contained = Array.new  end  def add_cell (cell)    @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  endendclass Snapshot  attr_reader :cells, :remaining_count, :index    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          @regions[i].add_cell new_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  endendclass Board  @n  @nxn  @cells  @remaining_count  @regions  @cells_solved_count  @number_of_assignments_made    attr_reader :n, :cells, :regions, :remaining_count, :snapshots, :number_of_assignments_made    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    @number_of_assignments_made = 1  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    @number_of_assignments_made += 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    def add_cell_to_region (index, region)    @regions[region].add_cell @cells[index]    #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}    puts "Number of assignments made: #{number_of_assignments_made}"  endenddef create_puzzle (board, known_file, region_file) contents = IO.read 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, i / n)   board.add_cell_to_region(i, n + (i % n))  end    n = board.n  region_index = 2 * n  contents = IO.read region_file  contents.each_line do |line|    line.gsub(/\)|\(/, '').chomp.each(' ') do |cell_index|      board.add_cell_to_region(cell_index.to_i - 1, region_index)    end    region_index += 1  end    contents = IO.read known_file  contents.gsub!(/\n/, '')  cell = 0  contents.each(' ') do |current|    board.cell_is(cell, current.to_i) unless current.strip == '?'    cell += 1  end  boardenddef 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 boardendsolve_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.