36. Valid Sudoku. Проверить Судоку на корректность.

Задача. Определить, является ли корректным заполнение доски Судоку размером 9×9. Проверять нужно только заполненные клетки по следующим правилам: Каждая строка должна содержать цифры от 1 до 9 без повторений. Каждый столбец должен содержать цифры от 1 до 9 без повторений. Каждый из девяти блоков размером 3×3 должен содержать цифры от 1 до 9 без повторений. Ссылка на leetcode: https://leetcode.com/problems/valid-sudoku Решение. Пример: Очевидно, что придётся пройти по каждой клетке хотя бы один раз. При обходе каждой клетки следует проверить следующие условия: 1) Если клетка пуста, переходим к следующей. 2) Если клетка заполнена, проверяем, что в ней записано число от 1 до 9. В противном случае доска Судоку считается некорректной. 3) Если в этой строке такое число уже встречалось — доска некорректна. 4) Если в этом столбце такое число уже встречалось — доска некорректна. 5) Если в соответствующем 3×3 блоке такое число уже встречалось — доска некорректна. Первые два условия тривиальны. Для остальных трёх нам потребуются дополнительные структуры данных, позволяющие отслеживать, какие числа уже встречались в каждой строке, столбце и блоке. Таким образом, нам нужно три дополнительных хранилища. В качестве такого хранилища можно использовать массив булевых значений: если число уже встречалось, соответствующий элемент устанавливается в true, в противном случае — в false. Далее нам потребуется по 9 элементов для каждой строки, каждого столбца и каждого блока. Итого 9 × 9 + 9 × 9 + 9 × 9 = 81 × 3 = 243 ячейки для хранения статуса. Например, для хранения чисел, которые мы уже видели в строках мы можем объявить массив: boolean rows[][] = new boolean[9][9]; Тогда, если мы видели число 7 в строке 5, нам нужно выставить в true, значение в: rows[4][6] = true Наглядно, для нашего примера это выглядит так: Строки у нас проиндексированы от 0 до 8. Числа в них: на позиции 0 число 1, на позиции 1 число 2 и т.д. Для нашего примера, после обхода всей доски Судоку, значения в rows будут: Например, в первой строке у нас выставлены в true значения для 3,5,7. Аналогично, для столбцов: В первом столбце (с индексом 0), у нас выставлены в true значения для 4,5,6,7,8. Реализация Пишем базовый обход всей доски Судоку: public boolean isValidSudoku(char[][] board) { for (int i = 0; i

May 7, 2025 - 01:36

36. Valid Sudoku. Проверить Судоку на корректность.

Задача.

Определить, является ли корректным заполнение доски Судоку размером 9×9. Проверять нужно только заполненные клетки по следующим правилам:

Каждая строка должна содержать цифры от 1 до 9 без повторений.
Каждый столбец должен содержать цифры от 1 до 9 без повторений.
Каждый из девяти блоков размером 3×3 должен содержать цифры от 1 до 9 без повторений.

Ссылка на leetcode: https://leetcode.com/problems/valid-sudoku

Решение.

Пример:

Очевидно, что придётся пройти по каждой клетке хотя бы один раз. При обходе каждой клетки следует проверить следующие условия:

1) Если клетка пуста, переходим к следующей.

2) Если клетка заполнена, проверяем, что в ней записано число от 1 до 9. В противном случае доска Судоку считается некорректной.

3) Если в этой строке такое число уже встречалось — доска некорректна.

4) Если в этом столбце такое число уже встречалось — доска некорректна.

5) Если в соответствующем 3×3 блоке такое число уже встречалось — доска некорректна.

Первые два условия тривиальны. Для остальных трёх нам потребуются дополнительные структуры данных, позволяющие отслеживать, какие числа уже встречались в каждой строке, столбце и блоке. Таким образом, нам нужно три дополнительных хранилища.

В качестве такого хранилища можно использовать массив булевых значений: если число уже встречалось, соответствующий элемент устанавливается в true, в противном случае — в false.
Далее нам потребуется по 9 элементов для каждой строки, каждого столбца и каждого блока. Итого 9 × 9 + 9 × 9 + 9 × 9 = 81 × 3 = 243 ячейки для хранения статуса.

Например, для хранения чисел, которые мы уже видели в строках мы можем объявить массив:

boolean rows[][] = new boolean[9][9];

Тогда, если мы видели число 7 в строке 5, нам нужно выставить в true, значение в:

rows[4][6] = true

Наглядно, для нашего примера это выглядит так:

Строки у нас проиндексированы от 0 до 8. Числа в них: на позиции 0 число 1, на позиции 1 число 2 и т.д.

Для нашего примера, после обхода всей доски Судоку, значения в rows будут:

Например, в первой строке у нас выставлены в true значения для 3,5,7.

Аналогично, для столбцов:

В первом столбце (с индексом 0), у нас выставлены в true значения для 4,5,6,7,8.

Реализация

Пишем базовый обход всей доски Судоку:

public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
        }
    }
    return true;
}

Добавляем тривиальные проверки. Если поле пустое, то переходим к следующей клетке, если не лежит в диапазоне от 1 до 9, то доска не валидна:

public boolean isValidSudoku(char[][] board) {
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
        }
    }
    return true;
}

Добавляем проверки на то, что мы уже видели или нет такое число в текущей строке и текущем столбце:

public boolean isValidSudoku(char[][] board) {
    boolean rows[][] = new boolean[9][9];
    boolean cols[][] = new boolean[9][9];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }

            int index = board[i][j] - '0' - 1;
            //уже видели такое число в текущей строке
            if (rows[i][index]) {
                return false;
            }
            rows[i][index] = true;

            //уже видели такое число в текущем столбце
            if (cols[j][index]) {
                return false;
            }
            cols[j][index] = true;

        }
    }
    return true;
}

И наконец, проверку на то, что уже видели в такое число в текущем блоке:

public boolean isValidSudoku(char[][] board) {
    boolean rows[][] = new boolean[9][9];
    boolean cols[][] = new boolean[9][9];
    boolean squares[][][] = new boolean[3][3][9];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
            int index = board[i][j] - '0' - 1;
            if (rows[i][index]) {
                return false;
            }
            rows[i][index] = true;
            if (cols[j][index]) {
                return false;
            }
            cols[j][index] = true;

            if (squares[i/3][j/3][index]) {
                return false;
            }
            squares[i/3][j/3][index] = true;
        }
    }
    return true;
}

Time Complexity = O(N*M), где N - число строк, M - число столбцов, т.к. мы обходим всю доску один раз.

Space Complexity = O(N * M) для хранения статуса видели ли мы или еще нет число в строке, столбце и блоке.

Оптимизация по памяти

Оптимизировать объём памяти не получится — нам всё равно придётся обойти всю доску. Зато можно снизить потребление памяти: поскольку в каждой строке, столбце или блоке всего девять допустимых чисел, вместо массива булевых значений достаточно использовать одно целое число и выставлять в нём биты на соответствующих позициях. Это типичный приём для ограниченного набора возможных значений, аналогичный метод часто применяется для работы с буквами алфавита.

Например, для первой строки в нашем случаем массив boolean можно заменить на одно число типа int:

true заменим на 1, false на 0 на соотвествующей позиции.

Чтобы выставить в числе бит на позиции x в 1 можно выполнить следующую битовую операцию:

value = value | (1 << x);
или
value |= (1 << x);

Чтобы проверить, выставлен ли бит на позиции x в 1, можно выполнить следующую проверку:

if ((value & (1 << x)) > 0) {
  ....
}

Зная это, можно сократить размерность наших массивов:

public boolean isValidSudoku(char[][] board) {
    int rows[] = new int[9];
    int cols[] = new int[9];
    int squares[][] = new int[3][3];
    for (int i = 0; i < board.length; i++) {
        for (int j = 0; j < board[i].length; j++) {
            if (board[i][j] == '.') {
                continue;
            }
            if (board[i][j] < '1' || board[i][j] > '9') {
                return false;
            }
            int index = board[i][j] - '0' - 1;
            int value = 1 << index;
            if ((rows[i] & value) > 0) {
                return false;
            }
            rows[i] |= value;
            if ((cols[j] & value) > 0) {
                return false;
            }
            cols[j] |= value;

            if ((squares[i/3][j/3] & value) > 0) {
                return false;
            }
            squares[i/3][j/3] |= value;
        }
    }
    return true;
}