Valid Sudoku

+10

Você recebe um tabuleiro de Sudoku 9 × 9 como board, uma lista de 9 strings com 9 caracteres cada, uma string por linha. Cada caractere é um dígito de 1 a 9 ou . para uma célula vazia. Retorne true se nenhum dígito aparecer duas vezes em uma linha, coluna ou caixa 3 × 3, e false caso contrário. Apenas as células preenchidas são verificadas: o tabuleiro não precisa ter solução.

Função

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 sequências de 9 caracteres, uma por linha, dígitos de 1 a 9 e . para uma célula vazia
Retornaboolean: true se nenhuma linha, coluna ou caixa 3 × 3 repetir um dígito, false caso contrário

Restrições

board.length == 9 e board[i].length == 9
board[i][j] é um dígito de 1 a 9 ou .
O tabuleiro pode ser impossível de completar; apenas as repetições entre as células preenchidas importam.

Exemplos

Entrada: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Saída: true
Explicação: A linha 4, contando a partir de 0, .74..89.3, tem 7, 4, 8, 9 e 3 uma vez cada, e nenhum dos outros 26 grupos repete um dígito.

Entrada: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Saída: false
Explicação: A linha 0 e a linha 7 começam com um 3, então a coluna 0 contém dois 3s. Elas não compartilham nenhuma linha nem caixa, então somente a verificação da coluna detecta isso.

Entrada: 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"]
Saída: false
Explicação: O 5 na linha 0, coluna 8 e o 5 na linha 2, coluna 7 não compartilham nenhuma linha ou coluna, mas ambos estão no bloco superior direito, então a resposta é false.

Para ir além

Como você verificaria um tabuleiro 16 × 16 com caixas 4 × 4 e os símbolos de 1 a 9 e de A a G? Em que se transforma a fórmula das caixas?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Cada dígito pertence a três grupos: sua linha, sua coluna e seu bloco 3 × 3. É fácil indexar linhas e colunas; é no bloco que os bugs aparecem. Numere os blocos de 0 a 8 com (r / 3) * 3 + c / 3, e uma passagem pelas 81 células verifica todos os 27 grupos.

Verifique cada linha, coluna e bloco separadamente

Intuição

A regra define 27 grupos: 9 linhas, 9 colunas e 9 blocos. Reúna as nove células de cada grupo e procure um dígito repetido, ignorando os pontos. O tabuleiro é válido exatamente quando nenhum grupo tem um.

Uma flag de presença por dígito detecta uma repetição entre nove células. Cada uma das 81 células é lida uma vez para cada um de seus três grupos: 243 leituras, uma quantidade fixa de trabalho. Em um tabuleiro n × n, o mesmo método custa O(n²).

Algoritmo

Para i de 0 a 8, colete a linha i, a coluna i e o bloco i.
O bloco i tem seu canto na linha 3 * (i / 3), coluna 3 * (i % 3); sua célula k fica k / 3 linhas abaixo e k % 3 colunas à direita dele.
Percorra cada grupo com sinalizadores de valores vistos novos, ignorando os pontos. Se um dígito já estiver sinalizado, retorne false.
Depois dos 27 grupos, retorne 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

Uma passada com uma tabela de elementos vistos para cada linha, coluna e caixa

Intuição

Visite cada célula uma vez e faça as três perguntas juntas. Mantenha três tabelas de sinalizadores de 9 × 9: seenRow[r][d] indica que o dígito d+1 já está na linha r, e seenCol e seenBox funcionam da mesma maneira.

A célula (r, c) pertence à caixa (r / 3) * 3 + c / 3. A primeira parte escolhe a faixa de três caixas, e c / 3 escolhe a caixa dentro da faixa. A célula (4, 7) fica na caixa 1 * 3 + 2 = 5, a caixa do meio à direita.

Um sinalizador já definido significa que o dígito se repete nesse grupo. Cada célula é lida uma vez e as tabelas armazenam 243 sinalizadores: tempo e memória constantes aqui, O(n²) em um tabuleiro n × n.

Algoritmo

Crie seenRow, seenCol e seenBox, cada um com 9 × 9 e todos definidos como false.
Para cada célula preenchida (r, c), considere d como seu dígito menos 1 e b = (r / 3) * 3 + c / 3.
Se seenRow[r][d], seenCol[c][d] ou seenBox[b][d] estiver definido, retorne false; caso contrário, defina os três.
Após a última célula, retorne 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

Armadilhas e casos extremos

Calcular o bloco como r / 3 + c / 3. Isso gera apenas valores de 0 a 4, então (0, 3) e (3, 0) compartilham um número, embora estejam em blocos diferentes, e dois 7s nessas posições são relatados como uma repetição.
Dividir usando / em JavaScript, Python 3 ou Lua, onde 4 / 3 é 1.33. Arredonde para baixo.
Tratar . como um valor. Um tabuleiro vazio, com nove pontos em cada linha, é válido.
Tentar resolver o quebra-cabeça. Uma linha 0 com 12345678. e um 9 mais abaixo na coluna 8 nunca pode ser completada, mas nada se repete: true.
Ignorar os blocos. Uma grade completa em que cada linha é a linha acima deslocada uma posição para a esquerda não tem repetições em nenhuma linha ou coluna, enquanto cada bloco contém repetições.

Perguntas frequentes3

Qual é a complexidade de tempo do Sudoku Válido?

O tabuleiro sempre tem 81 células, então ambas as abordagens são executadas em tempo O(1) e usam memória O(1). Para um Sudoku genérico de n × n, a verificação em uma única passagem lê cada uma das n² células uma vez e mantém 3n² sinalizadores: tempo e memória O(n²).

Um tabuleiro de Sudoku válido precisa ter solução?

Não. Válido aqui significa apenas que nenhum dígito se repete em uma linha, coluna ou bloco 3 × 3 entre as células preenchidas. Um tabuleiro pode passar nessa verificação e ainda assim não ter solução. Determinar se há solução exige uma busca, como o retrocesso, o que é um problema diferente.

É possível resolver o Sudoku válido com máscaras de bits?

Sim. Dê a cada linha, coluna e bloco um inteiro, em que o bit d significa que o dígito d+1 foi visto. Para uma célula preenchida, se 1 << d resultar em um valor diferente de zero ao fazer AND com qualquer uma das três máscaras, o dígito se repete; caso contrário, faça OR dele nas três. São 27 inteiros em vez de 243 sinalizadores.

def isValidSudoku(board):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

true