Recupera todas las marcas posibles que se pueden colocar en un rompecabezas de Sudoku [cerrado]

8

Dado un rompecabezas de Sudoku, encuentra todas las marcas posibles que se pueden llenar en cada celda vacía.

Caso de prueba

Entrada:

[
    [
        // Top left:
        [
            0, 0, 0,
            3, 4, 0,
            0, 0, 2
        ],
        // Top middle:
        [
            7, 4, 0,
            0, 0, 0,
            0, 0, 3
        ],
        // Top right:
        [
            8, 0, 0,
            1, 7, 0,
            0, 0, 0
        ]
    ],
    [
        // Middle left:
        [
            9, 0, 4,
            7, 0, 0,
            1, 0, 3
        ],
        // Center:
        [
            0, 5, 0,
            0, 0, 0,
            0, 7, 0
        ],
        // Middle right:
        [
            0, 0, 0,
            6, 4, 0,
            0, 0, 0
        ]
    ],
    [
        // Bottom left:
        [
            0, 0, 7,
            6, 3, 0,
            0, 0, 0
        ],
        // Bottom middle:
        [
            0, 0, 5,
            0, 0, 0,
            9, 1, 0
        ],
        // Bottom right:
        [
            0, 0, 0,
            5, 2, 0,
            7, 0, 0
        ]
    ]
]

Salida:

[
    [
        // Top left:
        [
            [5], [1, 5, 6, 9], [1, 5, 6, 9],
            [], [], [5, 6, 8, 9],
            [5, 8], [1, 5, 6, 7, 8, 9], []
        ],
        // Top middle:
        [
            [], [], [1, 2, 6, 9],
            [2, 5, 6, 8], [2, 6, 8, 9], [2, 6, 8, 9],
            [1, 5, 6, 8], [6, 8, 9], []
        ],
        // Top right:
        [
            [], [3, 5, 6, 9], [2, 3, 5, 6, 9],
            [], [], [2, 5, 6, 9],
            [4, 9], [5, 6, 9], [4, 5, 6, 9]
        ]
    ],
    [
        // Middle left:
        [
            [], [2, 6, 8], [],
            [], [2, 5, 8], [5, 8],
            [], [2, 5, 6, 8], []
        ],
        // Center:
        [
            [1, 2, 3, 6, 8], [], [1, 2, 6, 8],
            [1, 2, 3, 8], [2, 3, 8, 9], [1, 2, 8, 9],
            [2, 4, 6, 8], [], [2, 4, 6, 8, 9]
        ],
        // Middle right:
        [
            [2, 3], [1, 3, 8], [1, 2, 3, 7, 8],
            [], [], [1, 2, 3, 5, 8, 9],
            [2, 9], [5, 8, 9], [2, 5, 8, 9]
        ]
    ],
    [
        // Bottom left:
        [
            [2, 4, 8], [1, 2, 8, 9], [],
            [], [], [1, 8, 9],
            [2, 4, 5, 8], [2, 5, 8], [5, 8]
        ],
        // Bottom middle:
        [
            [2, 3, 4, 6, 8], [2, 3, 6, 8], [],
            [4, 8], [8], [4, 7, 8],
            [], [], [2, 4, 6, 8]
        ],
        // Bottom right:
        [
            [3, 4, 9], [1, 3, 6, 8, 9], [1, 3, 4, 6, 8, 9],
            [], [], [1, 4, 8, 9],
            [], [3, 6, 8], [3, 4, 6, 8]
        ]
    ]
]

Visualización de salida; los pequeños números:

Cuadrícula de Sudoku incompleta con todas las marcas válidas

Reglas

  • Este es un . La respuesta más corta en bytes (o equivalente) gana.
  • La entrada puede estar en formato de matriz o cadena.
  • La entrada debe estar en el orden presentado arriba (arriba a la izquierda, arriba a la mitad, arriba a la derecha, etc.)
  • La salida puede estar en formato de matriz o cadena, siempre que la salida pueda representar lógicamente el resultado esperado.
  • La salida debe estar en el mismo orden que la entrada (arriba a la izquierda, arriba a la mitad, arriba a la derecha, etc.)
  • La salida no necesita ser prettified.
  • El código debe ser aplicable a cualquier cuadrícula Sudoku incompleta válida.
  • Se aplican las reglas estándar de golf.

Notas adicionales:

Obtiene puntos de Internet falsos adicionales si su programa o función utiliza el resultado para resolver el rompecabezas de Sudoku hasta el punto en que los valores de las celdas ya no se puedan resolver lógicamente. Por ejemplo, la primera celda en el caso de prueba solo puede contener el número 5, por lo que debe tenerse en cuenta al completar los otros valores. Esto es solo por diversión y un desafío adicional, de lo contrario, la respuesta más corta gana independientemente de si se cumple o no este criterio.

driima
fuente
¿Qué tan flexible es el formato de entrada? ¿Podría ser, por ejemplo, una matriz de 9 cadenas? (como ["000340002", "740000003", ...])
Arnauld
1
¿Se permite una sola cadena que va de izquierda a derecha, de arriba a abajo como entrada? ¿Me gusta esto? ¿Y salida en el mismo orden?
orlp
1
Si no estamos aplicando la lógica para determinar qué células pueden y no pueden resolverse, ¿cuál es la pregunta que realmente nos pide que hagamos?
Peter Taylor el
1
¿Cuál es la distinción que estás haciendo entre eso y resolver el rompecabezas?
Peter Taylor el
1
Entonces, ¿en qué circunstancias se puede colocar un valor incorrecto en una celda? Deja de repetirte y comienza a definir tus términos.
Peter Taylor

Respuestas:

4

C (gcc), 193 bytes

#define F(x)for(x=0;x<9;++x)
char s[99];main(k,r,c){gets(s);F(r)F(c){
int d[99]={};F(k)d[s[r*9+k]]=d[s[k*9+c]]=d[s[r/3*27+k/3*9+c/3*3+k%3]]=1;
F(k)s[r*9+c]<48&&!d[49+k]&&putchar(49+k);puts("");}}

Asume la entrada en el siguiente formato (el mismo sudoku que el anterior):

..74.8..34....17...2..3...9.4.5....7.....64.1.3.7......7..5...63....52....91.7..

Y salidas en el siguiente formato:

5
1569
1569


1269

3569
23569


5689
etc
orlp
fuente
2

Python 2, 178 bytes

lambda s,R=range(9):[[[(s[Y][X][i]<1)*[q+1for q in R if~-(q+1in sum([[s[j/3][X][j%3*3+i%3],s[Y][j/3][j%3+i/3*3]]for j in R],[])+s[Y][X])]for i in R]for X in R[:3]]for Y in R[:3]]

Una función anónima que toma una matriz tridimensional de entradas y devuelve una matriz tridimensional de entradas.

PurkkaKoodari
fuente
2

JavaScript (ES6), 208 196 190 188 186 bytes

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))

Entrada :
una matriz de 9 cadenas (una por caja, de arriba a la izquierda a abajo a la derecha).

Salida :
una matriz de 9 matrices, donde cada elemento consta del número original en esta posición o una matriz de caracteres que representan los posibles dígitos.

Formateado y comentado

g => g.map((B, i) =>              // for each box B at position i in the grid:
  [...B].map((s, x) =>            // for each cell s at position x in this box:
    +s ||                         // if there already is a number at this position, use it
    [..."123456789"].filter(n =>  // else, for each digit n in [1 .. 9]:
      (t = i =>                   // t() = helper function that looks for the digit n inside
        (k = g[i].search(n) % m)  // a given box i and returns a truthy value if its
        < a | k > b               // position modulo m is not in the range [a .. b]
      )(                          //
        j = i % 3,                // test the top box in the current column, using:
        m = 3,                    // modulo = 3 and
        a = b = x % 3             // range = [x % 3 .. x % 3]
      ) &                         //
      t(j + 3) &                  // test the middle box in the current column
      t(j + 6) &                  // test the bottom box in the current column
      t(                          //
        j = i - j,                // test the left box in the current row, using:
        m = 9,                    // modulo = 9 and
        a = x - a, b = a + 2      // range = [floor(x / 3) .. floor(x / 3) + 2]
      ) &                         //
      t(j + 1) &                  // test the middle box in the current row
      t(j + 2) &                  // test the right box in the current row
      t(i, a = 0, b = 8)          // finally test the current box, using:
    )                             // modulo = 9 (unchanged) and
  )                               // range = [0 .. 8] (thus testing the entire box)
)                                 //

Manifestación

let f =

g=>g.map((B,i)=>[...B].map((s,x)=>+s||[..."123456789"].filter(n=>(t=i=>(k=g[i].search(n)%m)<a|k>b)(j=i%3,m=3,a=b=x%3)&t(j+3)&t(j+6)&t(j=i-j,m=9,a=x-a,b=a+2)&t(j+1)&t(j+2)&t(i,a=0,b=8))))

console.log(f([
  "000340002",
  "740000003",
  "800170000",
  "904700103",
  "050000070",
  "000640000",
  "007630000",
  "005000910",
  "000520700"
]));

Arnauld
fuente
1

Haskell, 135 bytes

(%)=mod
x!y=x-x%y
f a=[[j|j<-[1..9],and[a!!k/=j|k<-[i!3-i!9%27+p%3+p!3*3|p<-[0..8]]++[i!9..i!9+8]++[i%9,i%9+9..80]],a!!i<1]|i<-[0..80]]

Define una función fde listas de 81 Ints a listas de listas de Ints;

IO es como la respuesta de orlp , excepto que usa en [0,1,2,3,4,5,6,7,8,9]lugar de ".123456789".

dianne guardó un par de bytes.

Lynn
fuente
1

JavaScript (ES6), 185 bytes

a=>a.map((b,r)=>b.map((d,c)=>d.map((e,i)=>e.map((g,j)=>[1,2,3,4,5,6,7,8,9].filter(v=>a.every(b=>b[c].every(e=>e[j]-v))&b.every(d=>d[i].every(g=>g-v))&d.every(e=>e.every(g=>g-v))&!g)))))

Toma como entrada una matriz de tres filas de una matriz de tres columnas de una matriz de tres por tres de celdas de enteros, y devuelve una matriz de cinco dimensiones donde todos los enteros han sido reemplazados por matrices.

Neil
fuente