Настольные задачки с алгеброй бинарных переменных

Настольные головоломки с алгеброй двоичных переменных требуют от игроков найти скрытые объекты на основе набора ячеек-подсказок и их соседей, отмеченных как переменные (неизвестные). Переменная со значением 1 соответствует ячейке с объектом. Напротив, переменная со значением 0 соответствует пустой ячейке — никакого скрытого объекта.

Обзор

Эти головоломки основаны на алгебре с двоичными переменными, принимающими пару значений, например (нет, да), (ложь, правда), (не существует, существует), ( 0 , 1 ). Он предлагает игроку быстро составить некоторые уравнения и неравенства для решения. Разделение можно использовать для уменьшения сложности проблемы. Более того, если головоломка составлена ​​таким образом, что существует только единственное решение , этот факт можно использовать для исключения некоторых переменных без вычислений.

Задачу можно смоделировать как двоично-целочисленное линейное программирование , которое является частным случаем целочисленного линейного программирования.

История

Minesweeper , наряду со своими вариантами , является наиболее ярким примером головоломок такого типа.

Алгебра с двоичными переменными

Ниже буквы в математических утверждениях используются в качестве переменных, каждая из которых может принимать только значение 0 или 1 . Ниже приведен простой пример уравнения с двоичными переменными:

а + б = 0

Здесь есть две переменные a и b, но одно уравнение. Решение ограничено тем фактом, что a и b могут принимать только значения 0 или 1 . Здесь есть только одно решение: и a = 0 , и b = 0 . Еще один простой пример приведен ниже:

а + б = 2

Решение простое: a и b должны быть равны 1 , чтобы a + b было равно 2 .

Еще один интересный случай показан ниже:

а + б + с = 2

а + б ≤ 1

Здесь первое утверждение представляет собой уравнение, а второе утверждение представляет собой неравенство, указывающее на три возможных случая:

1. а = 1 и б = 0 ,
2. a = 0 и b = 1 , и
3. а = 0 и б = 0 ,

Последний случай вызывает противоречие относительно c, заставляя c = 2 , что невозможно. Следовательно, верен либо первый, либо второй случай. Это приводит к тому, что c должно быть равно 1 .

Преобразовать большое уравнение в меньшую форму нетрудно. Однако систему уравнений с двоичными переменными не всегда можно решить с помощью применения линейной алгебры. Ниже приведен пример применения вычитания двух уравнений:

а + б + в + г = 3

в + д = 1

Первый оператор имеет четыре переменные, тогда как второй оператор имеет только две переменные. Последнее означает, что сумма c и d равна 1 . Используя этот факт в первом утверждении, приведенные выше уравнения можно свести к

а + б = 2

в + д = 1

Алгебра на доске

Рисунок 1. Пример головоломки на доске 4х4.

Игру, основанную на алгебре с двоичными переменными, можно визуализировать разными способами. Один из общих способов — представить правую часть уравнения как подсказку в ячейке (подсказку), а соседей подсказки — как переменные. Простой случай показан на рисунке 1. Можно предположить, что соседями являются верхние/нижние, левые/правые и угловые ячейки, имеющие общий край или угол. Белые клетки могут содержать скрытый объект или ничего не содержать. Другими словами, это двоичные переменные. Они располагаются в левой части уравнений. Каждая ячейка подсказки (ячейка с синим фоном на рисунке 1) содержит положительное число, соответствующее количеству ее соседей, у которых есть скрытые объекты. Общее количество объектов на доске можно указать в качестве дополнительной подсказки. Та же плата с отмеченными переменными показана на рисунке 2.

Сведение к системе уравнений с двоичными переменными

Основное уравнение записано с использованием общего количества заданных скрытых объектов. Судя по первому рисунку, это соответствует следующему уравнению

a + b + c + d + e + f + g + h + i + j + k + m = 3

Остальные уравнения составляются одно за другим для каждой ячейки подсказки:

а + б + в + е + ж + ч + я + j = 1

ж + г + j + м = 1

ч + я + j + k = 2

я + j + м = 2

Хотя существует несколько способов решения приведенных выше уравнений, можно применить следующий явный способ:

1. Из системы уравнений известно, что i + j + m = 2 . Однако, поскольку j и m являются соседями ячейки с номером 1 , верно следующее: j + m ≤ 1 . Это означает, что переменная i должна быть равна 1 .
2. Поскольку i = 1 и переменная i является соседкой ячейки подсказки с номером 1 , переменные a , b , c , e , f , h и j должны быть равны нулю. Тот же результат можно получить, заменив i = 1 во второе уравнение следующим образом: a + b + c + e + f + h + j = 0 . Это эквивалентно a = 0 , b = 0 , c = 0 , e = 0 , f = 0 , h = 0 , j = 0 .
3. Рисунок 3 получен после шагов 1 и 2. Серые ячейки со знаком «–» — это переменные со значением 0 . Ячейка с символом Δ соответствует переменной со значением 1 . Переменная k является единственным соседом самой левой ячейки подсказки со значением 2 . У этой ячейки подсказки есть один сосед с объектом и только одна оставшаяся ячейка с переменной k . Следовательно, k должно быть равно 1 .
4. Аналогично, переменная m тоже должна быть равна 1 , потому что это единственная оставшаяся переменная, соседняя с самой правой ячейкой подсказки со значением 2 .
5. Поскольку k = 1 , m = 1 и i = 1 , мы завершаем маркировку трех скрытых объектов, поэтому d = 0 и g = 0 . Окончательное решение представлено на рисунке 4.

Рисунок 2: Двоичные переменные отмечены

Рисунок 3. Пример частично решен.

Рисунок 4: Пример решен

Использование уникальности

В приведенном выше примере (рис. 2) переменные a , b , c и e являются соседями ключевой ячейки 1 и не являются соседями какой-либо другой ячейки. Очевидно, что возможны следующие решения:

• а = 1 , б = 0 , с = 0 , е = 0
• а знак равно 0 , б знак равно 1 , с знак равно 0 , е знак равно 0
• а знак равно 0 , б знак равно 0 , с знак равно 1 , е знак равно 0
• а знак равно 0 , б знак равно 0 , с знак равно 0 , е знак равно 1

Однако, если головоломка составлена ​​так, что у нас должно быть только одно (уникальное) решение, мы можем установить, что все эти переменные a , b , c и e должны быть равны 0. В противном случае решений станет более одного.

Использование разделения

Рисунок 5: Пример разделения

Некоторые конфигурации головоломок могут позволить игроку использовать разделение. для снижения сложности. Пример приведен на рисунке 5. Каждому разделу соответствует определенное количество скрытых объектов. Сумма спрятанных предметов в перегородках должна быть равна общему количеству спрятанных на доске предметов. Одним из возможных способов определения разделения является выбор ведущих ячеек-подсказок, которые не имеют общих соседей. Ячейки за пределами красных прозрачных зон на рисунке 5 должны быть пустыми. Другими словами, в полностью белых клетках нет скрытых объектов. Поскольку в верхней зоне раздела должен быть скрытый объект, третья строка сверху не должна содержать скрытый объект. Это приводит к тому, что две ячейки переменных в нижнем ряду вокруг ячейки подсказки должны иметь скрытые объекты. В остальном решение простое.

Использование метода проб и проверок.

Рисунок 6: Пример пробного метода

В некоторых случаях игрок может установить переменную ячейку как 1 и проверить, нет ли каких-либо несоответствий. Пример на рисунке 6 демонстрирует проверку несоответствия. Ячейка, отмеченная скрытым предметом Δ, находится под тестом. Его маркировка приводит к установке всех переменных (серых ячеек) в 0 . Отсюда следует несоответствие. Ячейка подсказки, отмеченная красным со значением 1 , не имеет оставшихся соседей, которые могли бы включать в себя скрытый объект. Следовательно, проверяемая ячейка не должна содержать скрытый объект. В алгебраической форме имеем два уравнения:

а + б + в + г = 1

а + б + в + г + е + ж + г = 1

Здесь a , b , c и d соответствуют четырем верхним серым ячейкам на рисунке 6. Ячейка с Δ представлена ​​переменной f , а две другие серые ячейки отмечены как e и g . Если мы установим f = 1 , то a = 0 , b = 0 , c = 0 , d = 0 , e = 0 , g = 0 . В первом уравнении выше левая часть будет равна 0, а правая часть — 1 . Противоречие.

Для решения некоторых головоломок, возможно, придется последовательно применять метод проб и проверок, чтобы прийти к какому-то выводу. Это эквивалентно алгоритму двоичного поиска. исключить возможные пути, ведущие к несогласованности.

Сложность

Из-за двоичных переменных система уравнений для решения не обладает свойством линейности. Другими словами, ранг матрицы уравнения не всегда может соответствовать нужной сложности.

Сложность этого класса головоломок можно регулировать несколькими способами. Один из самых простых методов — установить соотношение количества ячеек с подсказками к общему количеству ячеек на доске. Однако это может привести к значительному изменению диапазона сложности для фиксированного соотношения. Другой метод — шаг за шагом уменьшать ячейки подсказок на основе некоторых стратегий решения проблем. Сложные стратегии могут быть включены для высоких уровней сложности, таких как вычитание одного уравнения из другого или более высокая глубина шагов пробы и проверки. С увеличением размера платы увеличивается диапазон проблемных случаев. На сложность головоломки влияет и соотношение количества спрятанных предметов к общему количеству ячеек.

Ссылки

• Пол Халмос , Наивная теория множеств . Принстон, Нью-Джерси: Компания Д. Ван Ностранда, 1960. Перепечатано Springer-Verlag, Нью-Йорк, 1974. ISBN   0-387-90092-6 (издание Springer-Verlag).
• Александр Шрийвер , Теория линейного и целочисленного программирования . John Wiley & Sons, 1986. Перепечатано в 1999 году. ISBN   0-471-98232-6 .
• Адам Дроздек, Структуры данных и алгоритмы в C++ , Brooks/Cole, второе издание, 2000. ISBN   0-534-37597-9 .