class Sudoku

Sudoku.rb

Created on September 23, 2013

Public Class Methods

new(*args) click to toggle source
# File lib/phg_sudoku_solver.rb, line 20
def initialize (*args)
  @total_iterations = 0
  @max_iterations = 100000
  @debug = false
  @cells = Array.new(9) { Array.new(9) }

  if args.size==1
    (0..8).each { |row|
      if args[0][row].is_a?(String)
        (0..8).each { |col|
          val = args[0][row][col]
          if /[0-9]/.match(val)
            @cells[row][col] = Cell.new(val.to_i)
          else
            @cells[row][col] = Cell.new()
          end
        }
      end
    }
  elsif args.size==0
    (0..8).each { |row|
      (0..8).each { |col|
        @cells[row][col] = Cell.new()
      }
    }
  end
  unless self.validate_sudoku
    raise Exception.new('Sudoku entered appears to be invalid.')
  end
end

Public Instance Methods

add_possible_value(row, col, val) click to toggle source
# File lib/phg_sudoku_solver.rb, line 71
def add_possible_value(row, col, val)
  @cells[row][col].add_possible_value(val)
end
check_col_value(row, col, val) click to toggle source
# File lib/phg_sudoku_solver.rb, line 286
def check_col_value(row, col, val)
  result = true
  (0..8).each { |r|
    if r!=row
      if @cells[r][col].get_fixed_value()==val
        result = false
      end
    end
  }
  result
end
check_matrix_value(row, col, val) click to toggle source
# File lib/phg_sudoku_solver.rb, line 298
def check_matrix_value(row, col, val)
  result = true
  row_start = (row/3).floor * 3
  col_start = (col/3).floor * 3
  (row_start..row_start+2).each { |y|
    (col_start..col_start+2).each { |x|
      unless row==y and col==x
        if @cells[y][x].get_fixed_value()==val
          result = false
        end
      end
    }
  }
  result
end
check_row_value(row, col, val) click to toggle source
# File lib/phg_sudoku_solver.rb, line 274
def check_row_value(row, col, val)
  result = true
  (0..8).each { |current_column|
    if current_column!=col
      if @cells[row][current_column].get_fixed_value()==val
        result = false
      end
    end
  }
  result
end
compute_possible_values() click to toggle source
# File lib/phg_sudoku_solver.rb, line 248
def compute_possible_values

  (0..8).each { |r|
    (0..8).each { |c|
      if @cells[r][c].get_fixed_value()<=0
        @cells[r][c].reset_possible_values()

        (1..9).each { |possible_value|
          if check_row_value(r, c, possible_value) and check_col_value(r, c, possible_value) and check_matrix_value(r, c, possible_value)
            add_possible_value(r, c, possible_value)
          end

        }
        if @cells[r][c].get_possible_values().count==1
          fixed_val = @cells[r][c].get_possible_values()[0]
          @cells[r][c].set_fixed_value(fixed_val)
          print_debug 'Resetting possible values...'
          @cells[r][c].reset_possible_values()
        elsif @cells[r][c].get_possible_values().count>1
          @cells[r][c].set_fixed_value(-1)
        end
      end
    }
  }
end
copy() click to toggle source
# File lib/phg_sudoku_solver.rb, line 342
def copy
  s = Sudoku.new()
  (0..8).each { |r|
    (0..8).each { |c|
      copied_cell = @cells[r][c].copy
      s.set_cells(r, c, copied_cell)
    }
  }
  s.set_max_iterations(@max_iterations)
  s.set_total_iterations(@total_iterations)
  s.set_debug(@debug)
  s
end
count_fixed_cells() click to toggle source
# File lib/phg_sudoku_solver.rb, line 130
def count_fixed_cells
  fixed_cell_count=0

  @cells.each() do |row|
    row.each() do |cell|
      fixed_cell_count = fixed_cell_count + 1 if cell.get_fixed_value != -1
    end
  end
  fixed_cell_count
end
dump_known_cells_str() click to toggle source
# File lib/phg_sudoku_solver.rb, line 464
def dump_known_cells_str

  result = '\n'
  for row in (0..8)
    (0..8).each do |col|
      if @cells[row][col].get_fixed_value() > 0
        val = @cells[row][col].get_fixed_value()
      else
        val = ' '
      end
      result+='%3s ' % val
      if col == 2 or col == 5
        result+= '| '
      end
    end
    if row==2 or row==5
      result+= '\n----------------------------------------\n'
    else
      result+= '\n'
    end
  end
  result
end
dump_to_str() click to toggle source
# File lib/phg_sudoku_solver.rb, line 437
def dump_to_str
  if @debug
    print '\n'
    (0..8).each { |row|
      (0..8).each { |col|
        printf('   %3s     | ' % @cells[row][col].get_fixed_value())
        if col == 2 or col == 5
          print '| '
        end

      }
      print '\n'
      (0..8).each { |col|
        array = @cells[row][col].get_possible_values()
        if array==[]
          array = '--'
        end
        printf(' %10s  ' % array)
        if col == 2 or col == 5
          print '| '
        end
      }
      print '\n\n'
    }
  end
end
find_col_implied_values() click to toggle source
# File lib/phg_sudoku_solver.rb, line 177
def find_col_implied_values
  (1..9).each { |i|
    (0..8).each { |c|
      fixed_count = 0
      variable_count = 0
      temp_row = -1
      temp_col = -1
      (0..8).each { |r|
        if @cells[r][c].get_fixed_value()==i
          fixed_count+=1
        end

        (0..@cells[r][c].get_possible_values().count).each { |j|
          if @cells[r][c].get_possible_values()[j]==i
            variable_count+=1
            temp_row = r
            temp_col = c
          end
        }

      }
      if (fixed_count==0) and (variable_count==1)
        @cells[temp_row][temp_col].set_fixed_value(i)
      end

      if fixed_count>1
        raise('Duplicate fixed value in column check.  Make sure you entered correct values.')
      end
    }
  }
end
find_matrix_implied_values() click to toggle source
# File lib/phg_sudoku_solver.rb, line 209
def find_matrix_implied_values
  # In each sub-matrix we check for implied values (i) one at a time...
  [0, 3, 6].each { |row_start|
    [0, 3, 6].each { |col_start|
      (1..9).each { |i|
        temp_row = 0
        temp_col = 0
        fixed_count = 0
        variable_count = 0
        (row_start..row_start+2).each { |r|
          (col_start..col_start+2).each { |c|

            if @cells[r][c].get_fixed_value()==i
              fixed_count+=1
            end

            (0..@cells[r][c].get_possible_values().count).each { |j|
              if @cells[r][c].get_possible_values()[j]==i
                variable_count+=1
                temp_row = r
                temp_col = c
              end
            }
          }
        }

        if (fixed_count==0) and (variable_count==1)
          @cells[temp_row][temp_col].set_fixed_value(i)
        end

        if fixed_count>1
          raise('Duplicate fixed value in matrix check.  Make sure you entered correct values.')
        end
      }
    }
  }
end
find_row_implied_values() click to toggle source
# File lib/phg_sudoku_solver.rb, line 141
def find_row_implied_values

  (1..9).each { |i|
    (0..8).each { |r|
      fixed_count = 0
      variable_count = 0
      temp_row = -1
      temp_col = -1
      (0..8).each { |c|
        # Start by counting up fixed values for the given number i.  (e.g. How many of i do we have?)
        if @cells[r][c].get_fixed_value()==i
          fixed_count+=1
        end

        #  We are checking to see if there is only one i in the possible values for this row.
        #  If so, then we will set the fixed value in the cell contains it.
        (0..@cells[r][c].get_possible_values().count).each { |j|
          if @cells[r][c].get_possible_values()[j]==i
            variable_count+=1
            temp_row = r
            temp_col = c
          end
        }

      }
      if (fixed_count==0) and (variable_count==1)
        @cells[temp_row][temp_col].set_fixed_value(i)
      end

      if fixed_count>1
        raise('Duplicate fixed values in row check.  Make sure you entered correct values.')
      end
    }
  }
end
get_cells() click to toggle source
# File lib/phg_sudoku_solver.rb, line 51
def get_cells
  @cells
end
get_fixed_value(row, col) click to toggle source
# File lib/phg_sudoku_solver.rb, line 59
def get_fixed_value(row, col)
  @cells[row][col].get_fixed_value()
end
get_possible_values(row, col) click to toggle source
# File lib/phg_sudoku_solver.rb, line 75
def get_possible_values(row, col)
  @cells[row][col].get_possible_values
end
get_total_iterations() click to toggle source
# File lib/phg_sudoku_solver.rb, line 79
def get_total_iterations
  @total_iterations
end
print_debug(message) click to toggle source
recurse() click to toggle source
# File lib/phg_sudoku_solver.rb, line 314
def recurse
  recurse = copy()
  (2..9).each { |guesses|
    (0..8).each { |r|
      (0..8).each { |c|
        if (recurse.get_possible_values(r, c).count==guesses)  #Staring with cells that have the fewest to solve.
          (0..recurse.get_possible_values(r, c).count).each { |j|
            unless recurse.get_possible_values(r, c)[j].nil?
              print_debug '\nStarting recursion with (%s,%s) set to %s\n' % [r, c, recurse.get_possible_values(r, c)[j]]
              recurse.set_fixed_value(r, c, recurse.get_possible_values(r, c)[j])
              print_debug('Recursion starting...')
              recurse, iterations = recurse.solve
              @total_iterations = @total_iterations + iterations
              if recurse!=nil
                return recurse
              else
                recurse = copy()
              end
            end
          }
        end
      }
    }
  }
  print_debug('Dead end found.\n')
  nil
end
set_cells(row, col, cell) click to toggle source
# File lib/phg_sudoku_solver.rb, line 55
def set_cells(row, col, cell)
  @cells[row][col]=cell
end
set_debug(b) click to toggle source
# File lib/phg_sudoku_solver.rb, line 433
def set_debug(b)
  @debug = b
end
set_fixed_value(row, col, val) click to toggle source
# File lib/phg_sudoku_solver.rb, line 63
def set_fixed_value(row, col, val)
  @cells[row][col].set_fixed_value(val)
end
set_max_iterations(iterations) click to toggle source
# File lib/phg_sudoku_solver.rb, line 12
def set_max_iterations(iterations)
  @max_iterations=iterations
end
set_possible_values(row, col, vals) click to toggle source
# File lib/phg_sudoku_solver.rb, line 67
def set_possible_values(row, col, vals)
  @cells[row][col].set_possible_values(vals)
end
set_total_iterations(iterations) click to toggle source
# File lib/phg_sudoku_solver.rb, line 16
def set_total_iterations(iterations)
  @total_iterations = iterations
end
solve() click to toggle source
# File lib/phg_sudoku_solver.rb, line 83
def solve
  iteration=0
  no_progress_count = 0
  print_debug 'Max Iterations = %s' %  @max_iterations

  while @solved_cell_count!=81
    iteration+=1
    @total_iterations+=1
    print_debug 'Iteration: %s   SolvedCells: %s\n' % [iteration, @solved_cell_count]
    print_debug dump_known_cells_str
    compute_possible_values()

    begin
      if validate_sudoku()
        find_row_implied_values()
        find_col_implied_values()
        find_matrix_implied_values()
      else
        return nil, @total_iterations
      end
    rescue Exception => error
      print_debug '\nValidation Error: %s\n' % error
      @solved_cell_count=count_fixed_cells()
      return nil, @total_iterations
    end

    if @max_iterations > 0 and @total_iterations > @max_iterations
      print_debug 'Total Iterations... %s\n' % @total_iterations
      print_debug 'This is just taking too long\n'
      raise Exception.new('Solution taking too long!\n\n')
    end

    if @solved_cell_count==count_fixed_cells()
      no_progress_count+=1
      if no_progress_count>9
        print_debug ('We''re not making progress here!')
        solution = recurse()
        return solution, @total_iterations
      end
    else
      no_progress_count=0
      @solved_cell_count=count_fixed_cells()
    end
  end
  return self, @total_iterations
end
validate_column(c) click to toggle source
# File lib/phg_sudoku_solver.rb, line 395
def validate_column(c)

  (1..9).each { |i|
    found_count = 0
    (0..8).each { |r|
      if @cells[r][c].get_fixed_value()==i
        found_count+=1
      end
    }
    if found_count>1
      raise Exception.new('Row invalid.  Canceling')
    end
  }
  true
end
validate_matrix(r, c) click to toggle source
# File lib/phg_sudoku_solver.rb, line 412
def validate_matrix(r, c)
  (1..9).each { |i|
    found_count=0
    row_start = (r/3).floor * 3
    col_start = (c/3).floor * 3
    (row_start..row_start+2).each { |y|
      (col_start..col_start+2).each { |x|
        if @cells[y][x].get_fixed_value()==i
          found_count+=1
        end

      }
    }
    if found_count>1
      raise Exception.new('Matrix invalid! Canceling.')
    end
  }
  true
end
validate_row(r) click to toggle source
# File lib/phg_sudoku_solver.rb, line 378
def validate_row(r)
  
  (1..9).each { |i|
    found_count=0
    (0..8).each { |c|
      if @cells[r][c].get_fixed_value()==i
        found_count+=1
      end
    }
    if found_count>1
      raise Exception.new('Row invalid %s.  Canceling' % r)
    end
  }
  true
end
validate_sudoku() click to toggle source
# File lib/phg_sudoku_solver.rb, line 356
def validate_sudoku
  results = true
  begin
    (0..8).each { |r|
      validate_row(r)
    }

    (0..8).each { |c|
      validate_column(c)
    }

    [0, 3, 6].each { |r|
      [0, 3, 6].each { |c|
        validate_matrix(r, c)
      }
    }
  rescue Exception => error
    results = false
  end
  results
end