Einführung

Regeln des Puzzles:

Das Puzzle Binary (auch bekannt als Takuzu oder Subiku) ist sehr einfach zu verstehen und hat nur wenige Regeln:
Da der Name des Spiels binär ist, ist es ziemlich offensichtlich, aber Sie können nur Nullen und Einsen eingeben.

1. Es dürfen nicht mehr als zwei gleiche Ziffern vertikal oder horizontal nebeneinander liegen
2. Jede Zeile und jede Spalte muss gleich viele Nullen und Einsen enthalten (dies bedeutet implizit, dass jedes Binärspiel immer gerade Dimensionen hat).
3. Es dürfen keine doppelten Zeilen und keine doppelten Spalten vorhanden sein (mit genau der gleichen Reihenfolge von Nullen und Einsen).

Sie können das Spiel auf www.binarypuzzle.com spielen, wenn Sie möchten.

Taktik:

Aufgrund von Regel 1 können wir immer eine Ziffer eingeben, wenn:
- bereits zwei gleiche Ziffern vertikal oder horizontal nebeneinander liegen. In diesem Fall können wir die gegenüberliegende Ziffer auf beiden Seiten eingeben. Dh .11...→ 0110...
- Es gibt zwei gleiche Ziffern vertikal oder horizontal mit nur einer Lücke dazwischen. Dh .1.1..→.101..

Aufgrund von Regel 1 können wir eine der Lücken füllen, wenn drei Lücken übrig sind und wir nicht drei neben derselben Ziffer haben können. Dh .0.1.0→ 10.1.0(Wir müssen noch zwei ausfüllen, und wir können nicht drei benachbarte in der Mitte haben, also muss die erste Lücke a sein 1.)

Aufgrund von Regel 2 können wir die verbleibenden Lücken in einer Zeile oder Spalte immer dann ausfüllen, wenn die Hälfte davon bereits mit der entgegengesetzten Ziffer ausgefüllt ist. Dh .1.011→010011

Aufgrund von Regel 3 können wir immer die entgegengesetzten Ziffern eingeben, wenn nur noch zwei in einer gleich geordneten Zeile zu lösen sind. Dh 101100 & 1..100→101100 & 110100

Aufgrund von Regel 3 können wir manchmal eine Lücke füllen, wenn drei Lücken in einer gleich geordneten Linie verbleiben. Dh 010011 & .1.01.→ 010011 & .1.010(Hier können wir 1am Ende kein a ausfüllen , da dies bedeuten würde, dass wir an den beiden anderen Lücken Nullen ausfüllen müssen, sodass beide Zeilen der Reihe nach gleich sind.)

Beispiel:

Wir beginnen mit dem folgenden 6x6-Raster, in dem einige Einsen und Nullen ausgefüllt sind (und die Punkte sind Lücken, die wir noch ausfüllen müssen):

.1....
.10.0.
1.11..
.1....
...1.0
......

Aufgrund der Regeln 1 und 2 können wir folgende Ziffern eingeben:

.1.01.
.1010.
101100
010011
.0.1.0
.010..

Aufgrund von Regel 1 können wir in Zeile 5, Spalte 1 eine 1 eintragen:

.1.01.
.1010.
101100
010011
10.1.0
.010..

Aufgrund von Regel 3 können wir in Zeile 1, Spalte 6 (bei Betrachtung von Zeile 4) eine 0 eintragen:

.1.010
.1010.
101100
010011
10.1.0
.010..

Jetzt können wir aufgrund der Regeln 1 und 2 weiterhin Lücken mit Ziffern füllen:

.1.010
010101
101100
010011
10.1.0
.010.1

Jetzt können wir Zeile 5 aufgrund von Regel 3 beenden (wenn wir Zeile 3 betrachten):

.1.010
010101
101100
010011
100110
.010.1

Und dann können wir das Rätsel aufgrund der Regeln 1 und 2 beenden:

011010
010101
101100
010011
100110
101001

Herausforderung:

Die Herausforderung ist einfach: Geben Sie angesichts des Startgitters das gelöste Rätsel aus.

HINWEIS: Sie müssen die oben genannten Regeln nicht implementieren. Das können Sie natürlich, und es sollte Ihnen Hinweise geben, wie Sie diese Herausforderung umsetzen können, aber es ist völlig in Ordnung, die Lösung unter Berücksichtigung der Regeln brutal durchzusetzen.
Wie Sie es lösen, liegt bei Ihnen, aber die Herausforderung besteht darin, das gelöste Rätsel auszugeben.

Herausforderungsregeln:

• Das Eingabe- und Ausgabeformat für das Raster ist flexibel. Bitte geben Sie an, was Sie verwenden. (Dh 2D-Byte-Array; String mit Zeilenumbrüchen usw.)
• Dies gilt auch für die verwendeten Zeichen. In dem Beispiel, das ich verwendet habe 01., aber wenn Sie möchten, können Sie ABxstattdessen verwenden. Bitte geben Sie an, welches Eingabe- / Ausgabeformat und welche Zeichen Sie verwendet haben.
• Sie können davon ausgehen, dass nur die folgenden Rastergrößen verwendet werden : 6x6; 8x8;; 10x10;; 12x12;; 14x14;; 16x16.

Allgemeine Regeln:

• Dies ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes.
  Lassen Sie sich nicht von Code-Golf-Sprachen davon abhalten, Antworten mit Nicht-Codegolf-Sprachen zu veröffentlichen. Versuchen Sie, eine möglichst kurze Antwort für "jede" Programmiersprache zu finden.
• Für Ihre Antwort gelten Standardregeln , sodass Sie STDIN / STDOUT, Funktionen / Methoden mit den richtigen Parametern und vollständige Programme verwenden dürfen. Ihr Anruf.
• Standardschlupflöcher sind verboten.
• Wenn möglich, fügen Sie bitte einen Link mit einem Test für Ihren Code hinzu.
• Fügen Sie bei Bedarf auch eine Erklärung hinzu.

Testfälle:

Die Punkte werden nur zur besseren Lesbarkeit hinzugefügt. Verwenden Sie stattdessen Leerzeichen oder andere Elemente, die Sie für Lücken bevorzugen. Sowohl das In- als auch das Ausgabeformat sind flexibel.

Input:
1..0..
..00.1
.00..1
......
00.1..
.1..00

Output:
101010
010011
100101
011010
001101
110100

Input:
.1....
.10.0.
1.11..
.1....
...1.0
......

Output:
011010
010101
101100
010011
100110
101001

Input:
.......1..
.00..0..1.
.0..1..0.0
..1...1...
1.1......1
.......1..
.0..1...0.
....11...0
.0.0..1..0
0...0...1.

Output:
0110010101
1001100110
1001101010
0110011001
1010100101
0101010110
1001101001
0110110100
1010011010
0101001011

Brachylog , 34 Bytes

{ℕ<2}ᵐ²&≜{d?ọᵐctᵐ=&{ḅlᵐ⌉<3}ᵐ}&\↰₂&

Probieren Sie es online aus!

Das ist verdammt langsam, also ist der Testfall auf TIO 4x4. Ich führe derzeit den 6x6-Testfall auf meinem Computer aus, um zu sehen, wie lange es dauert.

Dies nimmt eine Liste von Listen als Eingabe. Die unbekannten Werte sollten mit Variablen angegeben werden, dh mit Zeichenfolgen in Großbuchstaben (und sie sollten alle unterschiedlich sein, da Sie sonst angeben würden, dass einige Zellen denselben Wert haben müssen).

Erläuterung

Wir beschränken die Werte, in denen {0,1}wir uns befinden, und versuchen dann, die Variablen zu instanziieren, bis alle drei Regeln eingehalten werden. Dies ist der Grund, warum dies so langsam ist (weil alle getestet werden, bis eine gefunden wird; und weil in diesem Fall Brachylog nicht gut genug implementiert ist, so dass Einschränkungen auferlegt werden können, bevor eine mögliche Matrix ausprobiert wird).

                                 &  Output = Input
{   }ᵐ²                             Map two levels on the Input (i.e. each cell):
 ℕ<2                                  The cell is either 0 or 1
       &≜                           Assign values to all cells
         {                  }       Define predicate 2:
          d?                          The Input with no duplicates is still the Input
                                        (i.e. all rows are different)
           ?ọᵐctᵐ=                    All occurences of 1s and 0s for each rows are equal
                  &{      }ᵐ          Map on rows:
                    ḅlᵐ                 Get the lengths of runs of equal values
                       ⌉<3              The largest one is strictly less than 3
                             &\↰₂   Apply predicate 2 on the transpose of the Input
                                      (i.e. do the same checks but on columns)

JavaScript (ES6), 274 270 Byte

Übernimmt die Eingabe als 2D-Array, in dem leere Zellen mit markiert sind 2. Druckt alle möglichen Lösungen auf die Konsole.

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

Wie es funktioniert

Der erste Teil des Codes verwendet die M()Funktion, um die Gültigkeit der aktuellen Karte sowohl horizontal als auch vertikal zu überprüfen.

M = z =>
  !a.some((r, y) =>
    /(0|1),\1,\1/.exec(
      s = r.map((v, x) =>
        (
          v = z ? v : a[x][y],
          b -= v & 1,
          c -= !v,
          m |= v & 2,
          v
        ),
        b = c = w / 2
      )
    ) ||
    b * c < 0 |
    o[b * c || s] &
    (o[s] = 1),
    o = {}
  )

Es ordnet eine vollständige Zeile oder Spalte der Zeichenfolge s zu . Dies ist eigentlich ein Array, das zu einem String gezwungen wird, also sieht es so aus "1,2,2,0,2,2".

Es verwendet:

• Der reguläre Ausdruck /(0|1),\1,\1/zum Erkennen von 3 oder mehr aufeinanderfolgenden identischen Ziffern.
• Die Zähler b und c verfolgen die Anzahl der Einsen und Nullen . Beide Zähler werden auf w / 2 initialisiert und jedes Mal dekrementiert, wenn eine Eins bzw. eine Null angetroffen wird. Dies führt zu entweder:
  • b = c = 0 → b * c = 0 → die Zeile ist vollständig und korrekt (so viele Nullen wie Einsen )
  • b> 0 UND c> 0 → b * c> 0 → Die Zeile ist noch nicht vollständig, aber korrekt (wir haben nicht mehr als w / 2 Nullen oder mehr als w / 2 Einsen ).
  • b <0 ODER c <0 → b * c <0 → die Zeile ist ungültig
• Das Flag m (für 'fehlt'), das ungleich Null ist, wenn mindestens zwei auf dem Brett verbleiben .
• Das Ziel o , alle bisher angetroffenen Linienmuster zu verfolgen.

Wenn die Karte ungültig ist, hören wir sofort auf. Wenn die Karte gültig und vollständig ist, drucken wir sie auf die Konsole. Andernfalls versucht der zweite Teil des Codes, jede 2 durch eine Null oder eine Eins mit rekursiven Aufrufen zu ersetzen :

[0, 1].map(n =>
  (p = a[y][x]) == n |
  p > 1 && (
    a[y][x] = n,
    f(a, z = (x + 1) % w, y + !z),
    a[y][x] = p
  )
)

Demo

f=(a,x=0,y=0,w=a.length,p,R=a[y])=>(M=z=>!a.some((r,y)=>/(0|1),\1,\1/.exec(s=r.map((v,x)=>(v=z?v:a[x][y],b-=v&1,c-=!v,m|=v&2,v),b=c=w/2))||b*c<0|o[b*c||s]&(o[s]=1),o={}))(m=0)&M(1)&&(m?R&&[0,1].map(n=>(p=R[x])==n|p>1&&(R[x]=n,f(a,z=(x+1)%w,y+!z),R[x]=p)):console.log(a))

console.log('Example #1')
f([
  [1,2,2,0,2,2],
  [2,2,0,0,2,1],
  [2,0,0,2,2,1],
  [2,2,2,2,2,2],
  [0,0,2,1,2,2],
  [2,1,2,2,0,0]
])

console.log('Example #2')
f([
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,0,2,2,0,2,2,1,2],
  [2,0,2,2,1,2,2,0,2,0],
  [2,2,1,2,2,2,1,2,2,2],
  [1,2,1,2,2,2,2,2,2,1],
  [2,2,2,2,2,2,2,1,2,2],
  [2,0,2,2,1,2,2,2,0,2],
  [2,2,2,2,1,1,2,2,2,0],
  [2,0,2,0,2,2,1,2,2,0],
  [0,2,2,2,0,2,2,2,1,2]
])

Gelee , 53 51 Bytes

ṡ€3ḄFf0,7L
SḤnLṀȯÇ
⁻QȯÇ
Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ

Nimmt eine Liste von Listen das Gitter darstellt, enthält 0, 1und 2(Leerzeichen). Gibt eine Liste von Listen von Listen zurück. Jede Liste von Listen hat dasselbe Format (obwohl ohne 2s) und stellt eine mögliche Lösung für die Eingabe dar.

Probieren Sie es online aus! (Dies führt aufgrund von Speicherbeschränkungen keinen der Testfälle der Frage aus. Alle 2 ^nSpaces- Gitter werden als Liste mit Listen mit Ganzzahlen erstellt. Ich habe dort jedoch einen relativ umfangreichen Fall mit einer einzigen Lösung angegeben.) Die Fußzeile wird getrennt und formatiert die Raster.

Reine Brute-Force-Methode - implementiert die Regeln und überprüft sie für jedes Gitter, das durch Ersetzen eines der 2s durch 1s oder 0s gebildet werden könnte.

ṡ€3ḄFf0,7L - Link 1, # of runs of 3 1s or 3 0s by row: list of lists
ṡ€3        - all contiguous slices of length 3 for €ach list
   Ḅ       - convert all results from binary
    F      - flatten into one list
     f     - filter keep values in:
      0,7  -   0 paired with 7: [0,7]
         L - length

SḤnLṀȯÇ - Link 2, unequal counts of 1s and 0s by column ...or link 1: list of lists
S       - sum (vectorises, hence "by column", counts 1s since only 1s or 0s appear)
 Ḥ      - double
   L    - length (number of rows - OK since square)
  n     - not equal? (vectorises)
    Ṁ   - maximum (1 if any not equal)
     ȯÇ - ... or last link (1) as a monad

⁻QȯÇ - Link 3, rows are unique ...or link 2: list of lists
 Q   - unique
⁻    - not equal?
  ȯÇ - ... or last link (2) as a monad

Fṣ©2L’0,1ṗż@€®F€s€LÇÐḟZÇ$Ðḟ - Main link: list of lists
F                           - flatten
 ṣ©2                        - split at 2s and copy the result to the register
    L                       - length (# of such slices)
     ’                      - decrement (# of 2s)
      0,1                   - 0 paired with 1
         ṗ                  - Cartesian power (all binary lists of length # of 2s)
             ®              - recall value from register (the flat version split at 2s)
          ż@€               - zip (reversed @rguments) for €ach (1s & 0s where 2s were)
              F€            - flatten €ach
                s€L         - split €ach into chunks of length length(input) (into rows)
                    Ðḟ      - filter discard if:
                   Ç        -   call last link(3) as a monad
                         Ðḟ - filter discard if:
                        $   -   last two links as a monad:
                      Z     -     transpose
                       Ç    -     call last link(3) as a monad