4
$\begingroup$

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.

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
9
$\begingroup$

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/

Improve this answer
$\endgroup$
10
  • $\begingroup$ I don't want to solve it, I want to be able to tell if it can be solved or not. $\endgroup$
    – warspyking
    Commented Dec 12, 2014 at 2:47
  • $\begingroup$ Sorry, you are right, I have edited the answer to reflect that more clearly. My answer is still the same though. $\endgroup$
    – McMagister
    Commented Dec 12, 2014 at 2:51
  • 2
    $\begingroup$ If a square is connected to only one other square, it must either be the first or last square visited, since you can't backtrack. Hence, any shape with more than 2 such squares (like the T shape) has no solution. $\endgroup$
    – McMagister
    Commented Dec 12, 2014 at 10:54
  • 1
    $\begingroup$ I tried to edit "inverse" to "converse" but apparently edits must be at least 6 chars $\endgroup$
    – Sp3000
    Commented Dec 12, 2014 at 15:23
  • 2
    $\begingroup$ Another heuristic: 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. $\endgroup$
    – Lopsy
    Commented Dec 12, 2014 at 22:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.