Friday, August 31, 2018

mathematics - Check to see if a Configuration is Possible: prove there's an Hamiltonian path on a connected subset of the square grid graph




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.


T and square shapes on a grid


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.


vertex degrees added




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.


checkerboard




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:


equivalent T shapes





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.


Complex shape




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

classical mechanics - Moment of a force about a given axis (Torque) - Scalar or vectorial?

I am studying Statics and saw that: The moment of a force about a given axis (or Torque) is defined by the equation: $M_X = (\vec r \times \...