Alright, here's a new one for you guys. Instead of solving it, you need to determine if any given configuration is possible to solve, without actually solving it. It needs to be a general method of figuring it out, and should apply to most (if not all) situations.
Without further ado, here's the puzzle you have to use:
Imagine a square grid of arbitrary size. Now picture a T-shape drawn on it; the T is 3 blocks wide and 5 blocks tall as seen in the image below left.
Now picture starting on the top left, and staying within the T shape/boundaries, slowly progressing, filling each square as you go. Can you fill in all the squares of the grid? Of course not! The most you can do us fill 6 squares!
However if the shape itself was a square (like the shape below right), you can fill the entire shape.
How to move: Move to any orthogonally adjacent square which you have not already visited in the shape.
Note: For all situations you may assume to start in the upper left corner. Accepted answer goes to the simplest method.
Answer
What you seem to be asking (assuming the squares are completely filled), is to find an Hamiltonian path on a connected subset of the square grid graph.
Defintions (lifted from Wikipedia)
A Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once.
A square grid graph is the graph whose vertices correspond to the points in the plane with integer coordinates, x-coordinates being in the range 1,..., n, y-coordinates being in the range 1,..., m, and two vertices are connected by an edge whenever the corresponding points are at distance 1.
As far as I can tell, the answer is that the Hamiltonian path problem is an NP-complete problem, which means that there is no polynomial time algorithm to determine if an arbitrary graph contains a Hamiltonian path. In other words, given a large enough shape, it might take nearly forever just to find out if there is a solution to the stated problem.
A simple heuristic can determine if there is no solution: If a square is connected to only one other square (i.e. it has a degree of 1), it must either be the first or last square visited, since you can't backtrack. Hence, any shape with more than 2 such squares (marked with "1" in the image below) has no solution.
However, the converse is not true. The shape below right has 2 squares with degree 1, but is unsolvable as well.
Another heuristic (courtesy of Lopsy): color the squares like a checkerboard. The number of white and black squares can only differ by 1 if it is solvable. If e.g. there is one more white square than black, then the path must start and end on white.
In this case the T shape satisfies the heuristic while the shape on the right does not. Both are not solvable which again shows that the converse is false.
You can also simplify shapes by removing a vertex of degree 1 if and only if it is connected to a vertex of degree 2. For example, the following shapes are equivalent in terms of their solvability:
Lets put what we have learned to use. Here is a complex shape which satisfies both heuristics (only 1 vertex of degree 1, and there are 7 black squares vs 6 light squares). But we can remove the vertex with degree 1 because it is connected to a vertex of degree 2, and now the new shape does not satisfy the checkerboard heuristic anymore. So, the shape has no hamiltonian path.
This is really a question more for math or computer science:
https://cstheory.stackexchange.com/questions/tagged/hamiltonian-paths
https://mathoverflow.net/questions/tagged/hamiltonian-paths
This may also be of interest (algorithms for finding Hamiltonian paths for L, C, F, and E shaped graphs on a grid): http://www.hindawi.com/journals/jam/2012/475087/
No comments:
Post a Comment