Эффективность между списками и методами

Question

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

1) Что будет быстрее?

А) Пройдите через все пустые места, получите список чисел(1-9) удалите их, если они находятся в той же строке или в той же категории, а если это длина 1, добавьте только один оставшийся.Повторите это, пока необходимо.

B) Пройдите по всем числам, затем проверьте все места, чтобы видеть, может ли у них быть тот номер.Повторите это, пока необходимо.

2) Какой самый эффективный список для размещения списка длиной до 9?

Спасибо,

Легенда

Answer 1

Я думаю, что B работает!Вы можете использовать алгоритм возврата, чтобы проверить пустое место с любым из номеров 1-9 (по порядку).Заполните место с первым доступным выбором (1-9) и двигаться вперед.Если в какой-то момент вы не можете вставить номер в слот, вернитесь к предыдущему слоту и попробуйте другой номер.Это может быть полезно:

http://edwinchan.wordpress.com/2006/01/08/sudoku-solver-in-c-using-backtracking/

Answer 2

Ответ 2) Не список, а набор имеет смысл. В этом случае BitSet.

Случай 1) В судоку 9х9 есть 27 правил.

Случай 1А) Каждое место участвует в 3 правилах.

Случай 1B) Каждое число повторяется 9 раз; появляется в 3 правилах.

Ответ 1) 1A и 1B теоретически не должны отличаться, но 1A, кажется, облегчает алгоритм и структуру данных.