I am trying to find an algorithm for finding an optimal solution to a puzzle of a given format. The 7 by 6 puzzle board is made out of the following pieces:
Tears and grommets can be rotated and moved around the board, but spools, tie-offs and blockers cannot.
A simple example of the puzzle in it's starting state is:
While a more complicated version and a possible solution is:
The puzzle is scored by how many pieces are used in the solution (more is better) and how quickly the puzzle is solved.
I have so far written functions to detect and read in the board, as well as a function to check that the board is valid.
In order to solve the board, I have so far tried a brute force method, which randomly shuffled and rotated the movable pieces in the puzzle and then checked if the result was a valid solution, but this was fairly slow even for the simple boards, and extremely slow for more complex boards, and of course, did not come up with an optimal solution.
I then refined it a bit by excluding obvious wrong piece placements, but this was still over a second for small boards, and anywhere from 5 to 30 seconds for larger boards, and was also not an optimal solution.
I have heard about possibly using various path finding algorithms such as Djikstra's or A* but I'm struggling to see how these algorithms can be used to find the longest valid path, especially when branching pieces such as the 'T' and '+' pieces come into play.
Any help would be much appreciated!