Насколько сложна двоичная головоломка судоку?

Судоку - это хорошо известная головоломка, которая является NP-полной. Двоичный судоку - это вариант, который допускает только цифры и . Правила следующие. $0$ $1$

Каждая строка и каждый столбец должны содержать одинаковое количество нулей и единиц.
Каждая строка и каждый столбец уникальны.
Ни одна строка или столбец не содержит последовательные тройки нулей или единиц ( - последовательная тройка единиц). $1 1 1$

На входе находится квадрат частично заполненный нулями и единицами. Чтобы решить головоломку, каждая ячейка в квадрате должна быть заполнена либо либо , соблюдая при этом вышеуказанные правила. Я не смог найти какой-либо непостижимый результат для решения головоломки Binary Sudoku. $N \times N$ $N \times N$ $0$ $1$

Насколько сложно решить бинарную головоломку судоку? Это NP-полный?

Также меня интересует сложность связанной проблемы.

Учитывая полностью заполненный квадрат который соответствует только правилам 1 и 2 выше, $N \times N$

Насколько сложно найти перестановку строк и столбцов, чтобы получающийся квадрат соответствовал правилу 3?

cc.complexity-theory np-hardness puzzles Мухаммед Аль-Туркистани
источник

Это не та же проблема , поэтому я оставлю это как комментарий , а не ответ, но есть результат NP-твердость для однозначных подзадач стандартного вида головоломки Судоку в моей работе arxiv.org/abs/1202.5074

Дэвид Эпштайна

Как автор приложения бинарной головоломки (эта проблема), я могу предложить вам наблюдение (а не доказательство): все случаи этой головоломки, которые можно увидеть на практике, могут быть решены за полиномиальное время, но есть случаи, которые кажутся нерешаемыми таким образом, а именно в тех случаях, когда вы достигаете состояния, когда ни одно из трех правил не заставляет ячейку принимать определенное значение (то есть кажется, что вам нужно «попробовать что-то» и, возможно, вернуться к этому моменту).

Гарольд

Привет, я пытался создать программу для решения бинарных головоломок, за исключением того, что мне трудно завершать очень сложные бинарные головоломки, и мне понадобится подсказка для их разрешения. Моя программа может легко решить все бинарные проблемы, кроме очень сложных

Ответы:

РЕДАКТИРОВАТЬ : я быстро завершил любительское доказательство, которое я начал несколько месяцев назад и никогда не закончил.

Вы можете скачать его в формате PDF на моем блоге ... никто еще не проверил его, поэтому опровержения, комментарии и предложения приветствуются.

Я не знаю, есть ли официальные доказательства, но несколько месяцев назад я создал гаджеты, чтобы имитировать плоскую формулу 3-CNF; например гаджеты OR, SPLIT и TURN:

введите описание изображения здесь

Я построил / проверил гаджеты, используя простую программу решения ограничений.

Уникальность каждой строки / столбца (правило 2) может быть достигнута, помечая их уникальным «двоичным числом», используя блок 2x2, который действует как «цифра»:

01 = 0   10 = 1
10       01

И равное количество единиц и нулей (правило 3) может быть достигнуто путем зеркального отражения всей головоломки и инвертирования нулей с единицами (используя специальные стены в середине, которые позволяют переход без нарушения правил):

  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}$

Марцио де Биаси
источник

Я предполагаю, что вы имеете в виду плоскую схему SAT?

Мухаммед Аль-Туркистани

Я имею в виду Планарный тип 1 3CNF (двудольный граф между предложениями и переменными 3CNF плоский). Один гаджет используется для имитации назначения T / F, другой - для принудительного ввода T в каждом предложении, 2 гаджета OR - для имитации двух OR в каждом предложении, а SPLIT - для разделения и «переноса» сигнала из назначений. к пунктам. Сейчас я пытаюсь завершить работу, как только я закончу, я опубликую ссылку в ответе.

Марцио де Биаси

Таким образом, вы сокращаете от NP-полной плоской кубической двудольной монотонной задачи 1-в-3 SAT. право?

Мухаммед Аль-Туркистани

Нет, «тип 1» означает конкретную плоскую формулу 3CNF (есть небольшая разница между типом 1 и типом 2). Я использовал аналогичное сокращение, чтобы доказать NP-полноту игры-головоломки Tent ; Вы можете взглянуть на эту статью, однако я думаю, что через 1-2 дня я опубликую полное доказательство проблемы бинарной судоку - бинарной головоломки (я только что закончил снимки гаджетов) (и я надеюсь, что вы ' Я посмотрю на это, чтобы увидеть, действительно ли это работает :-)

Марцио Де Биаси

Удачи, я не могу ждать.

Мохаммед Аль-Туркистани