Предположим, вы построили систему уравнений и решили их наилучшим образом, но некоторые строки оказались со всеми нулями в левой части уравнения (я представляю уравнения в виде расширенной матрицы)
Предположим, вы пытались решить систему в кольце Z2 (что в практическом плане для этого конкретного примера означает, что единственное изменение - это то, что 1 + 1 = 0, в противном случае все остается прежним ... поэтому единственный оператор, который нам нужен, это XOR) и получил следующую матрицу:
1001 1
0100 1
0011 0
0000 0
Как вы можете видеть в этом примере, все 4-й ряд равен 0, что означает, что у нас нет ответа на него. Однако подумайте об этом следующим образом: строка всех 0 означает, что эта переменная не влияет на решение. Это на самом деле плохой выбор слов ... это просто означает, что они могут иметь любое значение (и здесь нам повезло, поскольку все значения означают 1 или 0, в отличие от действительных чисел ... Так что это означает, что у нас есть 2 решения для этой системы).
И вот почему: на данный момент вам нужно знать, что самый правый столбец все еще содержит правильное решение для вашей игры. Давайте возьмем первую строку для примера. Это говорит о том, что
button_0 + button_3 = 1
но мы знаем, что кнопка 3 может быть чем угодно (поскольку в строке 3 все 0). На данный момент кнопка 3 имеет значение 0 (самый правый столбец в строке 3 на этом этапе равен 0), поэтому теперь мы знаем, что это означает
button_0 + 0 = 1
поэтому мы точно знаем, что button_0 равен 1. Поэтому в этой системе, хотя мы не могли напрямую определить button_3, у нас все еще есть правильное решение.
Сгенерированной выше матрицы достаточно для проверки разрешимости. Если строка содержит все 0, то по сути это означает, что
nothing = nothing
или, чтобы лучше представить себе, почему это работает,
0x = 0
что имеет смысл, система все еще действует. Однако, если мы встречаем строку со всеми 0 с , за исключением самого правого бита, то есть
0000 1
что бы сказать
0x = 1
, что невозможно, поэтому мы теперь знаем, что система не может быть решена, поскольку мы не можем решить невозможную ситуацию, подобную этой.
Поэтому, в двух словах, попытайтесь решить уравнение как можно лучше, не беспокойтесь, если вы не можете точно выяснить, каковы некоторые из переменных, если вы в любой момент не можете встретить невозможное Строка, которую я только что упомянул, тогда игра разрешима.
Но что, если мы хотим, чтобы самое короткое решение для системы? Здесь мы должны рассмотреть все возможные решения. У нас есть кнопка_3, которая может иметь любое значение, поэтому это означает, что любая 1 в столбце 3 означает, что на строку, в которой она найдена, действует кнопка_3. Итак, предположим, что мы хотим проверить, будет ли решение, использующее button_3, короче. Мы создаем другую матрицу, но теперь устанавливаем для button_3 значение 1 (поскольку ранее мы установили, что это может быть что угодно, и у нас там уже было 0, поэтому теперь мы проверяем 1). Теперь мы получаем следующую матрицу:
1001 1
0100 1
0011 0
0001 1
Мы сократили это до максимума и теперь получаем следующую матрицу:
1000 0
0100 1
0010 1
0001 1
Это все еще верное решение, однако мы можем видеть, что решение длиннее (требуется 3, а не 2 нажатия кнопок), поэтому мы отказываемся от него. Мы должны сделать это для каждой перестановки установки строк, которые мы нашли как все 0s к 1. Поэтому, если у нас есть x строк, которые были всеми 0, то у системы есть x ^ 2 решения, и мы должны проверить все из них.