Valid Sudoku

Q: Как определить, в каком блоке 3 × 3 находится ячейка?

При целочисленном делении r / 3 обозначает полосу строк (0, 1 или 2), а c / 3 — стопку столбцов. Выражение (r / 3) * 3 + c / 3 нумерует блоки от 0 до 8 слева направо и сверху вниз. Ячейка (7, 1) находится в блоке 2 * 3 + 0 = 6 , то есть в нижнем левом.

СреднеХеширование

+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 групп, поэтому ответ — true.

Ввод: 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 × 16 с блоками 4 × 4 и символами от 1 до 9 и от A до G. Какие числа в твоём коде зависят от размера поля и какой станет формула для блока?

Подсказки

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

Открыто 0 из 3

Решение

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

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

Идея

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

Строка i — это board[i][0..8], а столбец i — это board[0..8][i]. Блок i начинается со строки 3 * (i / 3) и столбца 3 * (i % 3), используя целочисленное деление, поэтому блок 5 начинается со строки 3, столбца 6. Его ячейка k находится на k / 3 строк ниже и на k % 3 столбцов правее этого угла.

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

Алгоритм

Для i от 0 до 8 соберите строку i, столбец i и блок i — по девять ячеек в каждом.
Блок i начинается с позиции top = 3 * (i / 3) и left = 3 * (i % 3); его ячейка k находится в строке top + k / 3, столбце left + k % 3.
Для каждой группы пройдите по её ячейкам, каждый раз используя новые флаги seen, пропуская точки.
Если цифра уже отмечена флагом, верните 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. Первая часть определяет полосу из трёх блоков (строки с 0 по 2 дают полосу 0, строки с 3 по 5 — полосу 1, строки с 6 по 8 — полосу 2), а c / 3 определяет блок внутри полосы. Ячейка (4, 7) попадает в блок 1 * 3 + 2 = 5, средний правый блок.

Для каждой заполненной ячейки, если хотя бы один из трёх её флагов уже установлен, цифра повторяется в этой группе, и ты сразу возвращаешь false. В противном случае установи все три флага. Каждая ячейка считывается один раз, а таблицы содержат 243 флага, поэтому время и объём памяти фиксированы для поля 9 × 9 и составляют 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] имеет значение true, верни false.
В противном случае установи все три значения в true. После последней ячейки верни 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 в них считаются повтором. Используй (r / 3) * 3 + c / 3.
Деление с помощью / в JavaScript, Python 3 или Lua, где 4 / 3 — это 1.33, а не номер блока. Используй Math.floor, // или math.floor.
Считать . значением. На пустой доске в каждой строке девять точек, и это допустимо.
Пытаться решить головоломку. Если в строке 0 стоит 12345678., а ниже в столбце 8 находится 9, последнюю ячейку строки 0 заполнить невозможно, но ни в одной группе цифры не повторяются, поэтому ответ — true.
Проверять строки и столбцы, но не блоки. В полной сетке, где каждая строка сдвинута влево на одну позицию относительно предыдущей, нет повторов ни в одной строке или столбце, но в каждом блоке есть повторы.

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

Какова временная сложность задачи «Valid Sudoku»?

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

Должно ли у правильного поля судоку быть решение?

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

Как определить, в каком блоке 3 × 3 находится ячейка?

При целочисленном делении r / 3 обозначает полосу строк (0, 1 или 2), а c / 3 — стопку столбцов. Выражение (r / 3) * 3 + c / 3 нумерует блоки от 0 до 8 слева направо и сверху вниз. Ячейка (7, 1) находится в блоке 2 * 3 + 0 = 6, то есть в нижнем левом.

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

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

Python

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