массивы — C ++, используя списки для решения судоку
Я пытаюсь сделать решение судоку на C ++. Я хочу сохранить массив из [9] в [9] (очевидно). Сейчас я выясняю способ отслеживать возможные значения. Я думал о списке для каждой записи в массиве. Итак, список изначально имеет номера от 1 до 9, и на каждой итерации я смог бы избавиться от некоторых значений.
Теперь мой вопрос: могу ли я назначить один список каждой записи в двумерном массиве, если да, то как? И еще есть другой / лучший вариант?
Я начинающий программист, и это в основном мой первый проект на C ++.
заранее спасибо!
Решение
Одним простым решением является использование набора однобитовых флагов для каждого квадрата, например,
uint16_t board[9][9]; // 16 x 1 bit flags for each square where 9 bits are used
// to represent possible values for the square
Затем вы можете использовать побитовые операторы для установки / очистки / проверки каждого бита, например,
board[i][j] |= (1 << n); // set bit n at board position i, j
board[i][j] &= ~(1 << n); // clear bit n at board position i, j
test = (board[i][j] & (1 << n)) != 0; // test bit n at board position i, j
Другие решения
Ну, вы можете создать массив множеств, выполнив
std::array<std::set<int>,81> possibleValues;
например. Вы можете заполнить этот массив всеми возможностями, написав
const auto allPossible = std::set<int>{ 0, 1, 2, 3, 4, 5, 6, 7, 8 };
std::fill( std::begin(possibleValues), std::end(possibleValues),
allPossible );
если вы используете современный компилятор C ++ 11. Вот как вы можете установить / очистить и протестировать каждую запись:
possibleValues[x+9*y].insert( n ); // sets that n is possible at (x,y).
possibleValues[x+9*y].erase( n ); // clears the possibility of having n at (x,y).
possibleValues[x+9*y].count( n ) != 0 // tells, if n is possible at (x,y).
Если производительность является проблемой, вы можете использовать битовые операции, а не (относительно) тяжелые std::set операции. В этом случае используйте
std::array<short, 81> possibleValues;
std::fill( begin(possibleValues), end(possibleValues), (1<<10)-1 );
Значение n возможно для поля (x,y), если и только если possibleValues[x+9*y] & (1<<n) != 0где все индексы начинаются с 0 в этом случае.
Вы всегда можете думать о своей судоку как о трехмерном массиве, создающем трехмерное измерение для хранения возможных значений, и в основном:
// set "1" in cell's which index corespond to a possible value for the Sudoku cell
for (int x = 0; x < 9; x++)
for (int y = 0; y < 9; y++)
for (int i = 1; i < 10; i++)
arr[x][y][i] = 1;
а также arr[x][y][0] содержит значение вашего судоку.
например, для удаления значения «5» для ячейки [x][y] просто измените значение arr[x][y][5] = 0