Class: CombinatorialPuzzleSolver::Sudoku

Inherits:
Puzzle
  • Object
show all
Defined in:
lib/combinatorial_puzzle_solver/sudoku.rb

Overview

A sudoku puzzle.

A puzzle with dimension 3 implies the standard 9x9 puzzle, whereas dimension 2 implies a 4x4 puzzle.

Specifications

solves sudoku puzzles

Given the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8

When resolved:

4 2 6|3 8 1|7 5 9
1 3 9|7 5 6|8 2 4
7 8 5|2 4 9|6 3 1
-----+-----+-----
5 1 3|6 7 4|9 8 2
9 6 7|1 2 8|5 4 3
2 4 8|5 9 3|1 7 6
-----+-----+-----
8 5 4|9 1 2|3 6 7
6 9 2|8 3 7|4 1 5
3 7 1|4 6 5|2 9 8

Instance Attribute Summary (collapse)

Attributes inherited from Puzzle

#constraints, #identifiers, #symbols

Class Method Summary (collapse)

Instance Method Summary (collapse)

Methods inherited from Puzzle

#inspect, #inspect_identifier, #resolve!, #resolved_solution_space, #set_resolved_identifiers!

Constructor Details

- (Sudoku) initialize(dimension = 3, digits = [])

Creates a new and empty sudoku puzzle, with all identifiers unassigned.

Parameters:

  • dimension (Fixnum) (defaults to: 3)

    the dimension of the puzzle ('2' implies a 4x4 puzzle and '3' implies a 9x9 puzzle).

  • digits (Array[Fixnum]) (defaults to: [])

    an optional array of digits, where each digit corresponds to an identifier's value from 0 to 9.

Raises:

  • (RuntimeError)

    if the digits array (if given) is of incorrect size.

Specifications:

should raise RuntimeError if digits contain wrong number of values



39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 39

def initialize(dimension=3, digits=[])
  @dimension = dimension
  @size = dimension*dimension
  super(@size*@size, (1..@size).to_a) {|identifier|
    (rows + columns + squares).collect{|group| Constraint.new(group) }
  }

  unless digits.empty? then
    unless digits.size == @size*@size then
      error_msg = "Parsed #{digits.size} digits instead of #{@size*@size})."
      raise RuntimeError.new(error_msg)
    end

    digits.each_with_index{|value, index|
      identifiers[index].set!(value) unless value == 0
    }
  end
end

Instance Attribute Details

- (Fixnum) size (readonly)

Returns the width/height of the sudoku board (9 for a 9x9 puzzle).

Returns:

  • (Fixnum)

    the width/height of the sudoku board (9 for a 9x9 puzzle).



12
13
14
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 12

def size
  @size
end

Class Method Details

+ (Array[Sudoku]) scan(string, dimension = 3) {|sudoku| ... }

Parses a string where 1-9 are interpreted as values and 0 is interpreted as unassigned, whereas all other characters (including whitespaces) are discarded.

Parameters:

  • string (String)

    the input string.

  • dimension (Fixnum) (defaults to: 3)

    Dimension 2 implies a 4x4 puzzle, 3 implies 9x9.

Yield Parameters:

  • sudoku (Sudoku)

    each parsed sudoku puzzle.

Returns:

  • (Array[Sudoku])

    the parsed sudoku puzzles.

Raises:

  • (RuntimeError)

    if the parsed digits don't match up to even puzzles.

Specifications:

should create Sudoku puzzles and set the values

Given the input string:

000|301|000
009|000|000
080|000|030
---+---+---
000|004|980
007|120|500
200|090|170
---+---+---
050|012|000
090|007|000
300|405|008

It creates the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8

should ignore every character except the digits

Given the input string:

000301000009000000080000030000004980007120500200090170050012000090007000300405008

It creates the puzzle:

     |3   1|     
    9|     |     
  8  |     |  3  
-----+-----+-----
     |    4|9 8  
    7|1 2  |5    
2    |  9  |1 7  
-----+-----+-----
  5  |  1 2|     
  9  |    7|     
3    |4   5|    8


23
24
25
26
27
28
29
30
31
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 23

def self.scan(string, dimension=3)
  digits = string.scan(/\d/).collect{|value| value.to_i}
  size = dimension**4
  digits.each_slice(size).collect{|digits|
    puzzle = Sudoku.new(dimension, digits)
    yield puzzle if block_given?
    puzzle
  }
end

Instance Method Details

- (Array<Array<Identifier>>) columns

Returns the identifiers grouped by columns

Returns:

  • (Array<Array<Identifier>>)

    the identifiers grouped by columns

Specifications:

should return an array of all identifiers grouped in columns.

Columns

123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789
123456789


64
65
66
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 64

def columns
  rows.transpose
end

- (String) identifier_to_s(identifier)

Returns a string representation of an identifier, which would be “[row,column]”

Returns:

  • (String)

    a string representation of an identifier, which would be “[row,column]”



88
89
90
91
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 88

def identifier_to_s(identifier)
  index = identifiers.index(identifier)
  "[#{index / size + 1},#{index % size + 1}]"
end

- (Array<Array<Identifier>>) rows

Returns the identifiers grouped by rows

Returns:

  • (Array<Array<Identifier>>)

    the identifiers grouped by rows

Specifications:

should return an array of all identifiers grouped in rows.

Rows

111111111
222222222
333333333
444444444
555555555
666666666
777777777
888888888
999999999


59
60
61
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 59

def rows
  @identifiers.each_slice(@size).to_a
end

- (Array<Array<Identifier>>) squares

Returns the identifiers grouped by squares

Returns:

  • (Array<Array<Identifier>>)

    the identifiers grouped by squares

Specifications:

should return an array of all identifiers grouped in squares

Squares

111222333
111222333
111222333
444555666
444555666
444555666
777888999
777888999
777888999


69
70
71
72
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 69

def squares
  slices = columns.flatten.each_slice(@dimension).each_slice(@dimension).to_a
  slices.transpose.flatten.each_slice(@size).to_a
end

- (String) to_s

Returns a simple string representation of the sudoku puzzle.

Returns:

  • (String)

    a simple string representation of the sudoku puzzle.



75
76
77
78
79
80
81
82
83
84
# File 'lib/combinatorial_puzzle_solver/sudoku.rb', line 75

def to_s
  horizontal = "\n#{Array.new(@dimension){"-" * (@dimension*2-1) }.join("+")}\n"
  separators = [" ", "|", "\n", horizontal]

  values = @identifiers.collect{|id| (id.has_value?) ? id.value.to_s : " "}
  separators.each{|separator|
    values = values.each_slice(@dimension).collect{|s| s.join(separator) }
  }
  values.join
end