Introducción

Escriba un solucionador para los acertijos de Hitori utilizando menos bytes.

Reto

Tu tarea es escribir un solucionador para los rompecabezas lógicos Hitori (ひ と り, la palabra para "solo" en japonés; el significado del nombre del juego es "Déjame en paz"). Las reglas son las siguientes:

• Se le presenta una cuadrícula de celdas n por n, cada celda contiene un número entero entre 1 yn (inclusive).
• Su objetivo es asegurarse de que ningún número aparezca más de una vez en cada fila y cada columna de la cuadrícula, eliminando los números de la cuadrícula dada, sujeto a la restricción indicada en las siguientes dos reglas,
• No puede eliminar dos números de dos celdas adyacentes (horizontal o verticalmente).
• Las celdas numeradas restantes deben estar conectadas entre sí. Significa que dos celdas numeradas restantes se pueden conectar con una curva que se compone únicamente de segmentos que conectan números restantes adyacentes (horizontal o verticalmente). (Gracias a @ user202729 por señalar que falta esto)

Espero que las reglas estén claras por ahora. Si no hay algo claro sobre las reglas, consulte la página de Wikipedia .

Casos de prueba

Las celdas de las que se eliminan los números se representan con 0.

Input  ->  Output

4
2 2 2 4      0 2 0 4
1 4 2 3  ->  1 4 2 3
2 3 2 1      2 3 0 1
3 4 1 2      3 0 1 2

4
4 2 4 3      0 2 4 3
4 1 1 2  ->  4 1 0 2
3 1 2 1      3 0 2 1
4 3 1 3      0 3 1 0

5
1 5 3 1 2      1 5 3 0 2
5 4 1 3 4      5 0 1 3 4
3 4 3 1 5  ->  3 4 0 1 5
4 4 2 3 3      4 0 2 0 3
2 1 5 4 4      2 1 5 4 0

8
4 8 1 6 3 2 5 7      0 8 0 6 3 2 0 7
3 6 7 2 1 6 5 4      3 6 7 2 1 0 5 4
2 3 4 8 2 8 6 1      0 3 4 0 2 8 6 1
4 1 6 5 7 7 3 5  ->  4 1 0 5 7 0 3 0
7 2 3 1 8 5 1 2      7 0 3 0 8 5 1 2
3 5 6 7 3 1 8 4      0 5 6 7 0 1 8 0
6 4 2 3 5 4 7 8      6 0 2 3 5 4 7 8
8 7 1 4 2 3 5 6      8 7 1 4 0 3 0 6

9
8 6 5 6 8 1 2 2 9      8 0 5 6 0 1 2 0 9
5 6 2 4 1 7 9 8 3      5 6 2 4 1 7 9 8 3
5 8 2 5 9 9 8 2 6      0 8 0 5 0 9 0 2 0
9 5 6 6 4 3 8 4 1      9 5 6 0 4 3 8 0 1
1 1 6 3 9 9 5 6 2  ->  0 1 0 3 9 0 5 6 2
1 1 4 7 3 8 3 8 6      1 0 4 7 0 8 3 0 6
3 7 4 1 2 6 4 5 5      3 7 0 1 2 6 4 5 0
3 3 1 9 8 7 7 4 5      0 3 1 9 8 0 7 4 5
2 9 7 5 3 5 9 1 3      2 9 7 0 3 5 0 1 0 

Estos casos de prueba están tomados de Concept Is Puzzles , PuzzleBooks , Concept Is Puzzles , Wikipedia y Youtube , respectivamente.

Especificaciones

• No necesita preocuparse por el manejo de excepciones.

• Usted puede asumir que la entrada es siempre un rompecabezas válida con una única solución y se puede tomar ventaja de esto en la escritura de su código.

• Este es el código de golf , gana el menor número de bytes.

• 4 <= n <= 9 (16 originalmente, cambiado a 9 siguiendo la sugerencia de Stewie Griffin, también ahorra algunos problemas en IO)

• Puede tomar datos y proporcionar resultados a través de cualquier formulario estándar , y puede elegir el formato.

• Algunas sugerencias para el formato de salida son (pero no está restringido a estas)

  • Salida de la grilla final
  • Salida de la cuadrícula que contiene todos los números eliminados
  • Salida de una lista de coordenadas de uno de los anteriores

• Como de costumbre, las lagunas predeterminadas se aplican aquí.

_{Relacionado (inspirado en este desafío): compruebe si todos los elementos de una matriz están conectados}

_{Mi último desafío: extensión del juego de los sietes}

Haskell , 374 bytes

import Data.Array;import Data.List;r=range;p=partition
c(e,f)=p(\(b,p)->any(==1)[(b-d)^2+(p-q)^2|(d,q)<-e])f
n#g=[s|(o,(e:f))<-[p((==0).(g!))$indices g],
 null.fst$c(o,o),null.snd$until(null.fst)c([e],f),
 s<-case[((l,c),d)|((l,c),h)<-assocs g,h>0,
 d<-[filter((==h).(g!))$r((l,c+1),(l,n))++r((l+1,c),(n,c))],d/=[]]
 of[]->[g];((c,d):_)->n#(g//[(c,0)])++n#(g//[(c,0)|c<-d])]

Pruébalo en línea!

APL (Dyalog Unicode) , 133 bytes ^SBCS

{q←{⊢/4 2⍴⍵}⌺3 3⋄g←⍵=⊂∪,⍵⋄⍵×~1⊃{((⌈/q b)⌈b<{2<≢∪0,,(⍵×⊢⌈⌈/∘q)⍣≡⍵×(⍴⍵)⍴1+⍳≢,⍵}¨~b∘⌈¨⊂⍤2∘.≡⍨⍳⍴b)(+/↑w<g×⌈.⌈⍨w×g)⌈w b←⍵}⍣≡×\(⌈/=∘⌽⍨q⍵)0}

Pruébalo en línea!

Mi implementación de la regla n. ° 4 (las celdas deben formar un único componente conectado) es un desperdicio, pero aún así, pasa todas las pruebas en aproximadamente 10 segundos en TIO.

El algoritmo general: Almacene dos matrices booleanas by wpara celdas que seguramente serán en blanco y negro, respectivamente. Inicializar bcomo todo cero. Inicialice wcomo 1 solo para aquellas celdas que tienen vecinos coincidentes opuestos.

Repita hasta by wcalme:

• agregar a bceldas que están en la misma línea (horizontal o vertical) y del mismo valor que una celda enw

• agregar a wlos vecinos inmediatos de todas las celdas enb

• agregar a wtodos los puntos de corte: celdas cuya eliminación dividiría el gráfico de celdas no negras en múltiples componentes conectados

Finalmente, salida not(b)multiplicada por la matriz original.

Jalea , 62 bytes

Utiliza el enlace monádico isConnected de user202729 de otra pregunta.

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3
ḟ0ĠḊ€
¬T€œ&2\;Ç€FȦ
ZÇȯÇ_1Ŀ
2ḶṗLṗLa⁸ÇÞḢ

Un programa completo que imprime una representación de una lista de listas.
Funciona por fuerza bruta y es estúpidamente ineficiente.

Pruébalo en línea! - un 3 por 3, ya que es demasiado ineficiente ejecutar incluso un tamaño 4 dentro del límite TIO de 60 segundos.

¿Cómo?

FJṁa@µ«Ḋoµ€ZUµ4¡ÐLFQL<3 - Link 1 isConnected? List of lists
...                     - 1 if connected 0 if not -- see linked answer in the header

ḟ0ĠḊ€ - Link 2, helperFor-AnyRepeatedValues: list
ḟ0    - filter out zeros
  Ġ   - group indices by value (i.e. [[indices of min],...,[indices of max]]
   Ḋ€ - dequeue €ach -- leaving a list of empty lists iff no repeated values
      -                 any remaining values are non-zero (1-based indexing in Jelly)

¬T€œ&2\;Ç€FȦ - Link 3, columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues: list of lists
¬            - logical not (convert all zeros to ones and all others to zeros)
 T€          - for €ach row get a list of truthy indexes (i.e. indexes of original zeros)
     2\      - pairwise reduction (i.e. for neighbouring rows) with:
   œ&        -   intersection (empty if no columnwise adjacent original zeros
             -                 any remaining values are non-zero due to 1-based indexing)
        Ç€   - call last link (1) as a monad for €ach row
       ;     - concatenate
          F  - flatten into a single list (empty iff no columnwise adjacent original zeros
             -                                   AND no rowwise repeated values)
           Ȧ - any and all (0 if empty [or contains any zero -- never] else 1)

ZÇȯÇ_1Ŀ - Link 4, validity check? list of lists
Z       - transpose
 Ç      - call last link (2) as a monad rowwiseAnyAdjacentZerosOrColumnwiseAnyRepeatedValues?
   Ç    - call last link (2) as a monad columnwiseAnyAdjacentZerosOrRowwiseAnyRepeatedValues?
  ȯ     - logical OR
     1Ŀ - call link 1 as a monad (isConnected?)
    _   - subtract
        - this yields -1 for valid, while it yields 0 or 1 if not.

2ḶṗLṗLa⁸ÇÞḢ - Main link: list of lists
2Ḷ          - lowered range of 2 -> [0,1]
   L        - length (number of rows in the input)
  ṗ         - Cartesian power (all lists of zeros and ones of length L)
     L      - length (number of rows in the input again)
    ṗ       - Cartesian power (all grids of zeros and ones of same shape as the input)
       ⁸    - the input
      a     - logical AND -- effectively uses each of the formed grids as a mask
         Þ  - sort by:
        Ç   -   last link (3) as a monad
          Ḣ - head
            - implicit print