Class: SudokuBardi::Solver

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/sudoku_bardi.rb

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(board_str = '') ⇒ Solver

Returns a new instance of Solver.



53
54
55
56
57
 
# File 'lib/sudoku_bardi.rb', line 53

def initialize board_str = ''
  start
  process board_str
  push ['start']
end

Class Method Details

.constraint(c) ⇒ Object 



45
46
47
48
49
50
51
 
# File 'lib/sudoku_bardi.rb', line 45

def self.constraint c
  a = []
  c.size.times do
    a << c.dup
  end
  a
end

.piece_from_char(c) ⇒ Object 



39
40
41
42
43
 
# File 'lib/sudoku_bardi.rb', line 39

def self.piece_from_char c
  i = c.bytes.first - 49 # 49 == '0'.bytes.first + 1
  return nil if 0 > i
  NINE[i]
end

Instance Method Details

#add_mark(i) ⇒ Object 



203
204
205
 
# File 'lib/sudoku_bardi.rb', line 203

def add_mark i
  push ['mark', i, possible(i), -1]
end

#board_to_s ⇒ Object 



67
68
69
70
71
72
 
# File 'lib/sudoku_bardi.rb', line 67

def board_to_s
  a = @board.map do |piece|
    TO_S[piece]
  end
  a.join ''
end

#do_backtrack ⇒ Object 



219
220
221
222
223
224
225
226
227
228
229
230
 
# File 'lib/sudoku_bardi.rb', line 219

def do_backtrack
  pop if 'mark' == @ops[-1][0]
  op = pop
  if op
    while 'mark' != op[0]
      undo_op op if op[0].kind_of? Numeric
      op = pop
      return @ops unless op
    end
  end
  push op if op
end

#do_op(op) ⇒ Object 



79
80
81
82
83
84
85
86
87
 
# File 'lib/sudoku_bardi.rb', line 79

def do_op op
  i, piece = op
  r, c, b = RCB[i]
  @rows[r] -= [piece]
  @columns[c] -= [piece]
  @boxes[b] -= [piece]
  @board[i] = piece
  op
end

#each ⇒ Object 



254
255
256
257
258
259
260
261
262
263
264
265
266
267
 
# File 'lib/sudoku_bardi.rb', line 254

def each
  first = true
  finished = false
  until finished
    push ['backtrack', 81] unless first
    first = false
    result = solve_one
    if result
      yield [result[0].dup, result[1]]
    else
      finished = true
    end
  end
end

#gen_choices ⇒ Object 



190
191
192
193
194
195
196
197
198
199
200
201
 
# File 'lib/sudoku_bardi.rb', line 190

def gen_choices
  a = []
  @board.each_with_index do |piece, i|
    if !piece
      ps = possible(i)
      if 1 < ps.size
        a += ps.map {|e| [i, e]}
      end
    end
  end
  a
end

#min_choices ⇒ Object 



175
176
177
178
179
180
181
182
183
184
185
186
187
188
 
# File 'lib/sudoku_bardi.rb', line 175

def min_choices
  j = nil
  count = 10
  @board.each_with_index do |piece, i|
    if !piece
      len = possible(i).size
      if len < count
        j = i
        count = len
      end
    end
  end
  j
end

#play(ops) ⇒ Object 



129
130
131
132
133
 
# File 'lib/sudoku_bardi.rb', line 129

def play ops
  ops.each do |op|
    push do_op(op)
  end
end

#pop ⇒ Object 



107
108
109
110
 
# File 'lib/sudoku_bardi.rb', line 107

def pop
  return nil if 'start' == @ops[-1][0]
  @ops.pop
end

#pop_start ⇒ Object 



99
100
101
 
# File 'lib/sudoku_bardi.rb', line 99

def pop_start
  @ops.pop
end

#possible(i) ⇒ Object 



74
75
76
77
 
# File 'lib/sudoku_bardi.rb', line 74

def possible i
  r, c, b = RCB[i]
  @rows[r] & @columns[c] & @boxes[b]
end

#process(board_str) ⇒ Object 



135
136
137
 
# File 'lib/sudoku_bardi.rb', line 135

def process board_str
  play process_str(board_str)
end

#process_str(str_as_ops) ⇒ Object 



116
117
118
119
120
121
122
123
124
125
126
127
 
# File 'lib/sudoku_bardi.rb', line 116

def process_str str_as_ops
  ops = []
  str_as_ops.each_char.with_index do |char, i|
    piece = self.class.piece_from_char char
    if piece
      ps = possible i
      raise "impossible #{char} at #{i}" unless ps.include? piece
      push do_op([i, piece])
    end
  end
  ops
end

#push(op) ⇒ Object 



112
113
114
 
# File 'lib/sudoku_bardi.rb', line 112

def push op
  @ops << op
end

#push_start ⇒ Object 



103
104
105
 
# File 'lib/sudoku_bardi.rb', line 103

def push_start
  push ['start']
end

#single(i) ⇒ Object 



139
140
141
142
143
144
145
146
147
148
149
150
151
 
# File 'lib/sudoku_bardi.rb', line 139

def single i
  processed_single = false
  backtrack = false
  ps = possible i
  if 0 == ps.length
    backtrack = true
  end
  if 1 == ps.length
    processed_single = true
    push do_op([i, ps[0]])
  end
  [processed_single, backtrack]
end

#singles ⇒ Object 



153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
 
# File 'lib/sudoku_bardi.rb', line 153

def singles
  had_singles = true
  finished = true
  while had_singles
    finished = true
    single_found = false
    @board.each_with_index do |piece, i|
      if !piece
        finished = false
        processed_single, backtrack = single i
        single_found ||= processed_single
        if backtrack
          push ['backtrack', i]
          return finished
        end
      end
    end
    had_singles = single_found
  end
  finished
end

#solve_one ⇒ Object 



232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
 
# File 'lib/sudoku_bardi.rb', line 232

def solve_one
  solved = false
  until solved
    if 'backtrack' == @ops[-1][0]
      pop
      do_backtrack
      if 'start' == @ops[-1][0]
        return nil
      end
      try
    else
      solved = singles
      if !solved
        i = min_choices
        add_mark i
        try
      end
    end
  end
  [@ops, board_to_s]
end

#start ⇒ Object 



59
60
61
62
63
64
65
 
# File 'lib/sudoku_bardi.rb', line 59

def start 
  @board = [nil] * (NINE.size * NINE.size)
  @rows = self.class.constraint NINE
  @columns = self.class.constraint NINE
  @boxes = self.class.constraint NINE 
  @ops = []
end

#try ⇒ Object 



207
208
209
210
211
212
213
214
215
216
217
 
# File 'lib/sudoku_bardi.rb', line 207

def try
  mark = pop.dup
  mark[3] += 1
  piece = mark[2][mark[3]]
  push mark
  if piece
    push do_op([mark[1], piece])
  else
    push ['backtrack', mark[1]]
  end
end

#undo_op(op) ⇒ Object 



89
90
91
92
93
94
95
96
97
 
# File 'lib/sudoku_bardi.rb', line 89

def undo_op op
  i, piece = op
  r, c, b = RCB[i]
  @rows[r] += [piece]
  @columns[c] += [piece]
  @boxes[b] += [piece]
  @board[i] = nil
  op
end