Class: Xudoku::Solver

Inherits:
Object
  • Object
show all
Includes:
Utils
Defined in:
lib/xudoku/solver.rb

Overview

:nodoc:

Instance Attribute Summary collapse

Instance Method Summary collapse

Methods included from Utils

#bits_to_numbers, #guesses_from, #pick_better, #pos

Constructor Details

#initialize(board) ⇒ Solver

Returns a new instance of Solver.



10
11
12
13
 
# File 'lib/xudoku/solver.rb', line 10

def initialize(board)
  @board = board
  @stack = []
end

Instance Attribute Details

#board ⇒ Object

Returns the value of attribute board.



8
9
10
 
# File 'lib/xudoku/solver.rb', line 8

def board
  @board
end

#stack ⇒ Object

Returns the value of attribute stack.



8
9
10
 
# File 'lib/xudoku/solver.rb', line 8

def stack
  @stack
end

Instance Method Details

#apply(choice) ⇒ Object 



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

def apply(choice)
  workspace = choice.board.dup
  position, number = choice.current_guess
  workspace[position] = number
  stack << choice.step

  guesses = workspace.deduce
  stack << Choice.from([guesses, 0, workspace]) unless guesses.nil?

  [guesses, workspace]
end

#exhausted? ⇒ Boolean

Returns:

  • (Boolean) 


48
49
50
 
# File 'lib/xudoku/solver.rb', line 48

def exhausted?
  stack.empty?
end

#search ⇒ Object 



36
37
38
39
40
41
42
43
44
45
46
 
# File 'lib/xudoku/solver.rb', line 36

def search
  until exhausted?
    choice = stack.pop
    next if choice.exhausted?

    guesses, workspace = apply(choice)
    return workspace if guesses.nil?
  end

  nil
end

#solve ⇒ Object 



27
28
29
30
31
32
33
34
 
# File 'lib/xudoku/solver.rb', line 27

def solve
  workspace = board.dup
  guesses = workspace.deduce
  return workspace if guesses.nil?

  stack << Choice.from([guesses, 0, workspace])
  search
end