General Misc > Robot Videos
Rubiks cube solving robot
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
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
#@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}"
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'))
--- 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.
Navigation
[0] Message Index
[*] Previous page
Go to full version