MiddleКодИногдаЕщё не отвечали
Напишите код для решения судоку
Дана доска судоку 9×9, где пустые клетки равны 0. Заполните доску так, чтобы каждая строка, столбец и блок 3×3 содержали цифры 1–9 ровно по разу. Верните true, если доска решаема (и оставьте её заполненной), иначе false.
Требования:
и блок 3×3, а не всю доску.
- Для каждой постановки проверяйте только затронутые строку, столбец
- В тупике отменяйте постановку и пробуйте следующую цифру (поиск с возвратом).
#include <array>
using Board = std::array<std::array<int, 9>, 9>;
bool solve(Board& b) {
// ваш код здесь
}Допишите реализацию.
Используйте поиск с возвратом: найдите первую пустую клетку, попробуйте цифры 1–9, проверьте ограничения строки/столбца/блока, рекурсируйте. Если ни одна цифра не подходит — откат. Теоретически O(9^m), где m — количество пустых клеток, но отсечение ограничений делает алгоритм быстрым на практике.
- ✗Проверять всю доску на каждом шаге вместо только затронутых строки, столбца и блока
- ✗Не возвращать
trueпри нахождении решения — рекурсия должна передавать успех наверх - ✗Использовать 1-индексированные координаты, вызывающие ошибки на единицу в вычислении блока
- →Как распространение ограничений (дуговая согласованность) улучшает производительность поиска с возвратом?
- →Что такое эвристика 'наиболее ограниченная переменная' при выборе следующей клетки?
Оглавление
Задача
Реализуйте решение судоку методом поиска с возвратом (backtracking).
Решение
#include <array>
#include <cassert>
using Board = std::array<std::array<int, 9>, 9>;
bool isValid(const Board& b, int row, int col, int num) {
// Проверка строки и столбца
for (int i = 0; i < 9; ++i) {
if (b[row][i] == num || b[i][col] == num) return false;
}
// Проверка блока 3x3
int br = (row / 3) * 3, bc = (col / 3) * 3;
for (int r = br; r < br + 3; ++r)
for (int c = bc; c < bc + 3; ++c)
if (b[r][c] == num) return false;
return true;
}
bool solve(Board& b) {
for (int r = 0; r < 9; ++r) {
for (int c = 0; c < 9; ++c) {
if (b[r][c] != 0) continue; // уже заполнена
for (int num = 1; num <= 9; ++num) {
if (isValid(b, r, c, num)) {
b[r][c] = num;
if (solve(b)) return true; // решение найдено
b[r][c] = 0; // откат
}
}
return false; // ни одно значение не подошло
}
}
return true; // все клетки заполнены
}
int main() {
Board board = {{
{5,3,0, 0,7,0, 0,0,0},
{6,0,0, 1,9,5, 0,0,0},
{0,9,8, 0,0,0, 0,6,0},
{8,0,0, 0,6,0, 0,0,3},
{4,0,0, 8,0,3, 0,0,1},
{7,0,0, 0,2,0, 0,0,6},
{0,6,0, 0,0,0, 2,8,0},
{0,0,0, 4,1,9, 0,0,5},
{0,0,0, 0,8,0, 0,7,9}
}};
assert(solve(board));
// Проверяем несколько известных значений
assert(board[0][2] == 4);
assert(board[1][1] == 7);
}Ключевые моменты
- Backtracking: попробовать → рекурсия → откат при неудаче.
isValidпроверяет только строку, столбец и блок — не всю доску.- Оптимизация: выбирать клетку с наименьшим числом возможных значений (MRV-эвристика).
- Для сложных головоломок добавьте constraint propagation перед backtracking.
Оглавление
