Crie uma solução Sudoku CHECKER
Existem muitos SOLVERS do Sudoku aqui, mas quero que você crie uma solução CHECKER tão pequena quanto humanamente possível (código-golfe).
Uma entrada válida poderá aceitar uma matriz 9x9 como argumento (passado por referência, serializado na linha de comando ou como você desejar) ou aceitar um arquivo de entrada com nove linhas de nove números para a grade final . Veja exemplos de entrada abaixo.
A entrada válida deve ter números de base 10 (1-9)
As posições ausentes, vazias, extras, não numéricas ou com números fora de 1 a 9 devem ser rejeitadas como entrada inválida retornando um resultado diferente de zero, imprimindo um erro ou ambos.
Seu programa precisa testar se cada número aparece uma vez por coluna, uma vez por linha e uma vez por sub-grade 3x3. Se for aprovado, retorne "0" e, se não, retorne um resultado diferente de zero.
O uso de recursos externos (sites, etc.) deve ser evitado.
Se a sua solução for um programa independente, sair com um status de saída de ou imprimir "0" ou diferente de zero para "Aprovado" ou "Reprovado", respectivamente, está ok.
Deixe a menor resposta vencer!
Exemplos de entrada:
matriz c:
int input[9][9]={{1,2,3,4,5,6,7,8,9},
{4,5,6,7,8,9,1,2,3},
{7,8,9,1,2,3,4,5,6},
{2,3,1,5,6,4,8,9,7},
{5,6,4,8,9,7,2,3,1},
{8,9,7,2,3,1,5,6,4},
{3,1,2,6,4,5,9,7,8},
{6,4,5,9,7,8,3,1,2},
{9,7,8,3,1,2,6,4,5}
};
Arquivo:
123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645
As 9 subgrelhas:
+---+---+---+
|123|456|789|
|456|789|123|
|789|123|456|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+
fonte
1
ou-1
Python, 103
Eu odeio sudoku.
Como funciona: cada linha, coluna e bloco deve ter cada número de 1 a 9. Portanto, para cada
0 <= i, j < 9
célula, a célulai,j
está em bloco3*floor(i/3) + floor(j/3)
. Portanto, existem 243 requisitos a serem satisfeitos. Faço de cada requisito uma tupla,((item index,item type number),symbol)
ondeitem index
é um número entre 0 e 8 (inclusive),item type number
é 0,1 ou 2 para indicar linha, coluna ou bloco, respectivamente, esymbol
é a entradab[i][j]
.Editar: por engano, não verifiquei entradas válidas. Agora eu faço.
fonte
0
se a solução passa, nãoTrue
APL (46)
Isso requer uma matriz 9 por 9. O exemplo pode ser inserido no TryAPL da seguinte forma:
Explicação:
↓⍉⍵
: obtenha as colunas de⍵
,↓⍵
: obtém as linhas de⍵
,3/3⌿3 3⍴Z←⍳9
: crie uma matriz 3 por 3 contendo os números1
para9
, em seguida, triplique cada número nas duas direções, fornecendo uma matriz 9 por 9 com os números1
para9
indicar cada grupo,Z∘.=
: Para cada número1
para9
, fazer uma máscara de bits para o grupo determinado,/∘(,⍵)¨
: e mascarar⍵
com cada um, dando os grupos de⍵
.∊∘Z¨
: para cada subconjunto, veja se ele contém os números1
para9
,∧/,↑
: pegue a lógicaand
de todos esses números juntos.fonte
↓9 9⍴1 3 2⍉3 3 9⍴⍵
é equivalente,/∘(,⍵)¨↓Z∘.=,3/3⌿3 3⍴Z←⍳9
mas bem mais curto. Tenho certeza de que existem fórmulas ainda mais curtas.⍪
e executar uma única divisão no final:↓(9 9⍴1 3 2⍉3 3 9⍴⍵)⍪⍵⍪⍉⍵
∊∘Z¨
está testando se cada sub-matriz (linha, coluna ou bloco) é composta apenas dos números 1 a 9. Não está testando se todos os números estão representados. Você precisa fazer algo como oZ∘.∊
teste de que todo número em Z está contido em cada sub-matriz.∧/,↑
pode ser reduzido para∧/∊
. Acabei, acabei! ;-)If it passes, return "0" and if not, return a non-zero result.
Java / C # -
183/180181/178173/170 bytes(Altere
boolean
parabool
para C #)Formatado:
O método cria uma matriz
u
com 27 máscaras de bits, representando os dígitos encontrados nas nove linhas, colunas e quadrados.Em seguida, itera sobre todas as células, executando a operação
1 << a[x][y]
para criar uma máscara de bits representando o dígito e ORs sua coluna, linha e máscara de bits quadrada com ele.Ele itera sobre todas as 27 máscaras de bits, garantindo que todas elas adicionem até 27594 (1022 * 9, 1022 sendo a máscara de bit para todos os dígitos de 1 a 9 presentes). (Observe que
y
acaba como 27603, pois já contém 9 após o loop duplo.)Editar: acidentalmente deixado em um
%3
que não é mais necessário.Edit 2: Inspirado pelo comentário de Bryce Wagner, o código foi compactado um pouco mais.
fonte
python = 196
Não é o mais jogado, mas a idéia está aí. Conjuntos são bastante úteis.
Borda:
Programa:
fonte
n={*range(1,10)}
, mas isso é mais recente que o desafio. Em vez disso, useset(range(1,10))
como MatrixFrog disse.Java -
385306328260 caracteresEdit: Eu tolamente enganei as instruções de que a resposta tinha que ser um programa completo. Como ela pode ser apenas uma função válida, reescrevi e minimizei para ser uma função e reescrevi minha introdução à solução com isso em mente.
Então, como um desafio para mim, pensei em tentar fazer o menor verificador de solução Java.
Para conseguir isso, assumo que o quebra-cabeça do sudoku será transmitido como uma matriz multidimensional java, da seguinte forma:
Então, temos o solucionador real, que retorna "0" se solução válida, "1" se não.
Totalmente jogado:
Legível:
Então, como isso funciona? Basicamente, apenas crio minha própria base numérica com resolução suficiente em cada dígito, para que eu só precise fazer três comparações numéricas depois de passar pelo quebra-cabeça uma vez para saber se é válido. Eu escolhi a base 49 para esse problema, mas qualquer base maior que 45 seria suficiente.
Um exemplo (espero) claro: imagine que toda "linha" no quebra-cabeça sudoku seja um único dígito no número da base 49. Representaremos cada dígito no número da base 49 como um número da base 10 em um vetor para simplificar. Portanto, se todas as linhas estiverem "corretas", esperamos o seguinte número da base 49 (como um vetor da base 10):
ou convertido em um único número base-10:
1526637748041045
Siga uma lógica semelhante para todas as colunas e o mesmo para as "sub-grades". Qualquer valor encontrado na análise final que não seja igual a esse "número ideal" significa que a solução do quebra-cabeça é inválida.
Edite para solucionar a vulnerabilidade do all-5s e outros problemas relacionados: adiciono um quarto número da base 49, com base na idéia de que deve haver 9 de cada número em cada quebra-cabeça. Portanto, adiciono 5 a cada dígito no número da base 49 para cada ocorrência do número da base 10 que representa o índice do dígito. Por exemplo, se houver 10 9 e 9 8, 9 7, 8 6 e 9 de todos os outros, você obteria um número base 49 (como um vetor base 10 do tamanho 10 para lidar com o estouro):
O que falhará quando comparado com o número "ideal" da base 49.
Minha solução tira proveito dessa solução matemática, para evitar o máximo possível de loop e comparação. Simplesmente uso um
long
valor para armazenar cada número da base 49 como um número base 10 e uso uma matriz de pesquisa para obter os "fatores" para cada dígito da base 49 durante o cálculo do valor da verificação de coluna / linha / sub-grade.Como o Java não foi projetado para ser conciso, ter cuidado na construção matemática era a única maneira que eu imaginava que poderia construir um verificador conciso.
Diz-me o que pensas.
fonte
R 145
O código retirado do golfe (mais ou menos) pode ser encontrado aqui /programming//a/21691541/1201032 .
fonte
Haskell (Lambdabot), 65 bytes
fonte
Perl, 193 bytes
A entrada é esperada no formato de matriz:
O código de saída é 0, se
@a
for uma solução, caso contrário,1
será retornado.Versão não destruída:
Cada uma das 9 linhas, 9 colunas e 9 sub-matrizes é colocada em uma matriz classificada e verificada, se corresponde à matriz
(1..9)
. O número$r
é incrementado para cada correspondência bem-sucedida que deve somar 27 para uma solução válida.fonte
J
5254Leva seu argumento colado na linha de comando, terminado com a) como:
Retorna 1 se aprovado, 0 se não.
Internamente, ele converte a grade 9x9 em uma grade 3x3x3x3 e faz algumas permutações nos eixos para obter a unidade desejada (linhas, linhas e caixas) nas duas últimas dimensões.
Depois disso, é verificado que cada unidade possui 9 valores exclusivos.
Provavelmente longe de ser perfeito, mas já supera a maioria ;-)
fonte
Mathematica,
8479 caracteresExemplos:
fonte
3
sempre indicativo de entrada inválida ou, às vezes, é uma resposta a uma solução com falha?Javascript ES6, 150 caracteres
Recebe a entrada como uma sequência de 81 caracteres sem delimitadores.
A função retorna
null
como resposta negativa e uma matriz com a sequência original no primeiro elemento como positiva. Pode mudar para bool, adicionando!!
a função de início.Teste (veja o desafio relacionado para mais detalhes):
fonte
R,
6350 bytesAssume que a entrada
m
é uma matriz de números 9x9.Eu estava certo que mais golfe era possível.
Explicação:
Pegue
m
e, para cada linha, aplique amatch
função Especificamos outro argumentox=1:9
a ser passadomatch
.x
é o argumento de primeira posição padrão e, portanto, cada linha é colocada na segunda posição de argumento, que étable
. A funçãomatch
procura instâncias dex
intable
. Nesse caso, ele está procurando1:9
(os números de 1 a 9) em cada linha. Para cada um deles1:9
, ele retornaráTRUE
(ouFALSE
) se esse número for encontrado (ou não).Portanto, isso gera uma série de 81 valores booleanos.
Repita o procedimento acima para cada coluna da entrada.
Finalmente,
all
verifica se todos os elementos da lista de booleanos sãoTRUE
. Este será o caso se e somente se a solução estiver correta (ou seja, cada número1:9
está presente apenas uma vez em cada coluna e cada linha).Abordagem antiga:Ele pega cada linha, classifica-a e depois a compara[1, 2, ... 9]
. Uma linha correta deve corresponder exatamente. Em seguida, faz o mesmo para cada coluna. No total, devemos ter 162 correspondências exatas, que é o que a parte final verifica. Provavelmente existe alguma margem para mais golfe aqui ...fonte
Haskell - 175
A função
v
é a única a chamar. Ele funciona obtendo a diferença de cada linha, coluna e bloco na lista[1..9]
e resumindo os comprimentos dessas listas de diferenças.Demonstração usando o exemplo Sudoku:
fonte
Javascript - 149 caracteres
Espera que uma matriz
a
exista e cria uma variávelo
para saída0
com êxito e diferente de zero.Funciona verificando se a soma da posição em que cada valor ocorre para cada linha, coluna e grade 3 * 3 é igual a 36 (0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8).
Teste
Dá 'o = 0'
(Últimos 2 dígitos trocados)
Dá
o=-1
Dá
o=-284
fonte
Haskell,
121130127 bytes (87 Lambdabot)usa:
O Lambdabot carrega Data.List e Data.List.Split por padrão (não acho que a solução do BlackCap marque as caixas).
Idéias para melhoria bem-vindas
// Edit: eu errei :)
// Edit: 3 bytes salvos pelo BlackCap
fonte
(map sort)
por(sort<$>)
.c$(sort<$>)<$>
com$(sort<$>)=<<
05AB1E , 36 bytes | NoN-Competing |
Experimente online!
1 é verdade, qualquer outra coisa é falsa.
fonte
Clojure, 151 bytes
Muito tempo, mas outros parecem também. Também é irritante que a união de conjuntos exija a
require
, então usei uma concat de vetores.Repete cada linha e coluna e, se o valor estiver entre 1 e 9, emite três vetores, um para a linha, a coluna e a célula 3x3. Retorna 0 em caso de sucesso e
nil
, caso contrário, com dois caracteres extras, pode retornar 1 em caso de falha. Manipula números fora de 1 a 9 retornando,nil
mas trava em outras anomalias, como valores não inteiros. Os quocientes são de 0 a 2, portanto, é seguro usar valores8
e9
diferenciar valores de células de linhas e colunas.Input é um vetor aninhado de vetores (para que
nth
funcione):Ungolfed:
fonte
PHP,
196190 bytesO programa recebe 9 argumentos de linha de comando separados (uma sequência de dígitos para cada linha da grade);
sai com
1
(erro) inválido,0
(ok) válido.Corra com
php -nr '<code>' <row1> <row2> ...
.demolir
explicação
count_chars
conta caracteres em uma string e geralmente cria uma matriz com códigos ASCII como chaves e caracteres como valores; mas com o3
parâmetro mode, ele cria uma sequência classificada a partir dos caracteres; e isso pode ser facilmente comparado ao número com os dígitos desejados.A comparação não apenas verifica duplicatas, mas também inclui a verificação de caracteres inválidos. E isso requer apenas
<
, não!=
, porque esta é uma comparação numérica: o PHP interpretará a string como um número, na medida do possível.123e56789
,0x3456789
Ou similar não pode aparecer, porque os personagens são classificadas; e qualquer número inteiro puro com um dígito ausente é menor que123456789
... e.23456789
também, é claro.$a=$argv
salva um byte,$d=123456789
salva nove e$u=count_chars
salva 13.fonte
C # -
306298288 caracteresO seguinte programa Console foi usado para chamar a função de verificação;
Tudo isso é inicializar o array e passá-lo para a função de verificação P.
A função de verificação é a seguinte (na forma Golfed);
Ou de forma totalmente definida;
Isso usa a ideia de que todas as colunas, linhas e subgrades devem adicionar até 45. Ele funciona através da matriz de entrada e subtrai o valor de cada posição da sua linha, coluna e sub-grade. Depois de concluído, verifica se nenhuma das linhas, colunas ou subgrades ainda possui um valor.
Conforme solicitado, retorna 0 se a matriz for uma solução Sudoku válida e diferente de zero (1) onde não estiver.
fonte
private static int P(int[,]i){int[]r=new int[9],c=new int[9],g=new int[9];
. (Observe a remoção do espaço após o colchete fechado]
.) Além disso, não tenho certeza, mas acho que você pode se livrar doprivate static
.for(int p=0;p<9;p++)if(r[p]>0|c[p]>0|g[p]>0)return 1;return 0;}
, ou seja , não sabemos se funciona em C #. (Eu realmente não sei C #) #