Einführung

Schreiben Sie einen Löser für die Hitori- Rätsel mit den wenigsten Bytes.

Herausforderung

Ihre Aufgabe ist es, einen Löser für die Hitori (ひ ひ と, das Wort für "allein" auf Japanisch; der Name des Spiels lautet "Lass mich in Ruhe") zu schreiben. Die Regeln lauten wie folgt:

• Es wird ein n-mal-n-Gitter mit Zellen angezeigt, wobei jede Zelle eine ganze Zahl zwischen 1 und n (einschließlich) enthält.
• Ihr Ziel ist es, sicherzustellen, dass keine Zahl mehr als einmal in jeder Zeile und jeder Spalte des Rasters vorkommt, indem Sie Zahlen aus dem angegebenen Raster entfernen, vorbehaltlich der in den nächsten beiden Regeln angegebenen Einschränkungen.
• Sie können zwei Zahlen nicht aus zwei benachbarten (horizontal oder vertikal) Zellen entfernen.
• Die verbleibenden nummerierten Zellen müssen alle miteinander verbunden sein. Dies bedeutet, dass zwei verbleibende nummerierte Zellen mit einer Kurve verbunden werden können, die nur aus Segmenten besteht, die benachbarte verbleibende Zahlen (horizontal oder vertikal) verbinden. (Danke an @ user202729 für den Hinweis, dass dies fehlt)

Ich hoffe, die Regeln sind jetzt klar. Wenn die Regeln unklar sind, überprüfen Sie die Wikipedia-Seite .

Testfälle

Die Zellen, aus denen die Zahlen entfernt werden, werden mit 0en dargestellt.

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 

Diese Testfälle stammen aus Concept Is Puzzles , PuzzleBooks , Concept Is Puzzles , Wikipedia bzw. Youtube .

Technische Daten

• Sie müssen sich keine Sorgen um die Ausnahmebehandlung machen.

• Sie können davon ausgehen, dass die Eingabe immer ein gültiges Puzzle mit einer eindeutigen Lösung ist, und Sie können dies beim Schreiben Ihres Codes nutzen.

• Dies ist Code-Golf , die niedrigste Anzahl von Bytes gewinnt.

• 4 <= n <= 9 (16 ursprünglich in 9 geändert nach dem Vorschlag von Stewie Griffin, ersparen Sie auch einige Probleme bei der Eingabe / Ausgabe)

• Sie können Eingaben und Ausgaben über jedes Standardformular vornehmen und das Format frei wählen.

• Einige Vorschläge für das Ausgabeformat sind (aber Sie sind nicht auf diese beschränkt)

  • Ausgabe des endgültigen Rasters
  • Ausgabe des Rasters mit allen entfernten Zahlen
  • Geben Sie eine Liste der Koordinaten einer der oben genannten aus

• Wie üblich gelten hier Standardlücken .

_{Verwandt (inspiriert von dieser Herausforderung): Überprüfen Sie, ob alle Elemente in einer Matrix verbunden sind}

_{Meine letzte Herausforderung: Erweiterung des Spiels der Siebener}

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

Probieren Sie es online!

APL (Dyalog Unicode) , 133 Byte ^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}

Probieren Sie es online!

Meine Implementierung von Regel Nr. 4 (Zellen müssen eine einzige verbundene Komponente bilden) ist ziemlich verschwenderisch, aber dennoch besteht dies alle Tests in ungefähr 10 Sekunden auf TIO.

Der allgemeine Algorithmus: Speichern Sie zwei boolesche Matrizen bund wfür Zellen, die mit Sicherheit schwarz bzw. weiß sind. Initialisiere balles als Null. Initialisieren Sie wals 1 nur für die Zellen, die entgegengesetzte übereinstimmende Nachbarn haben.

Wiederholen bis bund zur wRuhe kommen:

• Zu bZellen hinzufügen, die sich in derselben Zeile (horizontal oder vertikal) befinden und denselben Wert wie eine Zelle in habenw

• zu wden unmittelbaren Nachbarn aller Zellen in hinzufügenb

• Zu wallen Schnittpunkten hinzufügen - Zellen, deren Entfernung den Graphen nicht schwarzer Zellen in mehrere verbundene Komponenten aufteilen würde

Schließlich wird die Ausgabe not(b)mit der ursprünglichen Matrix multipliziert.

Jelly , 62 Bytes

Verwendet den isConnected-Monadic-Link von user202729 aus einer anderen Frage.

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

Ein vollständiges Programm, das eine Darstellung einer Liste von Listen druckt.
Arbeitet mit roher Gewalt und ist dumm ineffizient.

Probieren Sie es online! - ein 3 mal 3, da es zu ineffizient ist, sogar eine Größe 4 innerhalb des 60-Sekunden-TIO-Limits auszuführen!

Wie?

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