Sort an array.

Question

I can’t come up with an algorithm. The right element should be equal to the left of the next.
Input: {0,0}, {0,3}, {1,6}, {2,1}, {3,2}, {3,6}, {6,0}.
Output: {3,6}, {6,0}, {0,0}, {0,3}, {3,2}, {2,1}, {1,6}.

Answer 1

Hello Chowa

Looks like domino stones. ;)

I would say you will need a bracktracking algorithm.

You start with a stone and try to add another stone. Until you find a solution.

If you can't find a stone, you remove the last stone. And try another one.

If you have to remove the first stone, but it's also your last stone -> no solution

Example:

{0,0} {0,3} {3,2} {2,1} {1,6} {6,0}

remove {6,0}, {1,6}, {2,1}, {3,2}

{0,0} {0,3} {3,6} {6,0}

remove all stones, start with another one.

{0,3} {3,2} {2,1} {1,6} {6,0} {0,0}

remove all stones until {0,3}

{0,3} {3,6} {6,0} {0,0}

remove all stones

{1,6} {6,0} {0,0} {0,3} {3,2} {2,1}

remove {2,1} and {3,2}

{1,6} {6,0} {0,0} {0,3} {3,6}

remove all stones until {6,0}

{1,6} {6,0} {0,3} {3,2} {2,1}

and so on...until you start with {3,6} then you will find the solution.

Answer 2

And of course you can improve it:

For example a stone start with a number which does not fit: This stone has to be the first stone.

End if a stone ends with a number which does not fit: This stone has to be the last stone.

About backtracking:

https://www.google.de/amp/s/www.freecodecamp.org/news/backtracking-algorithms-recursive-search/amp/

Answer 3

Many thanks!