Rubiks cube solving robot

[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 

[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. 

Its all about the cool-ness factor!

[Gopher]

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]

you could use rollers with numbers and encoders on them...

[Gopher]

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]

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]

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]

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]

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]

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}"
  end
end


class 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
  end
end


class 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
  end
end


class 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
    [email protected] 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}"
  end
end


def 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
  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.