Wprowadzenie

Zasady układanki:

Układanka Binarna (znana również jako Takuzu lub Subiku) jest bardzo łatwa do zrozumienia i ma tylko kilka zasad:
Ponieważ nazwa gry jest binarna, jest dość oczywista, ale można wprowadzać tylko zera i jedynki.

1. Nie więcej niż dwie takie same cyfry mogą znajdować się obok siebie w pionie lub poziomie
2. Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek (to domyślnie oznacza, że ​​każda gra binarna zawsze będzie miała równe wymiary).
3. Może nie być zduplikowanych wierszy ani zduplikowanych kolumn (z dokładnie taką samą kolejnością zer i jedynek).

Możesz zagrać w grę na stronie www.binarypuzzle.com, jeśli chcesz.

Taktyka:

Zgodnie z regułą 1 zawsze możemy wpisać cyfrę, jeżeli:
- Istnieją już dwie takie same cyfry w pionie lub poziomie sąsiadujące ze sobą, w którym to przypadku możemy wpisać cyfrę przeciwną po obu stronach. Tj .11...→ 0110...
- Istnieją dwie takie same cyfry w pionie lub poziomie, z tylko jedną przerwą między nimi. tj .1.1..→.101..

Zgodnie z regułą 1, gdy pozostały trzy przerwy i nie możemy mieć trzech sąsiadujących z tą samą cyfrą, możemy wypełnić jedną z tych przerw. Tj. .0.1.0→ 10.1.0(Wciąż musimy wypełnić dwa i nie możemy mieć trzech sąsiadujących na środku, więc pierwsza przerwa musi być a 1.)

Zgodnie z regułą 2 zawsze możemy wypełnić pozostałe luki w rzędzie lub kolumnie, jeśli połowa z nich jest już wypełniona przeciwną cyfrą. tj .1.011→010011

Ze względu na zasadę 3, zawsze możemy wypełnić przeciwne cyfry, jeśli pozostaną tylko dwie do rozwiązania na równo uporządkowanej linii. tj 101100 & 1..100→101100 & 110100

Ze względu na zasadę 3 możemy czasami wypełnić lukę, gdy trzy luki pozostaną na równo uporządkowanej linii. Tj. 010011 & .1.01.→ 010011 & .1.010(Tutaj nie możemy wypełnić1 na końcu, ponieważ oznaczałoby to, że musimy wypełnić zera na dwóch pozostałych przerwach, dzięki czemu obie linie będą jednakowe w kolejności.)

Przykład:

Zaczynamy od następującej siatki 6x6 z wypełnionymi zerami i zerami (a kropki to luki, które musimy jeszcze wypełnić):

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

Ze względu na zasady 1 i 2 możemy wpisać następujące cyfry:

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

Zgodnie z regułą 1 możemy wypełnić 1 w wierszu 5, kolumnie 1:

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

Zgodnie z zasadą 3 możemy wypełnić 0 w wierszu 1, kolumnie 6 (patrząc na wiersz 4):

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

Teraz możemy nadal wypełniać luki cyframi zgodnie z regułami 1 i 2:

.1.010
010101
101100
010011
10.1.0
.010.1

Teraz możemy zakończyć wiersz 5 ze względu na zasadę 3 (patrząc na wiersz 3):

.1.010
010101
101100
010011
100110
.010.1

Następnie możemy ukończyć układankę zgodnie z zasadami 1 i 2:

011010
010101
101100
010011
100110
101001

Wyzwanie:

Wyzwanie jest proste: biorąc pod uwagę początkową siatkę, wyjmij rozwiązaną zagadkę.

UWAGA: Nie musisz wdrażać powyższych zasad. Oczywiście możesz i powinien on dać ci wskazówki, jak wdrożyć to wyzwanie, ale brutalne wymuszanie rozwiązania z myślą o regułach jest całkowicie w porządku.
Sposób rozwiązania zależy od Ciebie, ale wyzwaniem jest wyjście z rozwiązanej układanki.

Zasady konkursu:

• Format wejścia i wyjścia dla siatki jest elastyczny, ale proszę podać, czego używasz. (Tj. Tablica bajtów 2D; ciąg znaków z nowymi liniami; itp.)
• Powyższe dotyczy również użytych znaków. W przykładzie, którego użyłem 01., ale jeśli chcesz, możesz użyćABx zamiast tego. Proszę podać, jakiego formatu wejścia / wyjścia i znaków użyłeś.
• Można tylko przypuszczać, wykorzystane zostaną następujące rozmiary siatki: 6x6; 8x8; 10x10; 12x12; 14x14; 16x16.

Główne zasady:

• To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach.
  Nie pozwól, aby języki kod-golfowe zniechęcały Cię do publikowania odpowiedzi w językach niekodujących golfa. Spróbuj znaleźć możliwie najkrótszą odpowiedź na „dowolny” język programowania.
• Do odpowiedzi odnoszą się standardowe reguły , więc możesz używać STDIN / STDOUT, funkcji / metody z odpowiednimi parametrami, pełnych programów. Twoja decyzja.
• Domyślne luki są zabronione.
• Jeśli to możliwe, dodaj link z testem swojego kodu.
• W razie potrzeby dodaj również wyjaśnienie.

Przypadki testowe:

Kropki są dodawane tylko dla czytelności, możesz zamiast tego użyć spacji lub cokolwiek innego, co wolisz dla przerw. Format zarówno wyjściowy, jak i wyjściowy jest elastyczny.

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 bajty

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

Wypróbuj online!

To jest cholernie wolne, więc przypadek testowy na TIO to 4x4. Obecnie uruchomię testową skrzynkę 6x6 na moim komputerze, aby zobaczyć, ile czasu to zajmuje.

To pobiera listę list jako dane wejściowe. Nieznane wartości należy wskazać zmiennymi, czyli ciągami wielkimi literami (i wszystkie powinny być różne, ponieważ w przeciwnym razie wskazujesz, że niektóre komórki muszą mieć tę samą wartość)

Wyjaśnienie

Ograniczamy wartości, które mają się znaleźć {0,1}, a następnie próbujemy tworzyć wystąpienia zmiennych, dopóki nie przestrzega się wszystkich 3 reguł. Dlatego jest to tak powolne (ponieważ spróbuje wszystkich z nich, aż do znalezienia jednego; i ponieważ w takim przypadku Brachylog nie jest wystarczająco dobrze wdrożony, aby można było nałożyć ograniczenia przed wypróbowaniem możliwej matrycy).

                                 &  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 bajtów

Pobiera dane wejściowe jako tablicę 2D, w której puste komórki są oznaczone 2. Drukuje wszystkie możliwe rozwiązania do konsoli.

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

Jak to działa

Pierwsza część kodu używa M()funkcji do sprawdzania poprawności bieżącej płytki, zarówno poziomo, jak i pionowo.

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 = {}
  )

Odwzorowuje pełny wiersz lub kolumnę na ciąg s . W rzeczywistości jest to tablica wymuszona na łańcuch, więc wygląda na to, że "1,2,2,0,2,2".

To używa:

• Wyrażenie regularne /(0|1),\1,\1/do wykrywania 3 lub więcej kolejnych identycznych cyfr.
• Liczniki b i c służą do śledzenia liczby zer i jedynek . Oba liczniki są inicjowane do w / 2 i zmniejszane za każdym razem, gdy napotkane jest jedno lub zero (odpowiednio). Prowadzi to do:
  • B = C = 0 → b * c = 0 → linia jest pełne i prawidłowy (tyle zer jak te )
  • b> 0 i c> 0 → b * c> 0 → linia nie jest kompletna, ale poprawna tak daleko (nie mamy więcej niż w / 2 zer lub więcej niż w / 2 z nich )
  • b <0 LUB c <0 → b * c <0 → wiersz jest nieprawidłowy
• Flaga m (dla „brakującej”), która jest niezerowa, jeśli na planszy pozostało co najmniej dwa .
• Obiekt o do śledzenia wszystkich napotkanych dotychczas wzorów linii.

Jeśli tablica jest nieważna, natychmiast się zatrzymujemy. Jeśli płyta jest ważna i kompletna, drukujemy ją na konsoli. W przeciwnym razie druga część kodu próbuje zastąpić każdą 2 wartością zero lub jedną z wywołaniami rekurencyjnymi:

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

Próbny

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

Galaretka , 53 51 bajtów

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

Pobiera listę list reprezentujących siatkę, zawierające 0, 1oraz 2(spacje). Zwraca listę list, każda lista list ma ten sam format (chociaż bez 2s) i reprezentuje możliwe rozwiązanie danych wejściowych.

Wypróbuj online! (nie uruchomi to żadnego z przypadków testowych pytania z powodu ograniczeń pamięci - wszystkiesiatki2 ^nSpaces są tworzone jako lista list liczb całkowitych - ale umieściłem tam stosunkowo spory przypadek z jednym rozwiązaniem). Stopka oddziela i formatuje siatki.

Metoda czystej siły brutalnej - wdraża reguły i sprawdza je dla każdej siatki, którą można utworzyć, zastępując dowolne 2s 1s lub 0s.

ṡ€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