Created
September 14, 2011 11:19
-
-
Save knsmr/1216339 to your computer and use it in GitHub Desktop.
magic matrix solver
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # | |
| # Magic matrix solver | |
| # Ken Nishimura 2011/9/14 | |
| # | |
| # Solver.new(Matrix.new((1..9))).solve yeilds: | |
| # | |
| # |8|1|6| | |
| # |3|5|7| | |
| # |4|9|2| | |
| # | |
| class Numeric | |
| def square_number? | |
| Math.sqrt(self).integer? | |
| end | |
| end | |
| class Float | |
| def integer? | |
| self.ceil == self | |
| end | |
| end | |
| module MagicMatrix | |
| module Utils | |
| def magic_constant | |
| @magic_constant ||= @items.inject(:+) / @order | |
| end | |
| def [](x, y) | |
| @matrix[x + y * @order] | |
| end | |
| def []=(x, y, n) | |
| @matrix[x + y * @order] = n | |
| end | |
| def top_left; @matrix[0]; end | |
| def top_right; @matrix[@order - 1]; end | |
| def buttom_left; @matrix[@order * (@order - 1)]; end | |
| def buttom_right; @matrix[@order**2 - 1]; end | |
| def column_indices(x) | |
| (0..(@order - 1)).map{|i| i * @order + x} | |
| end | |
| def row_indices(y) | |
| (0..(@order - 1)).map{|i| i + @order * y} | |
| end | |
| def diagonal_indices1 | |
| (0..(@order - 1)).map{|i| (@order + 1) * i} | |
| end | |
| def diagonal_indices2 | |
| (1..@order).map{|i| (@order - 1) * i} | |
| end | |
| def sum_cells(indices) | |
| indices.inject(0) {|sum, i| sum += @matrix[i]} | |
| end | |
| def coordinate(cell) | |
| x = cell % @order | |
| y = cell / @order | |
| return x, y | |
| end | |
| def col_width | |
| @col_width ||= @items.max.to_s.size | |
| end | |
| def to_s | |
| @matrix.map! { |e| e ? e : 0} | |
| @matrix.each_slice(@order) do |arr| | |
| print "|" | |
| arr.each do |e| | |
| print "%#{col_width}d|" % e | |
| end | |
| puts | |
| end | |
| end | |
| end | |
| class Matrix | |
| attr_accessor :items, :matrix, :order | |
| include Utils | |
| def initialize(arg) | |
| case arg | |
| when Array then arr = arg | |
| when Range then arr = arg.to_a | |
| end | |
| raise "Not a squre" unless arr.size.square_number? | |
| @order = Math.sqrt(arr.size).to_i | |
| @items = arr | |
| @matrix = Array.new(@order**2, 0) | |
| end | |
| def self.duplicate(arg) | |
| Marshal.load(Marshal.dump(arg)) | |
| end | |
| def next_blank_position | |
| p = matrix.take_while{|i| i != 0}.size | |
| p != matrix.size ? p : false | |
| end | |
| def candidate_numbers(cell) | |
| left = items - matrix | |
| x, y = coordinate(cell) | |
| case | |
| when x == @order -1 | |
| num = magic_constant - sum_cells(row_indices(y)) | |
| left.include?(num) ? [num] : nil | |
| when y == @order -1 | |
| num = magic_constant - sum_cells(column_indices(x)) | |
| left.include?(num) ? [num] : nil | |
| else | |
| left.select { |i| | |
| sum_cells(row_indices(y)) + i <= magic_constant && | |
| sum_cells(column_indices(x)) + i <= magic_constant | |
| } | |
| end | |
| end | |
| def symmetry_constraint_fullfilled? | |
| if top_left * top_right * buttom_left * buttom_right == 0 | |
| true | |
| else | |
| top_left > top_right && | |
| top_left > buttom_left && | |
| top_left > buttom_right && | |
| top_right > buttom_left | |
| end | |
| end | |
| def magic? | |
| return false unless sum_cells(diagonal_indices1) == magic_constant | |
| return false unless sum_cells(diagonal_indices2) == magic_constant | |
| 0.upto(@order - 1) do |i| | |
| if sum_cells(column_indices(i)) != magic_constant || | |
| sum_cells(column_indices(i)) != magic_constant | |
| return false | |
| end | |
| end | |
| true | |
| end | |
| end | |
| class Solver | |
| def initialize(matrix) | |
| @matrix = matrix | |
| end | |
| def solve | |
| if @matrix.next_blank_position | |
| stack = place_a_new_number_in_the_next_blank_cell(@matrix) | |
| while !stack.empty? | |
| matrix = Matrix.duplicate(stack.shift) | |
| Solver.new(matrix).solve | |
| end | |
| else | |
| if @matrix.magic? | |
| p @matrix if @matrix.magic? | |
| else | |
| end | |
| end | |
| end | |
| def place_a_new_number_in_the_next_blank_cell(matrix) | |
| stack = [] | |
| if cell = matrix.next_blank_position | |
| nums = matrix.candidate_numbers(cell) | |
| return stack unless nums | |
| nums.each do |e| | |
| new_matrix = Matrix.duplicate(matrix) | |
| new_matrix.matrix[cell] = e | |
| stack << new_matrix if new_matrix.symmetry_constraint_fullfilled? | |
| end | |
| end | |
| stack | |
| end | |
| end | |
| end | |
| include MagicMatrix | |
| if __FILE__ == $0 | |
| # m = Matrix.new([17, 113, 47, 89, 59, 29, 71, 5, 101]) | |
| m = Matrix.new([8, 1, 6, 3, 5, 7, 4, 9, 2]) | |
| # m = Matrix.new((1..16)) | |
| # m[0,0] = 1 | |
| # m = Matrix.new((1..9)) | |
| Solver.new(m).solve | |
| exit | |
| end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment