Recupere todas as marcas possíveis que podem ser colocadas em um quebra-cabeça Sudoku [fechado]

8

Dado um quebra-cabeça Sudoku, encontre todas as marcas possíveis que podem ser preenchidas em cada célula vazia.

Caso de teste

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
        ]
    ]
]

Resultado:

[
    [
        // 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]
        ]
    ]
]

Visualização de saída; os pequenos números:

Grade Sudoku incompleta com todas as marcas válidas

Regras

  • Este é um . A resposta mais curta em bytes (ou equivalente) vence.
  • A entrada pode estar no formato de matriz ou sequência.
  • A entrada deve estar na ordem apresentada acima (superior esquerdo, superior médio, superior direito, etc ...)
  • A saída pode estar no formato de matriz ou sequência, desde que a saída possa representar logicamente o resultado esperado.
  • A saída deve estar na mesma ordem que a entrada (superior esquerda, superior central, superior direita, etc ...)
  • A saída não precisa ser prettificada.
  • O código deve ser aplicável a qualquer grade Sudoku incompleta válida.
  • Aplicam-se regras de golfe padrão.

Notas Adicionais:

Você ganha pontos de internet falsos adicionais se o seu programa ou função usar o resultado para resolver o quebra-cabeça do Sudoku até o ponto em que os valores das células não possam mais ser resolvidos logicamente. Por exemplo, a primeira célula do caso de teste só pode conter o número 5, portanto deve ser considerada ao preencher os outros valores. Isso é apenas para diversão e desafio adicional; caso contrário, a resposta mais curta vence, independentemente de esse critério ser ou não atendido.

driima
fonte
Quão flexível é o formato de entrada? Poderia ser, por exemplo, uma matriz de 9 strings? (such as ["000340002", "740000003", ...])
Arnauld
1
É permitida uma entrada única da esquerda para a direita, de cima para baixo, como entrada? Como isso? E saída na mesma ordem?
orlp
1
Se não estamos aplicando lógica para descobrir quais células podem e não podem ser resolvidas, qual é a pergunta que realmente está nos pedindo para fazer?
Peter Taylor
1
Qual a distinção que você está fazendo entre isso e a solução do quebra-cabeça?
Peter Taylor
1
Então, em que circunstâncias um valor incorreto pode ser colocado em uma célula? Pare de se repetir e comece a definir seus termos.
Peter Taylor

Respostas:

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("");}}

Assume a entrada no seguinte formato (o mesmo sudoku que acima):

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

E saídas no seguinte formato:

5
1569
1569


1269

3569
23569


5689
etc
orlp
fonte
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]]

Uma função anônima que pega uma matriz tridimensional de entradas e retorna uma matriz tridimensional de entradas.

PurkkaKoodari
fonte
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 :
uma matriz de 9 strings (uma por caixa, do canto superior esquerdo para o canto inferior direito).

Saída :
Uma matriz de 9 matrizes, em que cada item consiste no número original nessa posição ou em uma matriz de caracteres representando os possíveis dígitos.

Formatado e 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)
)                                 //

Demo

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
fonte
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 uma função fde listas de 81 Ints para listas de listas de Ints;

IO é como a resposta do orlp , exceto que usa em [0,1,2,3,4,5,6,7,8,9]vez de ".123456789".

dianne salvou alguns bytes.

Lynn
fonte
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 uma matriz de três linhas de uma matriz de três colunas de uma matriz de três por três de células de números inteiros e retorna uma matriz tridimensional em que todos os números inteiros foram substituídos por matrizes.

Neil
fonte