2
$\begingroup$

Let say that we have four straight string with colors RED, GREEN, BLUE and YELLOW. These strings are tied up randomly. We know the current state of string (like starting point, where we should we start untying from) and the final state (where current string must look like after untying them).

Here is a very simple example of the problem:

a sample of the puzzle

At every move, we are allowed to replace only two nearby strings. For example, to solve the shown problem, we should do the following replacements:

1) Replace GREEN and YELLOW

2) Replace BLUE and GREEN

But in a programming environment, how can I calculate the movements to untie the strings? What will be the algorithm specifically to solve such type of problems? Here is another variation of the question. Its not possible to solve this problem according to the answer.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

Sequential programming would not be suitable for this kind of problem, but an algorithm could be implemented in a declarative programming language. I would suggest using Answer Set Programming, a language that is designed for logic axioms.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I took the liberty of adding links. Please don't hesitate to correct if I've gotten anything wrong. (Thanks for this answer--"short and sweet" but but useful!) $\endgroup$
    – DukeZhou
    Commented May 18, 2018 at 17:09
0
$\begingroup$

I sounds to me like something that could be expressed as a planning problem. You have a start state, end end state, and a set of actions. You need to find the correct actiona sequence to get from the start to the goal.

You could probably express this in PDDL and use a planner to find the right steps.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .