Advertisement
Guest User

Untitled

a guest
Feb 28th, 2015
201
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.60 KB | None | 0 0
  1. require 'Cell'
  2. require 'Group'
  3. require 'Inspector'
  4.  
  5. module Sudoku
  6.  
  7. # Builds the cells and groups and provides an API for setting up and interacting with the puzzle.
  8. #
  9. # Several debugging methods are provided that are being extracted to the inspector.
  10. class Board
  11.  
  12. # Builds the board structure and initializes an empty puzzle.
  13. #
  14. # @param start [String] optional initial values passed to #setup
  15. def initialize(start = nil)
  16. @cells = Array.new(9) { |r| Array.new(9) { |c| Cell.new r, c } }
  17. @rows = Array.new(9) { |i| Group.new :row, i }
  18. @cols = Array.new(9) { |i| Group.new :col, i }
  19. @boxes = Array.new(9) { |i| Group.new :box, i }
  20. (0..8).each do |i|
  21. connect @rows[i], row_cells(i)
  22. connect @cols[i], col_cells(i)
  23. connect @boxes[i], box_cells(i)
  24. end
  25. setup start if start
  26. end
  27.  
  28. # Sets the initial values of the puzzle.
  29. #
  30. # Place each row on a separate line and nine cell values on each row.
  31. # Whitespace is ignored around the row on each line. Each cell value
  32. # may be a digit [1-9] or a period (.) if empty.
  33. #
  34. # @param start [String] optional initial values passed to #setup
  35. #
  36. # @example Nine queens
  37. # .....9...
  38. # ...9.....
  39. # ......9..
  40. # 9........
  41. # .......9.
  42. # .9.......
  43. # ....9....
  44. # ..9......
  45. # ........9
  46. def setup(puzzle)
  47. r = 1
  48. puzzle.split.each do |line|
  49. c = 1
  50. line.each_char do |n|
  51. set(r, c, n.to_i, :start) if n =~ /[1-9]/
  52. c += 1
  53. end
  54. r += 1
  55. end
  56. end
  57.  
  58. # Returns true if the cell can be set to the value.
  59. #
  60. # @param r [Fixnum] one-based row
  61. # @param c [Fixnum] one-based column
  62. # @param n [Fixnum] one-based cell value
  63. # @return [Boolean]
  64. def possible?(r, c, n)
  65. cell(r, c).possible? n
  66. end
  67.  
  68. # Returns true if the cell has been set to a value.
  69. #
  70. # @param r [Fixnum] one-based row
  71. # @param c [Fixnum] one-based column
  72. # @return [Boolean]
  73. def known?(r, c)
  74. cell(r, c).known?
  75. end
  76.  
  77. # Sets the cell to the value for the given reason (omit when playing).
  78. #
  79. # @param r [Fixnum] one-based row
  80. # @param c [Fixnum] one-based column
  81. # @param n [Fixnum] one-based cell value
  82. # @param reason [Symbol] one of :start, :choose, or :force
  83. # @return [void]
  84. #
  85. # @raise [RuntimeError] if the cell is already set
  86. # @raise [RuntimeError] if the value is not possible for the cell
  87. def set(r, c, n, reason = :choose)
  88. cell(r, c).set(n, reason)
  89. end
  90.  
  91. # Iterates over each cell on the board from left-to-right and top-to-bottom.
  92. #
  93. # Used by the inspector.
  94. #
  95. # @yieldparam cell [Cell]
  96. # @return [void]
  97. def each_cell
  98. @cells.each { |row| row.each { |cell| yield cell } }
  99. end
  100.  
  101. def to_s
  102. @cells.map { |row| row * "" } * "n"
  103. end
  104.  
  105. # Creates an inspector for this board.
  106. #
  107. # @return [Inspector] doesn't yet fully implement the output available in this class
  108. def inspector
  109. Inspector.new self
  110. end
  111.  
  112. private
  113.  
  114. def cell(r, c)
  115. @cells[r - 1][c - 1]
  116. end
  117.  
  118. def row_cells(r)
  119. Array.new(9) { |c| @cells[r][c] }
  120. end
  121.  
  122. def col_cells(c)
  123. Array.new(9) { |r| @cells[r][c] }
  124. end
  125.  
  126. def box_cells(b)
  127. box_r = b % 3 * 3
  128. box_c = b / 3 * 3
  129. Array.new(9) { |i| @cells[box_r + i % 3][box_c + i / 3] }
  130. end
  131.  
  132. def connect(group, cells)
  133. cells.each { |cell| cell.join group }
  134. end
  135.  
  136. ### Debugging
  137.  
  138. public
  139.  
  140. def inspect
  141. "Board Staten#{to_s}"
  142. end
  143.  
  144. def debug
  145. debug_cells
  146. debug_rows
  147. debug_cols
  148. debug_boxes
  149. end
  150.  
  151. def debug_cells
  152. puts "Cell Possibilities"
  153. puts @cells.map { |row| row.map { |cell| cell.debug } * " " } * "n"
  154. end
  155.  
  156. def debug_rows
  157. puts "Row Possibilities"
  158. debug_group(@rows)
  159. end
  160.  
  161. def debug_cols
  162. puts "Column Possibilities"
  163. debug_group(@cols)
  164. end
  165.  
  166. def debug_boxes
  167. puts "Box Possibilities"
  168. debug_group(@boxes)
  169. end
  170.  
  171. private
  172.  
  173. def debug_group(groups)
  174. puts groups.map { |group| group.debug } * "n"
  175. end
  176. end
  177. end
  178.  
  179. require 'set'
  180.  
  181. module Sudoku
  182.  
  183. # Tracks the cells that make up a single row, column, or 3x3 box, which are still available
  184. # to be set to which values, and the values still left to be set somewhere in the group.
  185. class Group
  186.  
  187. # Creates an empty group of the given type.
  188. #
  189. # @param type [Symbol] either :row, :col, or :box
  190. # @param index [Fixnum] zero-based index
  191. def initialize(type, index)
  192. @type, @index = type, index
  193. @id = "#{type}-#{index + 1}"
  194. @knowns = {}
  195. @possibles = Hash[(1..9).map { |n| [n, Set.new] }]
  196. end
  197.  
  198. attr_reader :id, :type, :index
  199.  
  200. # Makes the cell available for the given value or all values.
  201. #
  202. # @param cell [Cell] the cell that can be set to the value
  203. # @param n [Fixnum or nil] omit to make the cell available for every value
  204. # @return [void]
  205. def available(cell, n = nil)
  206. if n
  207. @possibles[n] << cell
  208. else
  209. @possibles.each_value { |cells| cells << cell }
  210. end
  211. end
  212.  
  213. # Makes the cell unavailable to receive the value.
  214. #
  215. # If the value has only one cell possibility left, it is set to the value.
  216. #
  217. # @param cell [Cell] the cell that can no longer be set to the value
  218. # @param n [Fixnum] one-based cell value
  219. # @return [void]
  220. def unavailable(cell, n)
  221. # puts "%s - unavail: %s -> %d: %s" % [id, cell.id, n, debug]
  222. cells = @possibles[n]
  223. cells.delete cell
  224. if cells.size == 1 and !known? n
  225. cells.take(1).first.set n, :force
  226. end
  227. end
  228.  
  229. # Returns true if a cell in this group has been set to the value.
  230. #
  231. # @param n [Fixnum] one-based cell value
  232. # @return [Boolean] true if set; false if still available for this group
  233. def known?(n)
  234. !!@knowns[n]
  235. end
  236.  
  237. # Returns true if no cell in this group has been set to the value.
  238. #
  239. # @param n [Fixnum] one-based cell value
  240. # @return [Boolean] false if none set; true if still available for this group
  241. def possible?(n)
  242. !@knowns[n]
  243. end
  244.  
  245. # Returns the number of cells that can still be set to the value.
  246. #
  247. # @param n [Fixnum] one-based cell value
  248. # @return [Fixnum]
  249. def num_possible(n)
  250. @possibles[n].size
  251. end
  252.  
  253. # Stores that the cell has been set to the value and removes the value as a possible from other cells.
  254. #
  255. # @param cell [Cell] the cell that was just set
  256. # @param n [Fixnum] one-based cell value
  257. # @return [void]
  258. def known(cell, n)
  259. # puts "%s - known : %s -> %d: %s" % [id, cell.id, n, debug]
  260. raise "#{@knowns[n]} in #{@id} already known for #{n}" if known? n
  261. raise "#{cell} in #{@id} not possible for #{n}" unless @possibles[n].delete? cell
  262. @knowns[n] = cell
  263. @possibles[n].each { |possible| possible.unavailable self, n }
  264. end
  265.  
  266. # Returns a string denoting which values are still possible and in how many cells.
  267. #
  268. # @return [String] first group: possible values are as-is; not possible values are dots;
  269. # second group: number of available cells per cell value
  270. def debug
  271. ((1..9).map { |n| possible?(n) ? n : "." } * "") + " " + ((1..9).map { |n| num_possible n } * "")
  272. end
  273. end
  274. end
  275.  
  276. require 'set'
  277.  
  278. module Sudoku
  279.  
  280. # Models a single cell that tracks the possible values to which it may be set
  281. # and the current value if already set.
  282. class Cell
  283.  
  284. # Creates an empty cell at the given row and column.
  285. #
  286. # @param r [Fixnum] zero-based row number
  287. # @param c [Fixnum] zero-based column number
  288. def initialize(r, c)
  289. @r, @c = r, c
  290. @id = "(#{r + 1},#{c + 1})"
  291. @initial = @current = nil
  292. @possibles = (1..9).to_set
  293. @groups = []
  294. end
  295.  
  296. # Joins the given group and makes this cell available for all numbers.
  297. #
  298. # @param group [Group] contains this cell
  299. # @return [void]
  300. def join(group)
  301. @groups << group
  302. group.available self
  303. end
  304.  
  305. attr_reader :id, :r, :c, :initial, :current
  306.  
  307. # Returns true if this cell can be set to the value.
  308. #
  309. # @param n [Fixnum] one-based cell value
  310. # @return [Boolean]
  311. def possible?(n)
  312. !known? and @possibles.include? n
  313. end
  314.  
  315. # Iterates over each value this cell can be set to.
  316. #
  317. # @yieldparam n [Fixnum] one-based cell value
  318. # @return [void]
  319. def each_possible
  320. @possibles.each { |n| yield n } if !known?
  321. end
  322.  
  323. # Returns true if this cell has been set to a value.
  324. #
  325. # @return [Boolean]
  326. def known?
  327. !!@current
  328. end
  329.  
  330. # Removes a value from this cell's set of possibilities.
  331. #
  332. # If this leaves the cell with but one possibility, the cell is set to it.
  333. #
  334. # @param n [Fixnum] one-based cell value
  335. # @return [void]
  336. #
  337. # @raise [RuntimeError] if n is the only possibility left
  338. def known(n)
  339. if possible? n
  340. raise "No possibilities left for cell #{@id}" if @possibles.size == 1
  341. @possibles.delete n
  342. set(@possibles.take(1).first, :force) if @possibles.size == 1
  343. end
  344. end
  345.  
  346. # Notifies this cell's groups that the value is no longer possible for this cell.
  347. #
  348. # @param n [Fixnum] one-based cell value
  349. # @return [void]
  350. #
  351. # @todo Merge with #known.
  352. def unavailable(group, n)
  353. # puts " - unavail: %s -> %d: %s from %s" % [id, n, debug, group.id]
  354. @groups.each { |possible| possible.unavailable self, n }
  355. known n
  356. end
  357.  
  358. # Sets this cell to the value and notifies each group.
  359. #
  360. # @param n [Fixnum] one-based cell value
  361. # @param reason [Symbol] either :setup, :choose, or :force
  362. # @return [void]
  363. #
  364. # @raise [RuntimeError] if this cell is already set
  365. # @raise [RuntimeError] if the value is not possible for this cell
  366. def set(n, reason)
  367. puts " - %-7s: %s -> %d: %s" % [reason, id, n, debug]
  368. @initial = n if reason == :initial
  369. return if @current == n
  370. raise "cannot change #{@id} from #{@current} to #{n}" if @current
  371. raise "Cannot set #{@id} to #{n}" if !possible? n
  372. @possibles.delete n
  373. @current = n
  374. @groups.each do |group|
  375. group.known self, n
  376. @possibles.each { |n| group.unavailable self, n }
  377. end
  378. @possibles.clear
  379. end
  380.  
  381. # Returns the current value of this cell if set or a dot if not.
  382. #
  383. # @return [String] single digit or a dot
  384. def to_s
  385. (@current || ".").to_s
  386. end
  387.  
  388. # Returns a string denoting which values are still possible.
  389. #
  390. # @return [String] possible values are as-is; not possible values are dots
  391. def debug
  392. (1..9).map { |n| possible?(n) ? n : "." } * ""
  393. end
  394. end
  395. end
  396.  
  397. require 'Board'
  398.  
  399. module Sudoku
  400.  
  401. # Creates several test puzzles from easy to evil.
  402. #
  403. # @see http://www.websudoku.com/
  404. module Test
  405.  
  406. def self.easy
  407. self.test <<-PUZZLE
  408. ..38.4.5.
  409. 84......7
  410. 6....29..
  411. .18.5..9.
  412. 2.6.7.4.5
  413. .3..4.86.
  414. ..51....8
  415. 1......79
  416. .6.5.7.2.
  417. PUZZLE
  418. end
  419.  
  420. def self.medium
  421. self.test <<-PUZZLE
  422. .5.....7.
  423. 9428.....
  424. ....6...5
  425. 48..765..
  426. .93...78.
  427. ..598..14
  428. 7...4....
  429. .....8193
  430. .1.....4.
  431. PUZZLE
  432. end
  433.  
  434. def self.hard
  435. self.test <<-PUZZLE
  436. .....5.8.
  437. .8....5.1
  438. ..5.12.69
  439. ......17.
  440. .2.....3.
  441. .19......
  442. 15.34.7..
  443. 8.7....1.
  444. .6.9.....
  445. PUZZLE
  446. end
  447.  
  448. def self.evil # http://www.websudoku.com/?level=4&set_id=6247568390
  449. self.test <<-PUZZLE
  450. .4.2.....
  451. .....13.7
  452. ..5...91.
  453. .8..13...
  454. ..3.6.5..
  455. ...72..4.
  456. .12...4..
  457. 8.69.....
  458. .....2.3.
  459. PUZZLE
  460. end
  461.  
  462. def self.test(puzzle)
  463. puts "Initial Puzzle"
  464. puts puzzle
  465.  
  466. b = Board.new puzzle
  467. b.debug
  468. b.inspector.cells
  469. b
  470. end
  471. end
  472. end
  473.  
  474. module Sudoku
  475.  
  476. # Assists debugging the internal state of the board.
  477. class Inspector
  478.  
  479. # Stores the board for inspection
  480. #
  481. # @param board [Board]
  482. def initialize(board)
  483. @board = board
  484. end
  485.  
  486. # Displays the current cell values.
  487. def current
  488. rows = []
  489. row = nil
  490. @board.each_cell do |cell|
  491. if cell.c == 0
  492. row = ""
  493. rows << "" if cell.r != 0 && cell.r % 3 == 0
  494. end
  495. row += " " if cell.c != 0 && cell.c % 3 == 0
  496. row += cell.to_s
  497. rows << row if cell.c == 8
  498. end
  499. puts "Current Puzzle"
  500. puts
  501. puts rows * "n"
  502. end
  503.  
  504. # Displays the available values for each cell.
  505. def cells
  506. grid = ([["... " * 9] * 3, ""].flatten * 9).map(&:clone)
  507. @board.each_cell do |cell|
  508. r, c = 4 * cell.r, 4 * cell.c
  509. cell.each_possible do |n|
  510. grid[r + (n - 1) / 3][c + (n - 1) % 3] = n.to_s
  511. end
  512. end
  513. puts "Cell Possibilities"
  514. puts
  515. puts grid * "n"
  516. end
  517.  
  518. def inspect
  519. "Inspector"
  520. end
  521. end
  522. end
  523.  
  524. def rows
  525. @rows ||= Array.new(9) { |i| Group.new :row, i }
  526. end
  527.  
  528. def rows
  529. @rows ||= create_groups(:row)
  530. end
  531.  
  532. # ...
  533.  
  534. def create_groups(type)
  535. Array.new(9) { |i| Group.new type, i }
  536. end
  537.  
  538. def setup(puzzle)
  539. puzzle.split.each_with_index do |line, row|
  540. line.scan(/./).each_with_index do |char, column|
  541. set(row, column, char.to_i, :start) if char =~ /d/
  542. end
  543. end
  544. end
  545.  
  546. def cell[](row, column)
  547. cells[row - 1][column - 1]
  548. end
  549.  
  550. def current
  551. puts "Current Puzzle"
  552. puts cells.map { |row|
  553. row.map(&:to_s).each_slice(3).to_a.map(&:join).join(" ")
  554. }.each_slice(3).map { |slice| slice.join("n") }.join("nn")
  555. end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement