main question: can subarray out of array e.g. sub = a[2, 3]. if have 2d array, how can 2d subarray?
practical example: i'm trying iterate on 9 3x3 squares in sudoku board, check each 3x3 square duplicate numbers.
if have array (board) of 9 arrays (rows), there easy way 3x3 sub-2d-array of board? there easy way go through 9 of 3x3 sub-2d-arrays?
edit: sorry if original wasn't clear, main thing principle of getting portion of 2d array, sudoku part more of application of principle.
you determine if sudoku solution valid follows. checking 3x3 blocks simplified using method array#minor.
code
require 'matrix' def valid?(soln) rows_invalid = invalid_rows?(soln, "rows") cols_invalid = invalid_rows?(soln.transpose, "columns") blocks_invalid = invalid_blocks?(soln) puts "solution valid" unless rows_invalid || cols_invalid || blocks_invalid end def invalid_rows?(soln, label) rows_with_dups = soln.each.with_index(1).select { |r,i| r.uniq.size < r.size } return false if rows_with_dups.empty? puts "duplicates in #{label}: #{ rows_with_dups.map(&:last).join(' ') }" return true end def invalid_blocks?(soln) m = matrix[*soln] blocks_with_dups = [1,2,3].product([1,2,3]).select |row,col| f_row, f_col = 3*(row-1), 3*(col-1) block = m.minor(f_row..(f_row+2), f_col..(f_col+2)).to_a.flatten block.uniq.size < block.size end return false if blocks_with_dups.empty? puts "duplicates in blocks: #{ blocks_with_dups.map { |row,col| "(#{row}, #{col})" }.join(' ') }" return true end
examples
soln = [ %w| 4 1 7 8 5 3 9 6 2 |, %w| 5 8 9 7 6 2 4 3 1 |, %w| 6 3 2 9 1 4 7 5 8 |, %w| 9 6 8 3 2 1 5 7 4 |, %w| 7 2 3 4 8 5 1 9 6 |, %w| 1 5 4 6 7 9 8 2 3 |, %w| 8 4 6 2 9 7 3 1 5 |, %w| 2 7 1 5 3 8 6 4 9 |, %w| 3 9 5 1 4 6 2 8 7 |, ] #=> [["4", "1", "7", "8", "5", "3", "9", "6", "2"], # ["5", "8", "9", "7", "6", "2", "4", "3", "1"], # ["6", "3", "2", "9", "1", "4", "7", "5", "8"], # ["9", "6", "8", "3", "2", "1", "5", "7", "4"], # ["7", "2", "3", "4", "8", "5", "1", "9", "6"], # ["1", "5", "4", "6", "7", "9", "8", "2", "3"], # ["8", "4", "6", "2", "9", "7", "3", "1", "5"], # ["2", "7", "1", "5", "3", "8", "6", "4", "9"], # ["3", "9", "5", "1", "4", "6", "2", "8", "7"]] valid?(soln) #=> "solution valid"
now change 2 elements in soln
:
soln[0][5] = "7" soln[8][8] = "3" soln.map { |row| row.join(' ') } #=> ["4 1 7 8 5 7 9 6 2", # "5 8 9 7 6 2 4 3 1", # "6 3 2 9 1 4 7 5 8", # "9 6 8 3 2 1 5 7 4", # "7 2 3 4 8 5 1 9 6", # "1 5 4 6 7 9 8 2 3", # "8 4 6 2 9 7 3 1 5", # "2 7 1 5 3 8 6 4 9", # "3 9 5 1 4 6 2 8 3"] valid?(soln) #=> duplicates in rows: 1 9 # duplicates in columns: 6 9 # duplicates in blocks: (1, 2) (3, 3)
Comments
Post a Comment