Ежедневный бит (е) C ++ # 161, Распространенная задача на собеседовании: решение судоку.
Сегодня мы рассмотрим распространенную задачу интервью C++: решение судоку.
Дана головоломка судоку в виде std::vector‹std::vector‹char››, где незаполненные пробелы представлены в виде пробела, решите головоломку.
Правила судоку:
- каждая из девяти строк, столбцов и полей 3x3 должна содержать все цифры 1..9
Прежде чем вы продолжите читать решение, я рекомендую вам попробовать решить его самостоятельно. Вот проводник компилятора, связанный с парой тестов: https://compiler-explorer.com/z/MnG9EG1jf.
Решение
Хотя можно реализовать решатель судоку, который не угадывает, это проект на многие выходные (судя по опыту), а не то, что нужно делать во время собеседования по программированию. Однако в то же время мы не хотим реализовывать простой алгоритм угадывания, который выполняет головоломку методом грубой силы.
Хорошей золотой серединой является применение ограничения судоку; каждое число может появляться только один раз в каждой строке, столбце и поле. Это означает, что нет смысла угадывать число, уже присутствующее в соответствующей строке, столбце или поле. Кроме того, если мы приходим к ситуации, когда у нас нет вариантов угадать, мы знаем, что этот конкретный путь угадывания недействителен.
Нам не нужно постоянно перепроверять, какие числа уже присутствуют в строке/столбце/поле. Вместо этого мы можем отслеживать используемые числа для каждой строки/столбца/поля по мере изучения головоломки, добавляя числа по мере предположения и удаляя их при откате от плохого решения.
/* Calculate the corresponding box for row/col coordinates:
0 1 2
3 4 5
6 7 8
Any mapping will work, as long as it is consistent.
*/
int get_box(int64_t row, int64_t col) {
return (row/3)*3+col/3;
}
// Get the next empty space
std::pair<int64_t,int64_t> next(
const std::vector<std::vector<char>>& puzzle,
int64_t row, int64_t col) {
int64_t start = col;
for (int64_t i = row; i < std::ssize(puzzle); ++i)
for (int64_t j = std::exchange(start,0);
j < std::ssize(puzzle[i]); ++j)
if (puzzle[i][j] == ' ')
return {i,j};
return {-1,-1};
}
bool backtrack(
std::vector<std::vector<char>>& puzzle,
std::array<std::bitset<9>,9>& row,
std::array<std::bitset<9>,9>& col,
std::array<std::bitset<9>,9>& box,
int64_t r_curr, int64_t c_curr) {
// next coordinate to fill
auto [r_next, c_next] = next(puzzle, r_curr, c_curr);
// {-1,-1} means there is no unfilled space,
// i.e. we have solved the puzzle
if (r_next == -1 && c_next == -1)
return true;
// The candidate numbers for this space cannot
// repeat in the row, column or box.
auto candidates = row[r_next];
candidates |= col[c_next];
candidates |= box[get_box(r_next,c_next)];
// Guess a number
for (int64_t i = 0; i < 9; ++i) {
// Already in a row, column or box
if (candidates[i]) continue;
// Mark it on the puzzle, row, column and box
puzzle[r_next][c_next] = '1'+i;
row[r_next][i] = true;
col[c_next][i] = true;
box[get_box(r_next,c_next)][i] = true;
if (backtrack(puzzle,row,col,box,r_next,c_next))
return true;
// we get false if this was a guess
// that didn't lead to a solution
// Unmark from the box, column, row and puzzle
box[get_box(r_next,c_next)][i] = false;
col[c_next][i] = false;
row[r_next][i] = false;
puzzle[r_next][c_next] = ' ';
// And try the next digit
}
return false;
}
bool solve(std::vector<std::vector<char>>& puzzle) {
std::array<std::bitset<9>,9> row;
std::array<std::bitset<9>,9> col;
std::array<std::bitset<9>,9> box;
// Preprocessing step, mark the starting clues
// in the corresponding rows, columns and boxes
for (int64_t i = 0; i < 9; ++i)
for (int64_t j = 0; j < 9; ++j)
if (puzzle[i][j] != ' ') {
int64_t digit = puzzle[i][j]-'1';
row[i][digit] = true;
col[j][digit] = true;
box[get_box(i,j)][digit] = true;
}
return backtrack(puzzle,row,col,box,0,0);
}
