Разделение двумерного массива 9x9 на 9 подсеток (как в судоку)? (С++)

Я пытаюсь закодировать решатель судоку, и то, как я пытался это сделать, заключалось в том, чтобы иметь сетку указателей 9x9, содержащих адрес «установленных» объектов, которые обладают либо решением, либо допустимыми возможными значениями.

Я смог пройти через массив с 2 циклами for, сначала через каждый столбец, а затем перейти к следующей строке и повторить.

Однако мне трудно представить, как бы я обозначил, к какой подсетке (или блоку, блоку и т. д.) принадлежит конкретная ячейка. Мое первоначальное впечатление состояло в том, что операторы if в циклах for, например, если строка ‹ 2 (строки начинаются с 0) и столбец ‹ 2, то мы находимся в 1-м блоке, но это кажется запутанным. Будет ли лучший способ сделать это?


c++ multidimensional-array sudoku
person kevin    schedule 17.01.2011    source источник
comment
если (i,j) — координаты ячейки, то (i/3,j/3) — координаты блока.   -  person Yakov Galka    schedule 18.01.2011
comment
Для решателя содоку вы можете немного подумать о скорости и использовать предварительно рассчитанные таблицы поиска. Массив из 81 элемента для поиска блока, в котором находится ячейка, будет быстрым и простым. Не ответ, потому что вам все еще нужно сгенерировать этот массив, хотя вы можете просто заполнить его вручную как статический блок данных, если вы достаточно терпеливы.   -  person Steve314    schedule 18.01.2011
comment
@ Steve314 Steve314 При рассмотрении скорости предпочитайте простые вычисления поиску. Полное чтение памяти стоит дорого. Только когда ответ оказывается в кеше L1, его поиск может быть не медленнее (но он все еще занимает ценное пространство кеша L1).   -  person Sjoerd    schedule 18.01.2011
comment
@Sjoerd - 81-байтовая таблица не совсем велика, и, учитывая, что весь алгоритм короткий, она все равно должна находиться в кеше L1 для всех вызовов, кроме первого. Но вы, вероятно, правы в том, что простой расчет меньше, если подумать.   -  person Steve314    schedule 26.01.2011

Ответы (3)


arrow_upward
8
arrow_downward

Вы можете вычислить номер блока из строки и столбца следующим образом:

int block = (row/3)*3 + (col/3);

Это нумерует блоки следующим образом:

+---+---+---+
| 0 | 1 | 2 |
+---+---+---+
| 3 | 4 | 5 |
+---+---+---+
| 6 | 7 | 8 |
+---+---+---+
person sth    schedule 17.01.2011
comment
Я собирался опубликовать тот же ответ. - person Sjoerd; 18.01.2011

arrow_upward
1
arrow_downward

Я бы создал таблицу поиска с 81 записью. Каждая запись относится к ячейке в сетке 9x9 и дает вам необходимую информацию (какое поле, какой столбец, какая строка, ...)

person Christian Ammer    schedule 17.01.2011

arrow_upward
0
arrow_downward

Я использую это сам (но затем в python, предполагая, что x и y идут от 0 до 9 эксклюзивно):

int bx, by;
for (bx = (x/3)*3; bx < (x/3)*3 + 3; bx++) {
    for (by = (y/3)*3; by < (y/3)*3 + 3; by++) {
        // bx and by will now loop over each number in the block which also contains x, y
    }
}
person orlp    schedule 17.01.2011