Коробка судоку индексирует начальную позицию

Я реализую решатель судоку, используя поиск с возвратом. Он читает доску судоку в виде:

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, но на самом деле это не имеет значения, так как теперь я хочу понять суть этой формулы.


algorithm language-agnostic sudoku
person Paul    schedule 01.06.2013    source источник
comment
Используйте бумагу и карандаш. Термины (i / 27) и int((i % 9) / 3) делят поле на три горизонтальные и три вертикальные полосы, которые затем объединяются/пересекаются с помощью a+3*b в сетку 3x3.   -  person wildplasser    schedule 01.06.2013

Ответы (2)


arrow_upward
2
arrow_downward

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)
person Michael Butscher    schedule 01.06.2013

arrow_upward
2
arrow_downward

Извините, что некропилюю, но вот решение, которое может кому-то показаться интересным (при условии, что вы умеете читать шепелявость; в данном случае 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))

которые являются индексами каждого сектора стандартной доски судоку (проверено).

person Carcigenicate    schedule 04.11.2016