General Misc > Robot Videos

Rubiks cube solving robot

<< < (3/3)

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: ---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'))

--- End code ---

Here is diabol_problem.dat

--- Code: ---? ? 5 4 ? 9 8 ? ?
2 ? ? ? ? ? ? ? ?
6 ? ? ? 5 1 ? ? 7
? ? 7 ? ? ? ? ? ?
? ? ? 3 ? ? ? ? ?
? ? ? ? 1 ? 4 ? ?
7 4 ? ? 3 ? ? ? 6
? ? ? ? ? ? ? ? ?
? ? 1 8 ? ? ? ? ?

--- End code ---

Here is diabol_region.dat

--- Code: ---((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))
--- End code ---

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.