Задача: 37. Sudoku Solver
Сложность: hard

Напишите программу для решения головоломки Судоку, заполнив пустые ячейки.

Решение должно удовлетворять следующим условиям:

- В каждой строке числа 1-9 встречаются ровно один раз.
- В каждом столбце числа 1-9 встречаются ровно один раз.
- В каждом 3x3 блоке числа 1-9 встречаются ровно один раз.
- Символ '.' обозначает пустые ячейки.

Пример:

Input: board =  
[["5","3",".",".","7",".",".",".","."]  
,["6",".",".","1","9","5",".",".","."]  
,[".","9","8",".",".",".",".","6","."]  
,["8",".",".",".","6",".",".",".","3"]  
,["4",".",".","8",".","3",".",".","1"]  
,["7",".",".",".","2",".",".",".","6"]  
,[".","6",".",".",".",".","2","8","."]  
,[".",".",".","4","1","9",".",".","5"]  
,[".",".",".",".","8",".",".","7","9"]]  

Output:  
[["5","3","4","6","7","8","9","1","2"]  
,["6","7","2","1","9","5","3","4","8"]  
,["1","9","8","3","4","2","5","6","7"]  
,["8","5","9","7","6","1","4","2","3"]  
,["4","2","6","8","5","3","7","9","1"]  
,["7","1","3","9","2","4","8","5","6"]  
,["9","6","1","5","3","7","2","8","4"]  
,["2","8","7","4","1","9","6","3","5"]  
,["3","4","5","2","8","6","1","7","9"]]  

👨‍💻 Алгоритм:

1⃣Реализуйте обратный поиск: найдите первую пустую ячейку и попробуйте вставить числа от 1 до 9.

2⃣Проверять достоверность вставок: не нарушать правила чисел, строки, столбцы и блоки.

3⃣Если число достоверно — вставьте и перейдите к следующей ячейке, иначе откатиться (назад) и еще раз попробовать.

😎 Решение:

public class Solution {
    private const int N = 9;
    private char[][] board;
    private bool[,] rows = new bool[N, N + 1];
    private bool[,] cols = new bool[N, N + 1];
    private bool[,] boxes = new bool[N, N + 1];

    public void SolveSudoku(char[][] inputBoard) {
        board = inputBoard;
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (board[r][c] != '.') {
                    int num = board[r][c] - '0';
                    PlaceNumber(num, r, c, true);
                }
            }
        }
        Backtrack(0, 0);
    }

    private bool Backtrack(int row, int col) {
        if (col == N) { col = 0; row++; }
        if (row == N) return true;

        if (board[row][col] != '.') return Backtrack(row, col + 1);

        for (int num = 1; num <= 9; num++) {
            if (CouldPlace(num, row, col)) {
                PlaceNumber(num, row, col, true);
                if (Backtrack(row, col + 1)) return true;
                PlaceNumber(num, row, col, false);
            }
        }

        return false;
    }

    private bool CouldPlace(int num, int row, int col) {
        int boxIndex = (row / 3) * 3 + col / 3;
        return !rows[row, num] && !cols[col, num] && !boxes[boxIndex, num];
    }

    private void PlaceNumber(int num, int row, int col, bool place) {
        board[row][col] = place ? (char)(num + '0') : '.';
        rows[row, num] = place;
        cols[col, num] = place;
        boxes[(row / 3) * 3 + col / 3, num] = place;
    }
}

Ставь 👍 и забирай 📚 Базу знаний