1

我正在使用回溯实现数独求解器。它以以下形式读取数独板：

027800061000030008910005420500016030000970200070000096700000080006027000030480007

我知道如何通过做index % 9（然后做一个简单的比率为 9 的算术级数）来计算列上的元素，以及通过使用来计算一行上的元素index/9（然后添加一个直到我得到每个元素）来计算列上的元素，其中index 是 [0,80] 范围内的数字。

我无法弄清楚的是，如果我在该框中有一个元素的索引，如何获取该框的起始索引。

所以我用谷歌搜索得到：http: //jakevdp.github.io/blog/2013/04/15/code-golf-in-python-sudoku/

这家伙正在这样的框中获取起始索引：

start = 27 * int(i / 27) + 3 * int((i % 9) / 3)i我的元素列表中的索引在 哪里。

我无法理解他是如何计算出这个公式的，我该如何自己推导出来，所以请给我解释一下。

我理解这个公式之后的列表理解，这一切都有意义，只是不是这个公式。

PS：我写这篇文章是为了学习 Haskell，但这真的没关系，因为现在我想了解那个公式的要点。

4

2 回答 2

2

index表示索引到您的列表中。blockRow,blockCol并blockIndex参考块开始的行/列/索引。所有除法都是整数除法（向下舍入到下一个整数）。

index = row*9 + col

row = index / 9
col = index % 9

blockRow = (row / 3) * 3
blockCol = (col / 3) * 3

blockRow = (index / 9 / 3) * 3 = (index / 27) * 3
blockCol = (index % 9 / 3) * 3

blockIndex = (blockRow*9) + blockCol = ((index / 27) * 3 * 9) + (index % 9 / 3) * 3  = 
(index / 27) * 27 + 3 * (index % 9 / 3)
于 2013-06-01T12:55:18.110 回答
2

很抱歉破坏了这个，但这是一个有人可能会觉得有趣的解决方案（前提是你可以阅读 lisps；在这种情况下是 Clojure）。它返回数独板的每个“扇区”的索引，并且足够通用，可用于许多不同的板尺寸。standard-9-sector-indices假设电路板分为 9 个扇区，因此电路板宽度/高度应为 3 的倍数。get-sector-indices可用于任何电路板尺寸，但是：

(defn get-sector-indices [board-width sector-top-left-pos sector-dimensions]
  (let [[sw sh] sector-dimensions
        [tx ty] sector-top-left-pos]
    (for [y (range ty (+ ty sh))
          x (range tx (+ tx sw))]
      (+ x (* y board-width)))))

(defn standard-9-sector-indices [board-dimensions]
  (let [[bw bh] board-dimensions
        [sw sh :as sd] (map #(/ % 3) board-dimensions)]
       (for [y (range 0 bh sh)
             x (range 0 bw sw)]
         (get-sector-indices bw [x y] sd))))

维度参数应该是表示一[x y]对的向量/列表。

(standard-9-sector-indices [9 9])

回报：

((0 1 2 9 10 11 18 19 20)
 (3 4 5 12 13 14 21 22 23)
 (6 7 8 15 16 17 24 25 26)
 (27 28 29 36 37 38 45 46 47)
 (30 31 32 39 40 41 48 49 50)
 (33 34 35 42 43 44 51 52 53)
 (54 55 56 63 64 65 72 73 74)
 (57 58 59 66 67 68 75 76 77)
 (60 61 62 69 70 71 78 79 80))

这是标准数独板（经过测试）的每个扇区的指数。

于 2016-11-04T23:18:21.410 回答