The below puzzle, logically has no solution, Is it possible to prove that Matamatically?

Question

This image

contains a puzzle

Description of the puzzle:

• A square building has 16 (4 x 4) rooms
• A person is standing on, one corner as per the image
• There is the exit in the opposite cornet of the building

Conditions

1. The person has to travel through all the rooms
2. And there should be only one visit per room

Solution: This puzzle logically doesn't have any solution.

Not only this set, any similar kind of set, whihc has the total number of rooms in even number doesn't has a solution. Like the list,

• 2 x 2 = 4
• 4 x 4 = 16
• 6 x 6 = 36
• 8 x 8 = 64
• etc.

My Findings:

Lets say n = 1, 2, 3,... etc.

For any (2n)^2 set, there is logically no solution possible. This behavior can it be related to any mathematical formula/ logic, etc. ?

Answer 1

Colour the squares black and white in an alternating pattern, like a chess board. There are an equal number of black and white rooms ($8$ each). I'll refer to a visit to any particular room as a "move". Suppose that you start in a black room (that is, the room in the top left is black).

In order to successfully complete the puzzle, you must make 15 "moves", and end up on a black square.

We now reduce the problem only marginally. Suppose that you found a successful solution, and that you could start on a black square, and end on a black square in the opposite corner. Now remove the starting square and start your person on whichever adjacent white square you moved to in that successful solution. Also now remove the final black square in the opposite corner. You have exactly the same puzzle here and your successful solution should still work, you've just removed the first and last moves and respective squares from the game.

Now when you make a move, count this as placing a domino piece on the board. The square that you're on and the square you move to are covered by a $2 \times 1$ domino tile. The square that you subsequently move to and the move after that are covered by another $2 \times 1$ tile, and so on and so fourth. If you had a successful solution to start with, you would successfully tile the board with $2 \times 1$ dominos with this method.

This is a contradiction for the even square grids. Your new board has more white squares than black, and every time you place a domino you cover exactly one black and one white tile. Therefore you didn't have a successful solution in the first place.

Answer 2

There is a short non-inductive proof that the problem has no solution for grids with both sides of even length.

Suppose a solution exists. Then all squares of the solution path except the first and last can be covered with dominoes trivially, by following the path. But by the mutilated chessboard problem, since opposite corners of the chessboard colouring of the grid have the same colour and there are an equal number of squares of both colours, such a domino tiling is not possible – contradiction. Therefore no solution can exist.

If either side is of odd length, then a solution exists and is very easy to find.