algorithm - para - sudoku con operaciones matematicas

Código de golf: Validar la cuadrícula de Sudoku

Question

Introducción

Una cuadrícula de Sudoku válida se llena con los números del 1 al 9, y ningún número aparece más de una vez en cada subbloque de 9, fila o columna. Lea este artículo para obtener más detalles si no está familiarizado con este rompecabezas popular.

Reto

El desafío es escribir el programa más corto que valida una cuadrícula de Sudoku que podría no estar completa.

La entrada será una cadena de 9 líneas de 9 caracteres cada una, que representa la cuadrícula. Una celda vacía estará representada por a . . Su salida debe ser Valid si la cuadrícula es válida; de lo contrario, no será válida.

Ejemplo

Entrada

123...789
...456...
456...123
789...456
...123...
564...897
...231...
897...564
...564...

Salida

Valid

Entrada

123456789
987654321
123456789
123456789
987654321
123456789
123456789
987654321
123456789

Salida

Invalid

Código de Reglas de Golf

Por favor, publique su código más corto en cualquier idioma que resuelva este problema. La entrada y la salida pueden manejarse mediante stdin y stdout o por otros archivos de su elección.

El ganador será la solución más corta (por byte count) en un lenguaje con una implementación existente antes de la publicación de esta pregunta. Entonces, si bien es libre de usar un lenguaje que acaba de crear para enviar una solución de 0 bytes, no contará, y probablemente obtendrá votos negativos.

Answer 1

C: 165 162 161 160 159

int v[1566],x,y=9,c,b;main(){while(y--)for(x=9;x--+1;)if((c
=getchar()*27)>1242)b|=v[x+c]++|v[y+9+c]++|v[x-x%3+y/3+18+c]
++;puts(b?"Invalid":"Valid");return 0;}

Las dos nuevas líneas no son necesarias. Un personaje salvado por josefx :-) ...

Answer 2

Lisp Común: 266 252

(princ(let((v(make-hash-table))(r "Valid"))(dotimes(y 9)(dotimes(x
10)(let((c(read-char)))(when(>(char-code c)46)(dolist(k(list x(+ 9
y)(+ 18(floor(/ y 3))(- x(mod x 3)))))(when(>(incf(gethash(+(* k
9)(char-code c)-49)v 0))1)(setf r "Invalid")))))))r))

Answer 3

ASL: 108

args1["/n"x2I3*x;{;{:=T(T''{:i~{^0}?})}}
{;{;{{,0:e}:;{0:^},u eq}}/`/=}:-C
dc C@;{:|}C&{"Valid"}{"Invalid"}?P

ASL es un lenguaje de script inspirado en Golfscript que hice.

Answer 4

Golfscript: 56

n%{zip''''+9/.{''.''-..&=}%$0=/}:|2*{3/}%|;**"InvV"3/="alid"

Answer 5

Haskell: 207 230 218 195 172

import List
t=take 3
h=[t,t.drop 3,drop 6]
v[]="V"
v _="Inv"
f s=v[1|v<-[s,transpose s,[g=<<f s|f<-h,g<-h]],g<-map(filter(/=''.''))v,g/=nub g]++"alid/n"
main=interact$f.lines

Answer 6

Perl, 153 caracteres

@B contiene los 81 elementos del tablero.

&E comprueba si un subconjunto de @B contiene dígitos duplicados

bucle principal valida cada columna, "bloque" y fila del rompecabezas

sub E{$V+="@B[@_]"=~/(/d).*/1/}
@B=map//S/g,<>;
for$d(@b=0..80){
E grep$d==$_%9,@b;
E grep$d==int(($_%9)/3)+3*int$_/27,@b;
E$d*9..$d*9+8}
print$V?Inv:V,alid,$/

Answer 7

Perl: 186

La entrada es desde stdin, salida a stdout, saltos de línea en la entrada opcional.

@y=map//S/g,<>;
sub c{(join'''',map$y[$_],@$h)=~/(/d).*/1/|c(@_)if$h=pop}
print((''V'',''Inv'')[c map{$x=$_;[$_*9..$_*9+8],[grep$_%9==$x,0..80],[map$_+3*$b[$x],@b=grep$_%9<3,0..20]}0..8],''alid'')

(Linebreaks añadido para "claridad".)

c() es una función que verifica la entrada en @y contra una lista de listas de números de posición pasados ​​como un argumento. Devuelve 0 si todas las listas de posiciones son válidas (no contienen ningún número más de una vez) y 1 de lo contrario, usando la recursión para verificar cada lista. La línea inferior construye esta lista de listas, la pasa a c() y usa el resultado para seleccionar el prefijo correcto para la salida.

Una cosa que me gusta es que esta solución aprovecha la "auto-similitud" en la lista de posiciones de "bloque" en @b (que se reconstruye redundantemente muchas veces para evitar tener @b=... en otra declaración): la posición superior izquierda del bloque i dentro de todo el rompecabezas se puede encontrar multiplicando el elemento i en @b por 3.

Más extendido:

# Grab input into an array of individual characters, discarding whitespace
@y = map //S/g, <>;

# Takes a list of position lists.
# Returns 0 if all position lists are valid, 1 otherwise.
sub c {
    # Pop the last list into $h, extract the characters at these positions with
    # map, and check the result for multiple occurences of
    # any digit using a regex.  Note | behaves like || here but is shorter ;)
    # If the match fails, try again with the remaining list of position lists.
    # Because Perl returns the last expression evaluated, if we are at the
    # end of the list, the pop will return undef, and this will be passed back
    # which is what we want as it evaluates to false.
    (join '''', map $y[$_], @$h) =~ /(/d).*/1/ | c(@_) if $h = pop
}

# Make a list of position lists with map and pass it to c().
print((''V'',''Inv'')[c map {
        $x=$_;                  # Save the outer "loop" variable
        [$_*9..$_*9+8],         # Columns
        [grep$_%9==$x,0..80],   # Rows
        [map$_+3*$b[$x],@b=grep$_%9<3,0..20]   # Blocks
    } 0..8],                    # Generates 1 column, row and block each time
''alid'')

Answer 8

Perl: 202

Estoy leyendo Modern Perl y tengo ganas de programar algo ... (por cierto, es un libro muy bueno :)

while(<>){$i++;$j=0;for$s(split//){$j++;$l{$i}{$s}++;$c{$j}{$s}++;
$q{(int(($i+2)/3)-1)*3+int(($j+2)/3)}{$s}++}}
$e=V;for$i(1..9){for(1..9){$e=Inv if$l{$i}{$_}>1or$c{$i}{$_}>1or$q{$i}{$_}>1}}
print $e.alid

El conteo está excluyendo nuevas líneas innecesarias. Esto puede requerir Perl 5.12.2.

Un poco más legible:

#use feature qw(say);
#use JSON;

#$json = JSON->new->allow_nonref;

while(<>)
{
    $i++;
    $j=0;
    for $s (split //)
    {
        $j++;
        $l{$i}{$s}++;
        $c{$j}{$s}++;
        $q{(int(($i+2)/3)-1)*3+int(($j+2)/3)}{$s}++;
    }
}

#say "lines: ", $json->pretty->encode( /%l );
#say "columns: ", $json->pretty->encode( /%c );
#say "squares: ", $json->pretty->encode( /%q );

$e = V;
for $i (1..9)
{
    for (1..9)
    {
        #say "checking {$i}{$_}: " . $l{$i}{$_} . " / " . $c{$i}{$_} . " / " . $q{$i}{$_};
        $e = Inv if $l{$i}{$_} > 1 or $c{$i}{$_} > 1 or $q{$i}{$_} > 1;
    }
}

print $e.alid;

Answer 9

Perl: 168 128

$_=join'''',<>;@a=/.../g;print+(/(/d)([^/n]{0,8}|(.{10})*.{9})/1/s
+map"@a[$_,$_+3,$_+6]"=~/(/d).*/1/,0..2,9..11,18..20)?Inv:V,alid

El primer regex busca duplicados que estén en la misma fila y columna; el segundo regex maneja duplicados en el "mismo cuadro".

Es posible una mejora adicional al reemplazar /n en la primera expresión regular con una nueva línea literal (1 char), o con> = Perl 5.12, reemplazando [^/n] con /N (3 char)

Anteriormente, solución de 168 caracteres: la entrada es desde stdin, la salida es hacia stderr porque hace las cosas muy fáciles. Los saltos de línea son opcionales y no cuentan.

$_=join'''',<>;$m=alid.$/;$n=Inv.$m;/(/d)(/N{0,8}|(.{10})*.{9})/1/s&&
die$n;@a=/.../g;for$i(0,8,17){for$j($i..$i+2){
$_=$a[$j].$a[$j+3].$a[$j+6];/(/d).*/1/&&die$n}}die"V$m"

Answer 10

Python: 140

v=[(k,c) for y in range(9) for x,c in enumerate(raw_input()) for k in x,y+9,(x/3,y/3) if c>''.'']
print["V","Inv"][len(v)>len(set(v))]+"alid"

Answer 11

Python: 159 158

v=[0]*244
for y in range(9):
 for x,c in enumerate(raw_input()):
  if c>".":
<T>for k in x,y+9,x-x%3+y//3+18:v[k*9+int(c)]+=1
print["Inv","V"][max(v)<2]+"alid"

<T> es un carácter de pestaña única

Answer 12

Python: 230 221 200 185

Primero la versión legible en len = 199:

import sys
r=range(9)
g=[raw_input()for _ in r]
s=[[]for _ in r*3]
for i in r:
 for j in r:
  n=g[i][j]
  for x in i,9+j,18+i/3*3+j/3:
<T>if n in s[x]:sys.exit(''Invalid'')
<T>if n>''.'':s[x]+=n
print''Valid''

Como SO no muestra los caracteres de tabulación, he usado <T> para representar un solo carácter de tabulación.

PD. El mismo enfoque minimizó hasta 185 caracteres:

r=range(9)
g=[raw_input()for _ in r]
s=['''']*27
for i in r:
 for j in r:
    for x in i,9+j,18+i/3*3+j/3:n=g[i][j];s[x]+=n[:n>''.'']
print[''V'',''Inv''][any(len(e)>len(set(e))for e in s)]+''alid''

Answer 13

Ruby - 176

f=->x{x.any?{|i|(i-[?.]).uniq!}}
a=[*$<].map{|i|i.scan /./}
puts f[a]||f[a.transpose]||f[a.each_slice(3).flat_map{|b|b.transpose.each_slice(3).map &:flatten}]?''Invalid'':''Valid''

Answer 14

Lua, 341 bytes

Aunque sé que Lua no es el mejor idioma para jugar al golf, sin embargo, considerando su tamaño, creo que vale la pena publicarlo;). Versión sin golf, comentada e imprimiendo errores, para mayor diversión :)

i=io.read("*a"):gsub("/n","")   -- Get input, and strip newlines
a={{},{},{}} -- checking array, 1=row, 2=columns, 3=squares
for k=1,3 do for l=1,9 do a[k][l]={0,0,0,0,0,0,0,0,0}end end -- fillup array with 0''s (just to have non-nils)

for k=1,81 do -- loop over all numbers
    n=tonumber(i:sub(k,k):match''%d'') -- get current character, check if it''s a digit, and convert to a number
    if n then
        r={math.floor((k-1)/9)+1,(k-1)%9+1} -- Get row and column number
        r[3]=math.floor((r[1]-1)/3)+3*math.floor((r[2]-1)/3)+1 -- Get square number
        for l=1,3 do v=a[l][r[l]] -- 1 = row, 2 = column, 3 = square
            if v[n] then -- not yet eliminated in this row/column/square
                v[n]=nil    
            else
                print("Double "..n.." in "..({"row","column","square"}) [l].." "..r[l]) --error reporting, just for the extra credit :)
                q=1 -- Flag indicating invalidity
            end
        end
    end
end
io.write(q and"In"or"","Valid/n")

Versión golfeada, 341 bytes.

f=math.floor p=io.write i=io.read("*a"):gsub("/n","")a={{},{},{}}for k=1,3 do for l=1,9 do a[k][l]={0,0,0,0,0,0,0,0,0}end end for k=1,81 do n=tonumber(i:sub(k,k):match''%d'')if n then r={f((k-1)/9)+1,(k-1)%9+1}r[3]=f((r[1]-1)/3)+1+3*f((r[2]-1)/3)for l=1,3 do v=a[l][r[l]]if v[n]then v[n]=nil else q=1 end end end end p(q and"In"or"","Valid/n")