如何将9x9阵列拆分为9个3x3组件

Question

我有一个代表数独游戏的9x9多维数组.我需要将其分解为9个3x3多个组件.怎么做？我完全不知道从哪里开始.

game = [
[1, 3, 2, 5, 7, 9, 4, 6, 8],
[4, 9, 8, 2, 6, 1, 3, 7, 5],
[7, 5, 6, 3, 8, 4, 2, 1, 9],
[6, 4, 3, 1, 5, 8, 7, 9, 2],
[5, 2, 1, 7, 9, 3, 8, 4, 6],
[9, 8, 7, 4, 2, 6, 5, 3, 1],
[2, 1, 4, 9, 3, 5, 6, 8, 7],
[3, 6, 5, 8, 1, 7, 9, 2, 4],
[8, 7, 9, 6, 4, 2, 1, 5, 3]
]

分成几块,就变成了

chunk_1 = [
[1, 3, 2],
[4, 9, 8],
[7, 5, 6]
]

chunk_2 = [
[5, 7, 9],
[2, 6, 1],
[3, 8, 4]
]

...and so on

Answer 1

那是一个有趣的练习！

回答

game.each_slice(3).map{|stripe| stripe.transpose.each_slice(3).map{|chunk| chunk.transpose}}.flatten(1)

这会很麻烦，而且不需要定义每个chunk_1, chunk_2, ....

如果你愿意chunk_2，你可以使用extract_chunks(game)[1]

它输出[chunk_1, chunk_2, chunk_3, ..., chunk_9]，所以它是一个 Arrays of Arrays 数组：

1 3 2
4 9 8
7 5 6

5 7 9
2 6 1
3 8 4

4 6 8
3 7 5
2 1 9

6 4 3
5 2 1
...

您可以定义一个方法来检查此网格是否有效（它是）：

def extract_chunks(game)
  game.each_slice(3).map{|stripe| stripe.transpose.each_slice(3).map{|chunk| chunk.transpose}}.flatten(1)
end

class Array # NOTE: Use refinements if you don't want to patch Array
  def has_nine_unique_elements?
    self.flatten(1).uniq.size == 9
  end
end

def valid?(game)
  game.has_nine_unique_elements? &&
  game.all?{|row| row.has_nine_unique_elements? } &&
  game.all?{|column| column.has_nine_unique_elements? } &&
  extract_chunks(game).all?{|chunk| chunk.has_nine_unique_elements? }
end

puts valid?(game) #=> true

理论

• 大网格可以切成3 条，每条包含 3 行，每行 9 个单元格。
• 第一个条带将包含 chunk_1、chunk_2 和 chunk_3。
• 我们需要将条带垂直切成 3 块。这样做：
  • 我们转置条带，
  • 用 水平切割each_slice，
  • 再转回去。
• 我们对条纹 #2 和 #3做同样的事情。
• 为了避免返回单元格行块的条纹数组，我们使用flatten(1)删除一个级别并返回单元格行块的数组。:)

Answer 2

Matrix#minor方法是为此量身定制的:

require 'matrix'

def sub3x3(game, i, j)
  Matrix[*game].minor(3*i, 3, 3*j, 3).to_a
end

chunk1 = sub3x3(game, 0, 0)
  #=> [[1, 3, 2], [4, 9, 8], [7, 5, 6]] 
chunk2 = sub3x3(game, 0, 1)
  #=> [[5, 7, 9], [2, 6, 1], [3, 8, 4]] 
chunk3 = sub3x3(game, 0, 2)
  #=> [[4, 6, 8], [3, 7, 5], [2, 1, 9]] 
chunk4 = sub3x3(game, 1, 0)
  #=> [[6, 4, 3], [5, 2, 1], [9, 8, 7]]
...
chunk9 = sub3x3(game, 2, 2)
  #=> [[6, 8, 7], [9, 2, 4], [1, 5, 3]] 

Ruby没有数组"行"和"列"的概念.因此,为了方便起见,我将参考3x3"子阵列" game,在偏移i和j(i = 0,1,2,j = 0,1,2),作为3x3子矩阵,m = Matrix[*game]其左上角值在行偏移3*i和列偏移3*j处m,转换为数组.

这是相对低效的,因为为计算每个"块"创建了新矩阵.考虑到阵列的大小,这不是一个问题,而是提高效率,而不是重新考虑整体设计.创建九个局部变量(而不是一个九个数组的数组)是不可取的.

这里有一个建议,一旦所有开放单元格被填满,就检查game(使用上述方法sub3x3)的有效性.请注意,我使用了游戏的Wiki描述,其中唯一有效的条目是数字1-9,并且我假设当玩家在单元格中输入值时代码强制执行该要求.

def invalid_vector_index(game)
  game.index { |vector| vector.uniq.size < 9 }
end

def sub3x3_invalid?(game, i, j)
  sub3x3(game, i, j).flatten.uniq.size < 9
end

def valid?(game)
  i = invalid_vector_index(game)
  return [:ROW_ERR, i] if i
  j = invalid_vector_index(game.transpose)
  return [:COL_ERR, j] if j
  m = Matrix[*game]
  (0..2).each do |i|
    (0..2).each do |j|
      return [:SUB_ERR, i, j] if sub3x3_invalid?(game, i, j)
    end
  end
  true
end

valid?(game)
  #=> true

请注意,这要么返回true,意思game是有效,要么是一个表示解决方案无效的数组,并且包含可用于通知玩家原因的信息.

现在试试

game[5], game[6] = game[6], game[5]

所以

game
  #=> [[1, 3, 2,   5, 7, 9,   4, 6, 8],
  #    [4, 9, 8,   2, 6, 1,   3, 7, 5],
  #    [7, 5, 6,   3, 8, 4,   2, 1, 9],

  #    [6, 4, 3,   1, 5, 8,   7, 9, 2],
  #    [5, 2, 1,   7, 9, 3,   8, 4, 6],
  #    [2, 1, 4,   9, 3, 5,   6, 8, 7],

  #    [9, 8, 7,   4, 2, 6,   5, 3, 1],
  #    [3, 6, 5,   8, 1, 7,   9, 2, 4],
  #    [8, 7, 9,   6, 4, 2,   1, 5, 3]] 

valid?(game)
  #=> [:SUB_ERR, 1, 0]

行和列显然仍然有效,但此返回值表示至少有一个3x3子数组无效且数组

[[6, 4, 3],
 [5, 2, 1],
 [2, 1, 4]]

是第一个发现无效的.