Valid Sudoku

Q: Como descobrir em qual bloco 3 × 3 uma célula está?

Com a divisão inteira, r / 3 é a faixa de linhas (0, 1 ou 2) e c / 3 é a pilha de colunas. (r / 3) * 3 + c / 3 numera as caixas de 0 a 8, da esquerda para a direita e de cima para baixo. A célula (7, 1) está na caixa 2 * 3 + 0 = 6 , a do canto inferior esquerdo.

MédioHashing

+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 na mesma linha, na mesma coluna ou no mesmo bloco 3 × 3, e false caso contrário. Apenas as células preenchidas são verificadas: o tabuleiro não precisa ser solucionável.

Função

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 strings de 9 caracteres, uma por linha, com dígitos de 1 a 9 e . para uma célula vazia
Retornaboolean: verdadeiro se nenhuma linha, coluna ou caixa 3 × 3 repetir um dígito; falso 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: Cada linha, coluna e caixa contém cada dígito no máximo uma vez. A linha 4 (contando a partir de 0), .74..89.3, tem 7, 4, 8, 9 e 3 uma vez cada, e o mesmo vale para os outros 26 grupos, então a resposta é true.

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. As duas células estão em linhas diferentes e em caixas diferentes; somente a verificação da coluna detecta esse caso.

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 estão em linhas e colunas diferentes, mas ambos estão no bloco superior direito, então a resposta é false.

+16 testes ocultos ao enviar

Para ir além

Generalize a verificação para um tabuleiro 16 × 16 com caixas 4 × 4 e os símbolos de 1 a 9 e de A a G. Quais números no seu código dependem do tamanho do tabuleiro, e em que se transforma a fórmula da caixa?

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 ao mesmo tempo: sua linha, sua coluna e seu bloco 3 × 3. É fácil indexar linhas e colunas; o bloco é onde ocorre a maioria dos bugs. Numere os blocos de 0 a 8 com (r / 3) * 3 + c / 3, e uma única passagem pelas 81 células pode verificar os 27 grupos de uma só vez.

Verifique cada linha, coluna e caixa individualmente

Intuição

As regras definem 27 grupos: 9 linhas, 9 colunas e 9 blocos. Reúna as nove células de cada grupo e verifique se algum dígito se repete entre elas, ignorando os pontos. Se nenhum grupo tiver repetições, o tabuleiro é válido.

A linha i é board[i][0..8] e a coluna i é board[0..8][i]. O bloco i começa na linha 3 * (i / 3) e na coluna 3 * (i % 3), usando divisão inteira; portanto, o bloco 5 começa na linha 3, coluna 6. Sua célula k fica k / 3 linhas abaixo e k % 3 colunas à direita desse canto.

Para encontrar uma repetição entre nove células, mantenha uma sinalização de visitado para cada dígito e pare no primeiro dígito que já estiver sinalizado. Cada uma das 81 células é lida três vezes, uma vez para cada grupo ao qual pertence: 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, reúna a linha i, a coluna i e a caixa i, com nove células cada.
A caixa i começa em top = 3 * (i / 3) e left = 3 * (i % 3); sua célula k está na linha top + k / 3, coluna left + k % 3.
Para cada grupo, percorra suas células com indicadores de vistos recém-inicializados, ignorando os pontos.
Se um dígito já estiver marcado, retorne false.
Após os 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 passagem com uma tabela de elementos vistos para cada linha, coluna e bloco

Intuição

Em vez de reunir grupos, percorra cada célula uma vez e faça as três perguntas ao mesmo tempo. 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 forma para colunas e caixas.

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

Para cada célula preenchida, se algum de seus três sinalizadores já estiver definido, o dígito se repete nesse grupo e você retorna false imediatamente. Caso contrário, defina os três. Cada célula é lida uma vez e as tabelas armazenam 243 sinalizadores, então o tempo e a memória são fixos para um tabuleiro de 9 × 9, e O(n²) para um de n × n.

Algoritmo

Crie seenRow, seenCol e seenBox, cada um com 9 × 9 e todos false.
Visite cada célula (r, c); pule-a se contiver um ponto.
Considere d como o dígito menos 1 e b = (r / 3) * 3 + c / 3.
Se seenRow[r][d], seenCol[c][d] ou seenBox[b][d] for true, retorne false.
Caso contrário, defina os três como true. 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

As verificações de linha e coluna raramente dão errado. Os bugs estão no índice do bloco e no que conta como uma repetição.

Calcular o bloco como r / 3 + c / 3. Isso resulta apenas em valores de 0 a 4, então as células (0, 3) e (3, 0) compartilham um número, embora estejam em blocos diferentes, e dois 7s nelas são relatados como uma repetição. Use (r / 3) * 3 + c / 3.
Dividir com / em JavaScript, Python 3 ou Lua, onde 4 / 3 é 1.33, não um número de bloco. Use Math.floor, // ou math.floor.
Tratar . como um valor. Um tabuleiro vazio tem nove pontos em cada linha, e é válido.
Tentar resolver o quebra-cabeça. Com 12345678. como linha 0 e um 9 mais abaixo na coluna 8, a última célula da linha 0 nunca poderá ser preenchida; ainda assim, nenhum grupo repete um dígito, então a resposta é true.
Verificar linhas e colunas, mas não os blocos. Uma grade completa em que cada linha é a anterior 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 frequentes4

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 O(1) tempo e usam O(1) de memória. Para um Sudoku geral de n × n, a verificação em uma única passagem lê cada uma das n² células uma vez e mantém 3n² sinalizadores, portanto tem complexidade O(n²) em tempo e memória.

Um tabuleiro de Sudoku válido precisa ser solucionável?

Não. Válido aqui significa apenas que nenhum dígito se repete em uma linha, uma coluna ou um bloco 3 × 3 entre as células já 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.

Como descobrir em qual bloco 3 × 3 uma célula está?

Com a divisão inteira, r / 3 é a faixa de linhas (0, 1 ou 2) e c / 3 é a pilha de colunas. (r / 3) * 3 + c / 3 numera as caixas de 0 a 8, da esquerda para a direita e de cima para baixo. A célula (7, 1) está na caixa 2 * 3 + 0 = 6, a do canto inferior esquerdo.

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

Sim. Atribua um inteiro a cada linha, coluna e bloco, e deixe o bit d indicar que o dígito d+1 foi visto. Para uma célula preenchida, calcule 1 << d; se o resultado da operação AND com qualquer uma das três máscaras for diferente de zero, o dígito se repete; caso contrário, faça OR com ele nas três máscaras. São 27 inteiros em vez de 243 sinalizadores, com a mesma lógica de passagem única.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

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

Esperado

true