Note : I have been working on this since beginning of the original question, that is, almost 3 weeks :)
I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post herean answer.
Here is the file with all solutions, in case somebody wants to verify results without generating them (itIt took approx 7 hours on my machine)to generate results. Here is a txt file with all solutions, in case someone want to check them : Click hereresults.zip
It use A* PathfindingA* Pathfinding algorithm.
All the difficulty reside in findingWhat is difficult is to find a good heuristic. If the heuristic it understimateunderestimate the cost, it will perform like almost like a brute force approachDijkstra algorithm and because of complexity of a 19x19 board with 6 colors it will run forever. If it overestimate the cost it will converge quickly to a solution but won't give good ones at all (something like 26 moves were 19 was possible). Finding the perfect heuristic that give the exact remaining amount of steps to reach solution would be perfectthe best (it would be fast and would give best possible solution). It is (unless i'm wrong) impossible. It will actually require to solve the board itself first, while this is what you are actually trying to do (chicken and egg problem)
I build a
graphgraph of current board to evaluate. Eachnoderepresent a set of contiguous, same colored squares. Using thatgraph, I can easily calculate the exact minimal distance from center to any other node. For example distance from center to top left would be 10, because at minimum 10 colors separate them.For calculating
heuristic: I simulate playingplay the current board until the end. For each step, I choose the color which will minimize the sum of distances from root to all each nodeother nodes.Number of moves needed to reach that end is value of the
heuristic.Estimated cost (used by A*)(used by A*) =moves so far+heuristic
It is not perfect as it sligtlyslightly overestimate the cost (thus non optimal solution is found). Anyway it is fast to calculate and give good results.
I was able to get huge speed improvment by using graph only to perform all operations. At begining I had a 2-dimension2-dimension array. I flood it and recalculate graph when needed (eg : to calculate the heuristic). Now everything is done using the graph, which calculated only at the beginning. To simulate steps, flood fill is no more needed, I merge nodes instead. This is a lot faster.
Note : I have been working on this since beginning of the original question, that is, almost 3 weeks :)
I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post here.
Here is the file with all solutions, in case somebody wants to verify results without generating them (it took approx 7 hours on my machine) : Click here
It use A* Pathfinding algorithm.
All the difficulty reside in finding a good heuristic. If the heuristic it understimate the cost, it will perform like almost like a brute force approach and because of complexity of a 19x19 board with 6 colors it will run forever. If it overestimate the cost it will converge quickly to a solution but won't give good ones at all (something like 26 moves were 19 was possible). Finding the perfect heuristic that give the exact remaining amount of steps to reach solution would be perfect. It is (unless i'm wrong) impossible. It will actually require to solve the board itself first, while this is what you are actually trying to do (chicken and egg problem)
I build a
graphof current board to evaluate. Eachnoderepresent a set of contiguous, same colored squares. Using thatgraph, I can easily calculate the exact minimal distance from center to any other node. For example distance from center to top left would be 10, because at minimum 10 colors separate them.For calculating
heuristic: I simulate playing the current board until the end. For each step, I choose the color which will minimize the sum of distances from root to all each node.Number of moves needed to reach that end is value of the
heuristic.Estimated cost (used by A*)=moves so far+heuristic
It is not perfect as it sligtly overestimate the cost (thus non optimal solution is found). Anyway it is fast to calculate and give good results.
I was able to get huge speed improvment by using graph only to perform all operations. At begining I had a 2-dimension array. I flood it and recalculate graph when needed (eg : to calculate the heuristic). Now everything is done using the graph, which calculated only at the beginning. To simulate steps, flood fill is no more needed, I merge nodes instead. This is a lot faster.
I try many things, most of them fail and just didn't work at all, until recently. I got something interesting enough to post an answer.
It took approx 7 hours to generate results. Here is a txt file with all solutions, in case someone want to check them : results.zip
It use A* Pathfinding algorithm.
What is difficult is to find a good heuristic. If the heuristic it underestimate the cost, it will perform like almost like Dijkstra algorithm and because of complexity of a 19x19 board with 6 colors it will run forever. If it overestimate the cost it will converge quickly to a solution but won't give good ones at all (something like 26 moves were 19 was possible). Finding the perfect heuristic that give the exact remaining amount of steps to reach solution would be the best (it would be fast and would give best possible solution). It is (unless i'm wrong) impossible. It actually require to solve the board itself first, while this is what you are actually trying to do (chicken and egg problem)
I build a graph of current board to evaluate. Each
noderepresent a set of contiguous, same colored squares. Using thatgraph, I can easily calculate the exact minimal distance from center to any other node. For example distance from center to top left would be 10, because at minimum 10 colors separate them.For calculating
heuristic: I play the current board until the end. For each step, I choose the color which will minimize the sum of distances from root to all other nodes.Number of moves needed to reach that end is the
heuristic.Estimated cost(used by A*) =moves so far+heuristic
It is not perfect as it slightly overestimate the cost (thus non optimal solution is found). Anyway it is fast to calculate and give good results.
I was able to get huge speed improvment by using graph to perform all operations. At begining I had a 2-dimension array. I flood it and recalculate graph when needed (eg : to calculate the heuristic). Now everything is done using the graph, which calculated only at the beginning. To simulate steps, flood fill is no more needed, I merge nodes instead. This is a lot faster.
More details about how it works :
It use A* Pathfinding algorithm.
More details about how it works :
It use A* Pathfinding algorithm.