Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Решение судоку: алгоритмы и подход
Да, я решал судоку и с алгоритмической, и с практической точек зрения. Судоку — отличный пример для развития навыков решения проблем, понимания рекурсии, backtracking алгоритмов и оптимизации кода. Это задача, которая часто появляется на собеседованиях, потому что демонстрирует способность разработчика к логическому мышлению.
Основные правила судоку
Судоку — это головоломка на сетке 9x9 ячеек, разделённой на 9 подсеток 3x3:
- В каждой строке цифры 1-9 встречаются ровно один раз
- В каждом столбце цифры 1-9 встречаются ровно один раз
- В каждом блоке 3x3 цифры 1-9 встречаются ровно один раз
- Некоторые ячейки уже заполнены, остальные нужно заполнить
Алгоритм с использованием Backtracking
Это наиболее эффективный подход для решения судоку:
public class SudokuSolver {
private static final int SIZE = 9;
private static final int EMPTY = 0;
private int[][] board;
public SudokuSolver(int[][] board) {
this.board = board;
}
/**
* Основной метод решения судоку
* Использует Backtracking для перебора всех возможных вариантов
*/
public boolean solve() {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
// Пропускаем уже заполненные ячейки
if (board[row][col] == EMPTY) {
// Пробуем вставить цифры от 1 до 9
for (int num = 1; num <= SIZE; num++) {
if (isValid(row, col, num)) {
// Если цифра валидна, помещаем её
board[row][col] = num;
// Рекурсивно решаем оставшуюся часть
if (solve()) {
return true; // Решение найдено
}
// Если не помогло, откатываемся (backtrack)
board[row][col] = EMPTY;
}
}
// Если ни одна цифра не подошла, нужно откатиться
return false;
}
}
}
// Все ячейки заполнены, решение найдено
return true;
}
/**
* Проверяет, валидна ли цифра для позиции (row, col)
*/
private boolean isValid(int row, int col, int num) {
// Проверяем строку
if (!isValidInRow(row, num)) {
return false;
}
// Проверяем столбец
if (!isValidInCol(col, num)) {
return false;
}
// Проверяем блок 3x3
if (!isValidInBox(row, col, num)) {
return false;
}
return true;
}
/**
* Проверяет, нет ли числа в строке
*/
private boolean isValidInRow(int row, int num) {
for (int col = 0; col < SIZE; col++) {
if (board[row][col] == num) {
return false;
}
}
return true;
}
/**
* Проверяет, нет ли числа в столбце
*/
private boolean isValidInCol(int col, int num) {
for (int row = 0; row < SIZE; row++) {
if (board[row][col] == num) {
return false;
}
}
return true;
}
/**
* Проверяет, нет ли числа в блоке 3x3
*/
private boolean isValidInBox(int row, int col, int num) {
// Находим верхний левый угол блока 3x3
int boxRow = row - row % 3;
int boxCol = col - col % 3;
// Проверяем весь блок 3x3
for (int i = boxRow; i < boxRow + 3; i++) {
for (int j = boxCol; j < boxCol + 3; j++) {
if (board[i][j] == num) {
return false;
}
}
}
return true;
}
/**
* Выводит решённое судоку
*/
public void printBoard() {
for (int row = 0; row < SIZE; row++) {
if (row % 3 == 0) {
System.out.println("-----------+-------+-----------");
}
for (int col = 0; col < SIZE; col++) {
if (col % 3 == 0) {
System.out.print("| ");
}
System.out.print(board[row][col] + " ");
}
System.out.println("|");
}
System.out.println("-----------+-------+-----------");
}
}
Пример использования
public class Main {
public static void main(String[] args) {
// Пример судоку (0 = пустая ячейка)
int[][] 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}
};
SudokuSolver solver = new SudokuSolver(board);
System.out.println("Исходное судоку:");
solver.printBoard();
if (solver.solve()) {
System.out.println("\nРешённое судоку:");
solver.printBoard();
} else {
System.out.println("Решение не найдено!");
}
}
}
Анализ сложности
- Временная сложность: O(9^(nm)), где nm — количество пустых ячеек. В худшем случае может быть экспоненциальная, но с отсечением (pruning) обычно работает быстро
- Пространственная сложность: O(n*m) для рекурсивного стека вызовов
Оптимизация: метод наименьшего количества вариантов
Вместо перебора по всем ячейкам подряд, выбираем ячейку с наименьшим количеством возможных значений:
public class OptimizedSudokuSolver {
private int[][] board;
public boolean solve() {
// Находим ячейку с минимальным количеством возможных значений
Cell emptyCell = findEmptyCellWithMinOptions();
if (emptyCell == null) {
return true; // Все ячейки заполнены
}
int row = emptyCell.row;
int col = emptyCell.col;
for (int num : getPossibleValues(row, col)) {
board[row][col] = num;
if (solve()) {
return true;
}
board[row][col] = 0;
}
return false;
}
private Cell findEmptyCellWithMinOptions() {
Cell minCell = null;
int minOptions = 10;
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++) {
if (board[row][col] == 0) {
int options = getPossibleValues(row, col).size();
if (options < minOptions) {
minOptions = options;
minCell = new Cell(row, col);
}
// Если нет возможных значений, рано откатываемся
if (minOptions == 0) {
return minCell;
}
}
}
}
return minCell;
}
private Set<Integer> getPossibleValues(int row, int col) {
Set<Integer> possible = new HashSet<>();
for (int num = 1; num <= 9; num++) {
possible.add(num);
}
// Удаляем числа, уже присутствующие в строке, столбце и блоке
for (int i = 0; i < 9; i++) {
possible.remove(board[row][i]); // Строка
possible.remove(board[i][col]); // Столбец
}
int boxRow = row - row % 3;
int boxCol = col - col % 3;
for (int i = boxRow; i < boxRow + 3; i++) {
for (int j = boxCol; j < boxCol + 3; j++) {
possible.remove(board[i][j]);
}
}
return possible;
}
static class Cell {
int row, col;
Cell(int row, int col) {
this.row = row;
this.col = col;
}
}
}
Ключевые навыки, которые демонстрирует решение судоку
- Рекурсия — основной механизм решения
- Backtracking — откат при неудачном пути
- Логическое мышление — анализ ограничений
- Оптимизация — улучшение эффективности алгоритма
- Проверка ограничений — валидация данных
- Тестирование — проверка различных примеров судоку
Решение судоку показывает способность разработчика решать сложные задачи методично и аналитически, что высоко ценится в Java-разработке.