Valid Sudoku

+10

Вам дана доска судоку 9 × 9 в виде board — списка из 9 строк по 9 символов в каждой, по одной строке на каждый ряд. Каждый символ — это цифра от 1 до 9 или ., обозначающая пустую ячейку. Верните true, если в одном ряду, столбце или блоке 3 × 3 ни одна цифра не встречается дважды, и false в противном случае. Проверяются только заполненные ячейки: доска не обязательно должна иметь решение.

Функция

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 строк по 9 символов, по одной в каждой строке: цифры от 1 до 9 и . для пустой ячейки
Возвращаетboolean: true, если ни в строке, ни в столбце, ни в квадрате 3 × 3 цифры не повторяются; в противном случае — false

Ограничения

board.length == 9 и board[i].length == 9
board[i][j] — это цифра от 1 до 9 или .
Возможно, доску нельзя заполнить; важны только повторы среди заполненных ячеек.

Примеры

Ввод: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Вывод: true
Пояснение: В строке 4, если считать с 0, .74..89.3, цифры 7, 4, 8, 9 и 3 встречаются по одному разу, и ни в одной из остальных 26 групп цифры тоже не повторяются.

Ввод: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Вывод: false
Пояснение: Строки 0 и 7 обе начинаются с 3, поэтому в столбце 0 находятся две тройки. Они не находятся ни в одной строке или квадрате вместе, поэтому это выявляет только проверка столбца.

Ввод: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Вывод: false
Пояснение: 5 в строке 0, столбце 8 и 5 в строке 2, столбце 7 не находятся в одной строке или столбце, но оба находятся в верхнем правом блоке, поэтому ответ — false.

Дополнительный вопрос

Как бы вы проверили доску 16 × 16 с блоками 4 × 4 и символами от 1 до 9 и от A до G? Какой будет формула для блока?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Каждая цифра принадлежит трём группам: своей строке, своему столбцу и своему квадрату 3 × 3. Строки и столбцы индексировать легко; ошибки кроются в квадрате. Пронумеруй квадраты от 0 до 8 с помощью (r / 3) * 3 + c / 3, и один проход по 81 ячейке проверит все 27 групп.

Проверьте каждую строку, каждый столбец и каждый блок по отдельности

Идея

Правило задаёт 27 групп: 9 строк, 9 столбцов и 9 блоков. Соберите девять ячеек каждой группы и найдите повторяющуюся цифру, игнорируя точки. Доска корректна, только если ни в одной группе такой цифры нет.

Флаг посещения для каждой цифры позволяет найти повтор среди девяти ячеек. Каждая из 81 ячейки считывается один раз для каждой из трёх групп: 243 считывания — фиксированный объём работы. На доске n × n тот же метод требует O(n²).

Алгоритм

Для i от 0 до 8 соберите строку i, столбец i и блок i.
У блока i угол находится в строке 3 * (i / 3), столбце 3 * (i % 3); его ячейка k расположена на k / 3 строк ниже и на k % 3 столбцов правее.
Обойдите каждую группу с новыми флагами посещения, пропуская точки. Если цифра уже отмечена, верните false.
После всех 27 групп верните true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Один проход с таблицей уже встреченных значений для каждой строки, столбца и блока

Идея

Посети каждую клетку один раз и задай все три вопроса одновременно. Веди три таблицы флагов размером 9 × 9: seenRow[r][d] показывает, что цифра d+1 уже встречалась в строке r, а seenCol и seenBox работают так же.

Клетка (r, c) принадлежит блоку (r / 3) * 3 + c / 3. Первая часть выбирает полосу из трёх блоков, а c / 3 выбирает блок внутри полосы. Клетка (4, 7) попадает в блок 1 * 3 + 2 = 5, средний правый блок.

Установленный флаг означает, что цифра повторяется в этой группе. Каждая клетка считывается один раз, а таблицы содержат 243 флага: здесь время и память фиксированы, O(n²) на доске размером n × n.

Алгоритм

Создай seenRow, seenCol и seenBox, каждый размером 9 × 9 и заполненный значениями false.
Для каждой заполненной ячейки (r, c) пусть d будет её цифрой минус 1, а b = (r / 3) * 3 + c / 3.
Если установлено значение seenRow[r][d], seenCol[c][d] или seenBox[b][d], верни false; в противном случае установи все три значения.
После последней ячейки верни true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Ловушки и крайние случаи

Вычисление номера блока как r / 3 + c / 3. Получаются только числа от 0 до 4, поэтому (0, 3) и (3, 0) получают одинаковый номер, хотя находятся в разных блоках, а две цифры 7 в них считаются повтором.
Деление с помощью / в JavaScript, Python 3 или Lua, где 4 / 3 равно 1.33. Округляй вниз.
Считать . значением. Пустая доска, по девять точек в каждом ряду, считается допустимой.
Пытаться решить головоломку. Ряд 0 со значением 12345678. и цифрой 9 ниже в столбце 8 невозможно заполнить до конца, но повторов нет: true.
Пропускать блоки. В полной сетке, где каждый ряд — это предыдущий ряд, сдвинутый влево на одну позицию, нет повторов ни в строках, ни в столбцах, но в каждом блоке есть повторы.

Частые вопросы3

Какова временная сложность алгоритма проверки корректности судоку?

На доске всегда 81 ячейка, поэтому оба подхода работают за время O(1) и используют O(1) памяти. Для обобщённого судоку размером n × n проверка за один проход считывает каждую из n² ячеек один раз и хранит 3n² флагов: время и память O(n²).

Должна ли корректная доска судоку иметь решение?

Нет. Здесь «допустимая» означает только, что среди заполненных клеток ни одна цифра не повторяется в строке, столбце или квадрате 3 × 3. Доска может пройти эту проверку, но при этом не иметь решения. Чтобы определить, существует ли решение, нужен поиск, например с возвратом, а это уже другая задача.

Можно ли решить задачу Valid Sudoku с помощью битовых масок?

Да. Задай каждой строке, каждому столбцу и каждому блоку по одному целому числу, где бит d означает, что цифра d+1 уже встречалась. Для заполненной ячейки, если 1 << d при выполнении побитового AND с любой из трёх масок даёт ненулевой результат, цифра повторяется; в противном случае выполни побитовое OR с этим значением для всех трёх масок. Это 27 целых чисел вместо 243 флагов.

def isValidSudoku(board):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Ожидаемый вывод

true