Есть ли универсальный алгоритм для задач 'Можно ли переложить 1 спичку, чтобы равенство стало верным'?

Question

[kolomiec_artiom]

Добрый вечер. Стоит задача:

Дано выражение. К примеру: 9 = 6 (из спичек)
Можно ли переложив одну списку получить верное выражение?

Как это сделать программно?

Comments

[Даша Циклаури]

это NP-полная задача

[jcmvbkbc]

это NP-полная задача

Даша Циклаури, вопрос был не "какова сложность", а "как это сделать программно".

[Ксения]

jcmvbkbc, очень не уверена, но возможно стоит посмотреть в сторону логического программирования. Или ещё что-то такое хитрое применить

[Ксения]

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

[Даша Циклаури]

Ксения, ну как вариант свести к графу, где вершины - валидные комбинации, а ребра - множество морфизмов для каждой спички, но тогда задача сведется к построению графа :D

Answer 1

[jcmvbkbc]

Как это сделать программно?

Найти все возможные положения в которые можно положить спичку. Найти все допустимые фигуры из спичек. Вывести значение каждой допустимой фигуры и каждой комбинации допустимых фигур. Пройти по всем спичкам, каждую спичку переложить во все возможные положения, проверить, допустимы ли все образовавшиеся фигуры и их комбинация и вычислить значение получившегося выражения. Звучит просто, не правда ли?

Comments

[Ксения]

Мне кажется, это слишком в лоб. Можно создать некие эмпирические правила или же создать таблицу переходов, в которой будет указано, что, допустим, из 9 перейти в 1 будет стоить три спички, в 2 - две спички и т.д. Не особо-то много вариантов. А потом смотреть только те ячейки, которые для условия задачи подходят. Допустим, цена перехода "2" - смотрим варианты.
Единственная непонятка, эти числа - лежат в зоне досягаемости друг друга или нет? Можно ли их соединять спичками и т.д. При необходимости, добавить двузначные числа со стоимостью перехода к ним не более 2/3/../n.

[jcmvbkbc]

Мне кажется, это слишком в лоб.

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