Какую структуру данных представить для головоломки Судоку, и решить ее, найдя голый одиночный / скрытый одиночный

Question

Я сомневаюсь, какую из следующих двух структур данных следует использовать для представления доски судоку, чтобы решить ее с помощью техники голый сингл и скрытый сингл .

1.

//using bool array to store candidates of a cell.
int[,] board = new int[9,9];
bool[,] isFixed = new bool[9,9]; // determine cell is fixed.
bool[,,] candidates = new bool[9,9,9];

таким образом, мы можем проверить, содержит ли ячейка (строка, столбец) кандидата n, проверив, истинно ли candidates[row, col, n] или ложно

2.

int[,] board = new int[9,9];
bool[,] isFixed = new bool[9,9]; // determine cell is fixed.
bool[,] row = new bool[9,9]; //row(1,2) = true means number 2 was already appear (is solved or fixed) in 1st row
bool[,] col = new bool[9,9]; //col(1,2) = true means number 2 was already appear (is solved or fixed) in 1st col
bool[,] square3x3 = new bool[9,9]; //square3x3 (1,2) = true means number 2 was already appear (is solved or fixed) in 1st square3x3

таким образом, мы можем проверить, содержит ли ячейка (r, c) кандидата n, проверив, является ли выражение row[r, n] && col[c, n] && square3x3[r/3 * 3 + c/3, n] истинным или ложным

, когдаопределенная ячейка решается с номером n, 1-й способ, мы должны обновить кандидатов всех 3x9 ячеек в строке, col, square3x3 определенной ячейки, в то время как 2-й способ, мы просто устанавливаем только row [, n], col [,n] и square3x3 [, n] в true.

Но я не уверен, какой способ целесообразно и эффективно найти голый сингл и скрытый сингл.

Кто-нибудь может предложить мне алгоритм поиска скрытого сингла?

Помогите, спасибо!

Answer 1

Лично я бы не использовал набор базовых массивов, которые вы должны были бы синхронизировать, но класс Board.

Внутри него был бы массив элементов Field размером 9x9, который содержал бы необязательный элемент.(int?) заданное число, необязательное производное число и список (bool[9]) кандидатов.

Этот класс предоставит некоторые свойства / методы для доступа к определенной ячейке или строке / столбцу / блоку.

Answer 2

Когда я сам решал судоку, мне не хватило всего двух многомерных массивов.

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

Вероятно, вы можете получить некоторые идеи из моего кода (правда, в Ruby)

https://github.com/stulentsev/sudoku-solver/blob/master/solver.rb