Jak trudna jest binarna łamigłówka Sudoku?

Sudoku jest dobrze znaną łamigłówką, która jest kompletna NP. Sudoku Binarne to wariant, który dopuszcza tylko cyfry i . Zasady są następujące. $0$ $1$

Każdy wiersz i każda kolumna musi zawierać równą liczbę zer i jedynek.
Każdy wiersz i każda kolumna jest unikalny.
Żaden wiersz ani kolumna nie zawiera kolejnych potrójnych zer lub jedynek ( to potrójne z jedynki). $1 1 1$

Dane wejściowe to kwadrat częściowo wypełniony zerami i zerami. Aby rozwiązać zagadkę, każda komórka w kwadracie musi być wypełniona przez lub przy zachowaniu powyższych zasad. Nie udało mi się znaleźć żadnego trudnego wyniku do rozwiązania zagadki Sudoku Binarnego. $N \times N$ $N \times N$ $0$ $1$

Jak ciężko jest rozwiązać zagadkę Sudoku Binarnego? Czy jest kompletny NP?

Interesuje mnie również złożoność powiązanego problemu.

Biorąc pod uwagę wypełniony kwadrat który jest zgodny tylko z powyższymi zasadami 1 i 2, $N \times N$

jak trudno jest znaleźć permutację wierszy i kolumn, aby wynikowy kwadrat był zgodny z regułą 3?

cc.complexity-theory np-hardness puzzles

— Mohammad Al-Turkistany
źródło

To nie jest ten sam problem, więc zostawię to jako komentarz niż odpowiedzi, ale nie wynik Problem NP-trudny do jednocyfrowych podproblemów standardowego rodzaju Sudoku w moim referacie arxiv.org/abs/1202.5074

— David Eppstein

Jako autor aplikacji binarnej łamigłówki (ten problem) mogę zaoferować obserwację (nie dowód): wszystkie przypadki tej układanki widziane w praktyce można rozwiązać w czasie wielomianowym, ale są przypadki, które wydają się nie do rozwiązania w ten sposób, a mianowicie dokładnie te przypadki, w których osiągasz stan, w którym żadna z trzech reguł bezpośrednio nie zmusza komórki do przyjęcia określonej wartości (tj. wydaje się, że musisz „spróbować czegoś” i być może cofnąć się do tego momentu).

— Harold

Hej, próbowałem stworzyć programy do rozwiązywania zagadek binarnych, z wyjątkiem tego, że mam trudności z ukończeniem bardzo trudnych zagadek binarnych i potrzebowałbym wskazówki, jak je rozwiązać. Mój program może z łatwością wykonywać wszystkie problemy binarne, z wyjątkiem bardzo trudnych

EDYCJA : Szybko ukończyłem amatorski dowód, że zacząłem kilka miesięcy temu i nigdy nie skończyłem.

Możesz pobrać go w formacie PDF na moim blogu ... nikt jeszcze tego nie sprawdził, więc odrzucenia, komentarze i sugestie są mile widziane.

Nie wiem, czy istnieje oficjalny dowód, ale kilka miesięcy temu zbudowałem gadżety, aby naśladować planarną formułę 3-CNF; na przykład gadżety OR, SPLIT i TURN to:

wprowadź opis zdjęcia tutaj

Zbudowałem / sprawdziłem gadżety za pomocą prostego programu do rozwiązywania ograniczeń.

Unikalność każdego wiersza / kolumny (reguła 2) można osiągnąć, oznaczając je unikalnym „numerem binarnym” za pomocą bloku 2x2, który działa jak „cyfra”:

01 = 0   10 = 1
10       01

Równą liczbę 1 i 0 (reguła 3) można uzyskać odzwierciedlając całą łamigłówkę i odwracając 0 z 1 (używając specjalnych ścian w środku, które umożliwiają przejście bez łamania zasad):

  3CNF simulation    |  wall  | 3CNF sim. with  | 0000 (using 2x2 blocks)
                     |        | 0,1 inverted    | 0001
 --------------------+        +-----------------+ 0010
    wall                        wall            | ....
 --------------------+        +-----------------+ ....
  3CNF sim. with     |  wall  | 3CNF simulation |
  0,1 inverted       |        |                 |
 --------------------+--------+-----------------+
 0101 .... (using 2x2 blocks)
 0011 ....
 0000 ....

$N \times N$

$\{0,1,\bot\}^{N \times N}$

— Marzio De Biasi
źródło

Chyba masz na myśli planarny obwód SAT?

— Mohammad Al-Turkistany

Mam na myśli Planarny typ 1 3CNF (dwustronny wykres między klauzulami 3CNF i zmiennymi jest płaski). Jeden gadżet służy do symulacji przypisania T / F, drugi służy do wymuszenia T na każdej klauzuli, 2 gadżety OR są używane do symulacji dwóch OR każdej klauzuli i SPLIT do dzielenia i „przenoszenia” sygnału z przypisań do klauzul. Teraz próbuję ukończyć pracę, jak tylko ją ukończę, opublikuję link w odpowiedzi.

— Marzio De Biasi

Zmniejszasz więc z NP-kompletny planarny sześcienny dwustronny monotoniczny problem 1-w-3 SAT. dobrze?

— Mohammad Al-Turkistany

Nie, „typ 1” oznacza konkretną zastosowaną płaską formułę 3CNF (istnieje niewielka różnica między typem 1 a typem 2). Zastosowałem podobną redukcję, aby udowodnić kompletność NP gry logicznej Namiot ; możesz zajrzeć do tego artykułu, jednak myślę, że za 1-2 dni opublikuję kompletny dowód problemu binarnego sudoku - inaczej układanki binarnej (właśnie ukończyłem migawki gadżetów) (i mam nadzieję, że „ Zobaczę, czy to naprawdę działa :-)

— Marzio De Biasi

Powodzenia, nie mogę się doczekać.

— Mohammad Al-Turkistany