I have a final set of tiles in which every edge can have on of four colors.
The task is to find a maximal possible square build from a given set (finite) of this tiles. Tiles can be rotated.
I need to design 3 algorithms for finding a solution for this task. One complete and two aproximations.
Obviously it is my task for Algorithms class so Im not asking about complete solutions (as this would be unfair) but for some directions.
Im already designed a kind of complete algorithm (using backtracking - search for a square of size sqrt(n) - if it could not be found try finding smaller and so on) but I have no idea how to create aproximation algorithms.
I think one will be kind of stupid which will find a good answer only in specific cases just to document that it is not a good aproach but still I need one much faster then backtracking and quite good one.
Also is this problem NP-hard one? My backtracking algorithm is exponential one but it doesnt mean that there cannot be a better one...
EDIT: I have complete algorithm with exponential time, could some one give me some hints how to build some kind of aproximation for this problem with polynomial time or something better then exponential?
EDIT2: I have the idea that this problem can be changed to a problem of reducting a graph to square grid graph ( http://mathworld.wolfram.com/GridGraph.html ). Still there is a problem if the tiles can be arranged in such a way to build a grid, but this could be a good point to start. Are there any, for example, greedy or any other aproximation algorithms for reducting graph to square-grid graph?
Suppose your backtracking algorithm constructs k-by-k squares for increasing values of k. You can extend the backtracking algorithm with heuristics. So instead of choosing the next tile randomly, choose and attach a tile such that the colors of the free tiles "agree with" those on the square. The big problem is to find the "agreement" heuristics. One possible heuristics is to find the least common color on the free tiles and use it.