Class: SudokuSolver::Solver

Inherits:
Object
  • Object
show all
Defined in:
lib/sudoku_solver/solver.rb

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(problem) ⇒ Solver

Returns a new instance of Solver.



26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/sudoku_solver/solver.rb', line 26

def initialize(problem)
  @problem = problem
  @width = @problem.length
  if problem.any? { |l| l.length != @width }
    raise InvalidProblemError.new(problem)
  end
  @dimension = Math.sqrt(@width).to_i
  @size = (0..(@width -1))
  @possibilities = (1..@width)
rescue
  raise InvalidProblemError.new(problem)
end

Class Method Details

.solve(problem) ⇒ Object 



12
13
14
 
# File 'lib/sudoku_solver/solver.rb', line 12

def self.solve(problem)
  self.new(problem).solve
end

Instance Method Details

#grid ⇒ Object 



16
17
18
19
20
21
22
23
24
 
# File 'lib/sudoku_solver/solver.rb', line 16

def grid
  Grid.new(@dimension).each { |c|
    v = @problem[c.y][c.x]
    unless v.nil? || @possibilities.to_a.include?(v)
      raise InvalidProblemError.new(@problem) 
    end
    c.content = v ? [v] : @possibilities.to_a
  }
end

#reduce(grid) ⇒ Object 



60
61
62
63
64
65
66
67
68
 
# File 'lib/sudoku_solver/solver.rb', line 60

def reduce(grid)
  unsolved = grid.reject { |c| c.content.length == 1 }
  until unsolved.empty? do
    changed = unsolved.reject { |c| restrict(c) }
    break unless changed.length > 0
    unsolved.reject! { |c| c.content.length == 1 }
  end
  grid
end

#restrict(cell) ⇒ Object 



70
71
72
73
74
75
76
77
78
 
# File 'lib/sudoku_solver/solver.rb', line 70

def restrict(cell)
  taken = cell.neighbours.collect { |c| c.content }.
    reject { |r| r.length > 1 }.flatten
  remaining = (cell.content - taken).sort
  if remaining.length == 0
    raise InvalidProblemError.new(@problem)
  end
  (cell.content == remaining) || ! (cell.content = remaining)
end

#solve ⇒ Object 



39
40
41
42
 
# File 'lib/sudoku_solver/solver.rb', line 39

def solve
  self.step(self.grid).to_a.collect { |l| l.collect { |c|
    c.content.length == 1 ? c.content.first : nil } }
end

#step(grid) ⇒ Object

Raises:



44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
# File 'lib/sudoku_solver/solver.rb', line 44

def step(grid)
  grid = self.reduce(grid)
  return grid if grid.solved?
  cell = grid.detect { |c| c.content.length > 1 }
  cell.content.each { |value|
    begin
      new_grid = grid.dup
      new_grid[cell.x, cell.y] = [value]
      solution = step(new_grid)
      return solution if solution.solved?
    rescue InvalidProblemError
    end
  }
  raise InvalidProblemError.new(@problem)
end