Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- require 'Cell'
- require 'Group'
- require 'Inspector'
- module Sudoku
- # Builds the cells and groups and provides an API for setting up and interacting with the puzzle.
- #
- # Several debugging methods are provided that are being extracted to the inspector.
- class Board
- # Builds the board structure and initializes an empty puzzle.
- #
- # @param start [String] optional initial values passed to #setup
- def initialize(start = nil)
- @cells = Array.new(9) { |r| Array.new(9) { |c| Cell.new r, c } }
- @rows = Array.new(9) { |i| Group.new :row, i }
- @cols = Array.new(9) { |i| Group.new :col, i }
- @boxes = Array.new(9) { |i| Group.new :box, i }
- (0..8).each do |i|
- connect @rows[i], row_cells(i)
- connect @cols[i], col_cells(i)
- connect @boxes[i], box_cells(i)
- end
- setup start if start
- end
- # Sets the initial values of the puzzle.
- #
- # Place each row on a separate line and nine cell values on each row.
- # Whitespace is ignored around the row on each line. Each cell value
- # may be a digit [1-9] or a period (.) if empty.
- #
- # @param start [String] optional initial values passed to #setup
- #
- # @example Nine queens
- # .....9...
- # ...9.....
- # ......9..
- # 9........
- # .......9.
- # .9.......
- # ....9....
- # ..9......
- # ........9
- def setup(puzzle)
- r = 1
- puzzle.split.each do |line|
- c = 1
- line.each_char do |n|
- set(r, c, n.to_i, :start) if n =~ /[1-9]/
- c += 1
- end
- r += 1
- end
- end
- # Returns true if the cell can be set to the value.
- #
- # @param r [Fixnum] one-based row
- # @param c [Fixnum] one-based column
- # @param n [Fixnum] one-based cell value
- # @return [Boolean]
- def possible?(r, c, n)
- cell(r, c).possible? n
- end
- # Returns true if the cell has been set to a value.
- #
- # @param r [Fixnum] one-based row
- # @param c [Fixnum] one-based column
- # @return [Boolean]
- def known?(r, c)
- cell(r, c).known?
- end
- # Sets the cell to the value for the given reason (omit when playing).
- #
- # @param r [Fixnum] one-based row
- # @param c [Fixnum] one-based column
- # @param n [Fixnum] one-based cell value
- # @param reason [Symbol] one of :start, :choose, or :force
- # @return [void]
- #
- # @raise [RuntimeError] if the cell is already set
- # @raise [RuntimeError] if the value is not possible for the cell
- def set(r, c, n, reason = :choose)
- cell(r, c).set(n, reason)
- end
- # Iterates over each cell on the board from left-to-right and top-to-bottom.
- #
- # Used by the inspector.
- #
- # @yieldparam cell [Cell]
- # @return [void]
- def each_cell
- @cells.each { |row| row.each { |cell| yield cell } }
- end
- def to_s
- @cells.map { |row| row * "" } * "n"
- end
- # Creates an inspector for this board.
- #
- # @return [Inspector] doesn't yet fully implement the output available in this class
- def inspector
- Inspector.new self
- end
- private
- def cell(r, c)
- @cells[r - 1][c - 1]
- end
- def row_cells(r)
- Array.new(9) { |c| @cells[r][c] }
- end
- def col_cells(c)
- Array.new(9) { |r| @cells[r][c] }
- end
- def box_cells(b)
- box_r = b % 3 * 3
- box_c = b / 3 * 3
- Array.new(9) { |i| @cells[box_r + i % 3][box_c + i / 3] }
- end
- def connect(group, cells)
- cells.each { |cell| cell.join group }
- end
- ### Debugging
- public
- def inspect
- "Board Staten#{to_s}"
- end
- def debug
- debug_cells
- debug_rows
- debug_cols
- debug_boxes
- end
- def debug_cells
- puts "Cell Possibilities"
- puts @cells.map { |row| row.map { |cell| cell.debug } * " " } * "n"
- end
- def debug_rows
- puts "Row Possibilities"
- debug_group(@rows)
- end
- def debug_cols
- puts "Column Possibilities"
- debug_group(@cols)
- end
- def debug_boxes
- puts "Box Possibilities"
- debug_group(@boxes)
- end
- private
- def debug_group(groups)
- puts groups.map { |group| group.debug } * "n"
- end
- end
- end
- require 'set'
- module Sudoku
- # Tracks the cells that make up a single row, column, or 3x3 box, which are still available
- # to be set to which values, and the values still left to be set somewhere in the group.
- class Group
- # Creates an empty group of the given type.
- #
- # @param type [Symbol] either :row, :col, or :box
- # @param index [Fixnum] zero-based index
- def initialize(type, index)
- @type, @index = type, index
- @id = "#{type}-#{index + 1}"
- @knowns = {}
- @possibles = Hash[(1..9).map { |n| [n, Set.new] }]
- end
- attr_reader :id, :type, :index
- # Makes the cell available for the given value or all values.
- #
- # @param cell [Cell] the cell that can be set to the value
- # @param n [Fixnum or nil] omit to make the cell available for every value
- # @return [void]
- def available(cell, n = nil)
- if n
- @possibles[n] << cell
- else
- @possibles.each_value { |cells| cells << cell }
- end
- end
- # Makes the cell unavailable to receive the value.
- #
- # If the value has only one cell possibility left, it is set to the value.
- #
- # @param cell [Cell] the cell that can no longer be set to the value
- # @param n [Fixnum] one-based cell value
- # @return [void]
- def unavailable(cell, n)
- # puts "%s - unavail: %s -> %d: %s" % [id, cell.id, n, debug]
- cells = @possibles[n]
- cells.delete cell
- if cells.size == 1 and !known? n
- cells.take(1).first.set n, :force
- end
- end
- # Returns true if a cell in this group has been set to the value.
- #
- # @param n [Fixnum] one-based cell value
- # @return [Boolean] true if set; false if still available for this group
- def known?(n)
- !!@knowns[n]
- end
- # Returns true if no cell in this group has been set to the value.
- #
- # @param n [Fixnum] one-based cell value
- # @return [Boolean] false if none set; true if still available for this group
- def possible?(n)
- !@knowns[n]
- end
- # Returns the number of cells that can still be set to the value.
- #
- # @param n [Fixnum] one-based cell value
- # @return [Fixnum]
- def num_possible(n)
- @possibles[n].size
- end
- # Stores that the cell has been set to the value and removes the value as a possible from other cells.
- #
- # @param cell [Cell] the cell that was just set
- # @param n [Fixnum] one-based cell value
- # @return [void]
- def known(cell, n)
- # puts "%s - known : %s -> %d: %s" % [id, cell.id, n, debug]
- raise "#{@knowns[n]} in #{@id} already known for #{n}" if known? n
- raise "#{cell} in #{@id} not possible for #{n}" unless @possibles[n].delete? cell
- @knowns[n] = cell
- @possibles[n].each { |possible| possible.unavailable self, n }
- end
- # Returns a string denoting which values are still possible and in how many cells.
- #
- # @return [String] first group: possible values are as-is; not possible values are dots;
- # second group: number of available cells per cell value
- def debug
- ((1..9).map { |n| possible?(n) ? n : "." } * "") + " " + ((1..9).map { |n| num_possible n } * "")
- end
- end
- end
- require 'set'
- module Sudoku
- # Models a single cell that tracks the possible values to which it may be set
- # and the current value if already set.
- class Cell
- # Creates an empty cell at the given row and column.
- #
- # @param r [Fixnum] zero-based row number
- # @param c [Fixnum] zero-based column number
- def initialize(r, c)
- @r, @c = r, c
- @id = "(#{r + 1},#{c + 1})"
- @initial = @current = nil
- @possibles = (1..9).to_set
- @groups = []
- end
- # Joins the given group and makes this cell available for all numbers.
- #
- # @param group [Group] contains this cell
- # @return [void]
- def join(group)
- @groups << group
- group.available self
- end
- attr_reader :id, :r, :c, :initial, :current
- # Returns true if this cell can be set to the value.
- #
- # @param n [Fixnum] one-based cell value
- # @return [Boolean]
- def possible?(n)
- !known? and @possibles.include? n
- end
- # Iterates over each value this cell can be set to.
- #
- # @yieldparam n [Fixnum] one-based cell value
- # @return [void]
- def each_possible
- @possibles.each { |n| yield n } if !known?
- end
- # Returns true if this cell has been set to a value.
- #
- # @return [Boolean]
- def known?
- !!@current
- end
- # Removes a value from this cell's set of possibilities.
- #
- # If this leaves the cell with but one possibility, the cell is set to it.
- #
- # @param n [Fixnum] one-based cell value
- # @return [void]
- #
- # @raise [RuntimeError] if n is the only possibility left
- def known(n)
- if possible? n
- raise "No possibilities left for cell #{@id}" if @possibles.size == 1
- @possibles.delete n
- set(@possibles.take(1).first, :force) if @possibles.size == 1
- end
- end
- # Notifies this cell's groups that the value is no longer possible for this cell.
- #
- # @param n [Fixnum] one-based cell value
- # @return [void]
- #
- # @todo Merge with #known.
- def unavailable(group, n)
- # puts " - unavail: %s -> %d: %s from %s" % [id, n, debug, group.id]
- @groups.each { |possible| possible.unavailable self, n }
- known n
- end
- # Sets this cell to the value and notifies each group.
- #
- # @param n [Fixnum] one-based cell value
- # @param reason [Symbol] either :setup, :choose, or :force
- # @return [void]
- #
- # @raise [RuntimeError] if this cell is already set
- # @raise [RuntimeError] if the value is not possible for this cell
- def set(n, reason)
- puts " - %-7s: %s -> %d: %s" % [reason, id, n, debug]
- @initial = n if reason == :initial
- return if @current == n
- raise "cannot change #{@id} from #{@current} to #{n}" if @current
- raise "Cannot set #{@id} to #{n}" if !possible? n
- @possibles.delete n
- @current = n
- @groups.each do |group|
- group.known self, n
- @possibles.each { |n| group.unavailable self, n }
- end
- @possibles.clear
- end
- # Returns the current value of this cell if set or a dot if not.
- #
- # @return [String] single digit or a dot
- def to_s
- (@current || ".").to_s
- end
- # Returns a string denoting which values are still possible.
- #
- # @return [String] possible values are as-is; not possible values are dots
- def debug
- (1..9).map { |n| possible?(n) ? n : "." } * ""
- end
- end
- end
- require 'Board'
- module Sudoku
- # Creates several test puzzles from easy to evil.
- #
- # @see http://www.websudoku.com/
- module Test
- def self.easy
- self.test <<-PUZZLE
- ..38.4.5.
- 84......7
- 6....29..
- .18.5..9.
- 2.6.7.4.5
- .3..4.86.
- ..51....8
- 1......79
- .6.5.7.2.
- PUZZLE
- end
- def self.medium
- self.test <<-PUZZLE
- .5.....7.
- 9428.....
- ....6...5
- 48..765..
- .93...78.
- ..598..14
- 7...4....
- .....8193
- .1.....4.
- PUZZLE
- end
- def self.hard
- self.test <<-PUZZLE
- .....5.8.
- .8....5.1
- ..5.12.69
- ......17.
- .2.....3.
- .19......
- 15.34.7..
- 8.7....1.
- .6.9.....
- PUZZLE
- end
- def self.evil # http://www.websudoku.com/?level=4&set_id=6247568390
- self.test <<-PUZZLE
- .4.2.....
- .....13.7
- ..5...91.
- .8..13...
- ..3.6.5..
- ...72..4.
- .12...4..
- 8.69.....
- .....2.3.
- PUZZLE
- end
- def self.test(puzzle)
- puts "Initial Puzzle"
- puts puzzle
- b = Board.new puzzle
- b.debug
- b.inspector.cells
- b
- end
- end
- end
- module Sudoku
- # Assists debugging the internal state of the board.
- class Inspector
- # Stores the board for inspection
- #
- # @param board [Board]
- def initialize(board)
- @board = board
- end
- # Displays the current cell values.
- def current
- rows = []
- row = nil
- @board.each_cell do |cell|
- if cell.c == 0
- row = ""
- rows << "" if cell.r != 0 && cell.r % 3 == 0
- end
- row += " " if cell.c != 0 && cell.c % 3 == 0
- row += cell.to_s
- rows << row if cell.c == 8
- end
- puts "Current Puzzle"
- puts
- puts rows * "n"
- end
- # Displays the available values for each cell.
- def cells
- grid = ([["... " * 9] * 3, ""].flatten * 9).map(&:clone)
- @board.each_cell do |cell|
- r, c = 4 * cell.r, 4 * cell.c
- cell.each_possible do |n|
- grid[r + (n - 1) / 3][c + (n - 1) % 3] = n.to_s
- end
- end
- puts "Cell Possibilities"
- puts
- puts grid * "n"
- end
- def inspect
- "Inspector"
- end
- end
- end
- def rows
- @rows ||= Array.new(9) { |i| Group.new :row, i }
- end
- def rows
- @rows ||= create_groups(:row)
- end
- # ...
- def create_groups(type)
- Array.new(9) { |i| Group.new type, i }
- end
- def setup(puzzle)
- puzzle.split.each_with_index do |line, row|
- line.scan(/./).each_with_index do |char, column|
- set(row, column, char.to_i, :start) if char =~ /d/
- end
- end
- end
- def cell[](row, column)
- cells[row - 1][column - 1]
- end
- def current
- puts "Current Puzzle"
- puts cells.map { |row|
- row.map(&:to_s).each_slice(3).to_a.map(&:join).join(" ")
- }.each_slice(3).map { |slice| slice.join("n") }.join("nn")
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement