Ответ
Классический алгоритм для решения Судоку — поиск с возвратом (Backtracking). Он перебирает возможные варианты чисел для пустых клеток и откатывается при обнаружении противоречия.
Принцип работы:
- Найти первую пустую клетку (обозначенную как 0).
- Попробовать подставить в нее числа от 1 до 9.
- Для каждого числа проверить, допустимо ли оно по правилам Судоку (отсутствие в строке, столбце и блоке 3x3).
- Если число допустимо, поместить его в клетку и рекурсивно вызвать алгоритм для решения оставшейся части сетки.
- Если рекурсивный вызов вернул
true— решение найдено. - Если ни одно число не подошло — откатиться (backtrack): обнулить клетку и вернуть
false, чтобы предыдущий вызов попробовал другое число.
Реализация на Java:
public class SudokuSolver {
private static final int SIZE = 9;
private static final int EMPTY = 0;
public boolean solve(int[][] board) {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
if (board[row][col] == EMPTY) {
for (int num = 1; num <= SIZE; num++) {
if (isValidPlacement(board, row, col, num)) {
board[row][col] = num; // Пробуем число
if (solve(board)) { // Рекурсивно решаем дальше
return true; // Решение найдено!
}
board[row][col] = EMPTY; // Откат (backtrack)
}
}
return false; // Нет допустимых чисел для этой клетки
}
}
}
return true; // Все клетки заполнены
}
private boolean isValidPlacement(int[][] board, int row, int col, int num) {
// Проверка строки и столбца
for (int i = 0; i < SIZE; i++) {
if (board[row][i] == num || board[i][col] == num) {
return false;
}
}
// Проверка блока 3x3
int blockRowStart = 3 * (row / 3);
int blockColStart = 3 * (col / 3);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[blockRowStart + i][blockColStart + j] == num) {
return false;
}
}
}
return true;
}
}Сложность: В худшем случае O(9^(N)), где N — количество пустых клеток, но на практике откаты сокращают перебор, и алгоритм решает стандартные головоломки почти мгновенно.
Ответ 18+ 🔞
А, Судоку, блядь! Ну это ж классика, как "Муму", только с цифрами. Сейчас расскажу, как эта штука работает, чтобы ты не ломал голову, как Герасим над мешком.
Смотри, есть у нас эта ебаная сетка 9 на 9, и некоторые клетки пустые, как мозги у того, кто её не может решить. Алгоритм, который всех спасает, называется поиск с возвратом (Backtracking). Представь себе упоротого перфекциониста, который пытается впихнуть цифры, а потом, когда всё идёт по пизде, орет "АЙ ВСЁ НАХУЙ!" и начинает заново, но уже умнее.
Как этот конченый перфекционист работает:
- Ищет первую попавшуюся пустую клетку. Глазами водит туда-сюда, как маньяк.
- Начинает тыкать в неё цифры от 1 до 9, по очереди, как кнопки в лифте.
- Перед тем как впихнуть цифру, проверяет: а не будет ли конфликта? То есть, чтобы этой же цифры не было уже в строке, в столбце и в этом самом маленьком квадратике 3x3, где она сидит. Если есть — сразу "НЕ-А, НАХУЙ", пробует следующую.
- Если цифра вписалась без скандала, он её туда суёт и говорит: "ОКЕЙ, А ТЕПЕРЬ, СУКА, РЕШАЙ ВСЮ ОСТАВШУЮСЯ ХУЙНЮ САМ!" — то есть запускает себя же рекурсивно на оставшейся доске. Ебать, самогипноз.
- Если этот вложенный "он" вернулся и сказал "ДА, БЛЯ, ВСЁ РЕШИЛ!" — значит, путь верный, можно праздновать.
- А вот если он перебрал все цифры от 1 до 9, и каждая, блядь, вела в тупик — наступает момент истины. ОТКАТ. Он берёт и обнуляет эту клетку обратно, со словами "СОРЯН, ПРЕДЫДУЩИЙ ЧУВАК, ТЫ НАХУЙ НЕПРАВ". Возвращает
false, и тот, кто его вызывал (более ранняя версия его же), понимает: "Ага, значит ту цифру, что я поставил перед этим, надо менять". И пробует следующую. Во какие ебушки-воробушки!
Вот он, весь этот цирк, на Java:
public class SudokuSolver {
private static final int SIZE = 9;
private static final int EMPTY = 0;
public boolean solve(int[][] board) {
for (int row = 0; row < SIZE; row++) {
for (int col = 0; col < SIZE; col++) {
if (board[row][col] == EMPTY) {
for (int num = 1; num <= SIZE; num++) {
if (isValidPlacement(board, row, col, num)) {
board[row][col] = num; // Пробуем число
if (solve(board)) { // Рекурсивно решаем дальше
return true; // Решение найдено!
}
board[row][col] = EMPTY; // Откат (backtrack)
}
}
return false; // Нет допустимых чисел для этой клетки
}
}
}
return true; // Все клетки заполнены
}
private boolean isValidPlacement(int[][] board, int row, int col, int num) {
// Проверка строки и столбца
for (int i = 0; i < SIZE; i++) {
if (board[row][i] == num || board[i][col] == num) {
return false;
}
}
// Проверка блока 3x3
int blockRowStart = 3 * (row / 3);
int blockColStart = 3 * (col / 3);
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[blockRowStart + i][blockColStart + j] == num) {
return false;
}
}
}
return true;
}
}Сложность, говорят, в теории — O(9^(N)), где N пустых клеток. Это пиздец как много, типа перебрать все вселенные. Но на практике-то, из-за этих постоянных проверок и откатов, для обычной газетной судокушке он щёлкает её за миллисекунды. Чистая магия, ёпта. В рот меня чих-пых, а работает!