Why can't I reach every cell in a 3x3 square?

[musicgold]

Hi,

I was playing this game in which you start from any cells of a 3x3 or 5x5 square and draw a line that loops through every cell in the box. The line can go only through a vertical or horizontal side (not diagonally). When you start from certain cells (problem cells), you can't reach at least one cell. In the attached file, I have shown such paths. The cells that can't be reached are shown with a question mark.

I am trying to find out how to express mathematically a.) why a particular cell can't reach every cell in a box, and 2) how many problem cells will be in a nxn matrix, where n is an odd number.

This is what I have noticed so far:
1. With even numbered squares such as 2x2 and 4x4, have no problem cells.
2. The 3x3 square has 4 problem cells and the 5x5 square has 12 problem cells.
3. Corner cells and the center cell (in the case of 3x3 and 5x5) are never problem cells.
4. The problem situation occurs when the line enters a T junction with empty cells on either sides.

How should I approach this problem?

Thanks.

 

[bigfooted]

Don't know too much about this, but I think what you are asking for is if there is a Hamiltonian path for any starting position on a grid, or for which starting positions there are no Hamiltonian paths:

https://en.wikipedia.org/wiki/Hamiltonian_path
and it is difficult:
https://en.wikipedia.org/wiki/Hamiltonian_path_problem

 

[mathman]

Attached Files

When I click on it. a new page opens up - blank!

 

[mfb]

and it is difficult

In this special case: It always works if at least one of the side lengths is even because they have a Hamilton cycle and you can just follow that no matter where you start. Otherwise there are some starting positions that don't work.

 

[musicgold]

When I click on it. a new page opens up - blank!

That means it downloads the file in the default download folder of your browser.

 

[musicgold]

I have done some more progress on this problem.
5. If I name each cell of the box using the Row x column convention, I can see a pattern. The top left cell is named as (1,1) , the next cell on the right as (1,2) , the first cell in the second row as (2,1) and so on. The cells whose row and column numbers add to an odd number are problem cells.

6. Based on that, I think, in a NxN square, where N is an odd number, there will be
$(N^2 -1 )/2$. I am not sure how to prove this though.

 

[FactChecker]

You are showing particular paths that can not be completed. But it's not clear to me that there are any such problem and starting point where there is no solution even if one is free to pick the right path. Do you have an example like that?

EDIT: I take it back. I do not see any solution to your 3x3 example. I think I have trouble with all of the odd x odd examples.

 

[Tom.G]

An awful lot like:
https://en.wikipedia.org/wiki/Seven_Bridges_of_Königsberg

 

[mfb]

I have done some more progress on this problem.
5. If I name each cell of the box using the Row x column convention, I can see a pattern. The top left cell is named as (1,1) , the next cell on the right as (1,2) , the first cell in the second row as (2,1) and so on. The cells whose row and column numbers add to an odd number are problem cells.

6. Based on that, I think, in a NxN square, where N is an odd number, there will be
$(N^2 -1 )/2$. I am not sure how to prove this though.

Color the field with a checkerboard pattern. Every connection goes from black to white or vice versa. Now consider how many fields of each color there are.