Ежедневен бит(д) на C++ #161, Често срещан проблем за интервю: Sudoku Solver.
Днес ще разгледаме често срещан проблем за интервю в C++: решаване на судоку.
Даден е судоку пъзел като std::vector‹std::vector‹char››, където незапълнените интервали са представени като интервал, решете пъзела.
Правила на судоку:
- всеки от деветте реда, колони и кутии 3x3 трябва да съдържа всички цифри 1..9
Преди да продължите да четете решението, препоръчвам ви да опитате да го решите сами. Ето програма за изследване на компилатор, свързана с няколко тестови случая: https://compiler-explorer.com/z/MnG9EG1jf.
Решение
Въпреки че е възможно да се приложи решаване на судоку, което не предполага, това е проект за много уикенди (говорейки от опит), а не нещо, което да правите по време на интервю за кодиране. В същото време обаче не искаме да внедрим директен инструмент за решаване на отгатвания, който грубо подрежда пъзела.
Хубаво средно положение е прилагането на ограничението Sudoku; всяко число може да се появи само веднъж във всеки ред, колона и поле. Това означава, че няма смисъл да гадаете число, което вече присъства в съответния ред, колона или кутия. Освен това, ако стигнем до ситуация, в която нямаме опции за отгатване, знаем, че този конкретен път за отгатване е невалиден.
Не е нужно да проверяваме отново кои числа вече присъстват в ред/колона/кутия. Вместо това можем да следим използваните числа за всеки ред/колона/кутия, докато изследваме пъзела, като добавяме числата, както предполагаме, и ги премахваме, когато се връщаме от лошо решение.
/* 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);
}
