Thread: Pathing algorythem

I have been set a problem and do not know how to solve it, basically it is this.

I am given a 6 by 7 board with a total of 42 squares on it. Each of those squares has a line on it the line is either straight from one side to the other, t from one side to the other with one branch off or x all sides are connected to their opposite. There is a start point placed and 3 end points at random. Also randomly placed in spots that do not affect the solubility of the puzzle are barriers or pieces that cannot move cannot rotate and cannot continue a line. All other pieces with the exception of start and end points can be switched with another piece and or rotated. The object and my task is to build a program that will both connect the start point to the end point (there is no limitation on how they are connected or in which order they are connected however the start and end pieces must be touching a line on a random side and no other). Additionally as a secondary assignment we are tasked with completing the board to its fullest extent and completing the puzzle. Is there currently an algorithm out that can be used for this, i have looked into mapping and pathing algorithms but i do not think they can be adapted into this puzzle given that the pieces can move and change and there is no static map to which the algorithms can be applied.

Well you could start with a simple depth-first pathfinding algorithm so you can see which squares you need to take to get to the end points. After that you would have to come up with your own solution for which pieces go where depending on your previously determined path.

Seems like a decent approach to it without getting too involved or giving out too much information. Perhaps someone else has a better suggestion