Is there a Hamiltonian circuit on a chess board with a lame rook, with equal # of horizontal and vertical steps?

Question

You have a 8x8 chessboard, and a "lame rook" that can only move 1 square at a time, horizontally and vertically only. Starting in a corner (or anywhere, really), can the piece make a circuit, visiting every square only once, other than returning to where it started. So it needs 32 horizontal movers, and 32 vertical.

I suspect the answer is no, but I can't prove it. I can prove it can't be done on a 4x4 board. I know it can be done on 6x6 and a friend says he found such a path for 10x10.An answer for 8x8 would be nice. A general answer about what sizes can and can't be done would be superb.

atsuo · Answer

*** Edited ***

I prove that 8×8 board does not have the solution.

Let "Hamiltonian circuit" be "HC".
┏━┳━┳━┳━┳━┳━┳━┳━┓
┃こ╂け┃ヽ┃ヽ┃ヽ┃ヽ┃く╂き┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃さ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃か┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
┃し┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃お┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃あ╂い┃ヽ┃ヽ┃ヽ┃ヽ┃う╂え┃
┗━┻━┻━┻━┻━┻━┻━┻━┛
HC passes through 4 corner squares あ,え,き,こ, so it contains 8 moves shown in the above diagram. If HC be a directed circuit then it is あ→い→う→え→お→か→き→く→け→こ→さ→し→あ or its reversed sequence, and other sequences can not become a directed HC. For example, if あ→い→お→え→う→... then this directed path is disturbed by the path い→お and can not arrive at か from う.
Next, think an undirected temporary circuit on the board.
┏━┳━┳━┳━┳━┳━┳━┳━┓
┃こ╂け╂ヽ╂ヽ╂ヽ╂ヽ╂く╂き┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃さ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃か┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃し┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃お┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃あ╂い╂ヽ╂ヽ╂ヽ╂ヽ╂う╂え┃
┗━┻━┻━┻━┻━┻━┻━┻━┛
This circuit contains the same number of vertical and horizontal moves. To modify this circuit to HC, we must add moves for inner 36 squares. There are 2 procedures P1 and P2.
P1 : Add 2 horizontally adjacent squares (horizontal domino) to the circuit. The number of vertical moves are increased by 2.
P2 : Add 2 vertically adjacent squares (vertical domino) to the circuit. The number of horizontal moves are increased by 2.
We can do P1 and P2 in any sequence. For example, add a horizontal domino すせ and a vertical domino たそ to this circuit.
┏━┳━┳━┳━┳━┳━┳━┳━┓
┃こ╂け╂ヽ╂ヽ╂ヽ╂ヽ╂く╂き┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃さ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃か┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃た╂ヽ┃
┣┿╋━╋━╋━╋━╋━╋┿╋━┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃そ╂ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃ヽ┃
┣┿╋━╋━╋━╋━╋━╋━╋┿┫
┃し┃ヽ┃す╂せ┃ヽ┃ヽ┃ヽ┃お┃
┣┿╋━╋┿╋┿╋━╋━╋━╋┿┫
┃あ╂い╂ヽ┃ヽ╂ヽ╂ヽ╂う╂え┃
┗━┻━┻━┻━┻━┻━┻━┻━┛
2 squares are added to the circuit by 1 procedure, so if we can do 9 P1s and 9 P2s then HC has the same number of vertical and horizontal moves, it becomes the solution. If so then 6×6 squares must be divided into 9 vertical dominos and 9 horizontal dominos. Name 36 squares as followings.
┏━┳━┳━┳━┳━┳━┓
┃ち┃つ┃ち┃つ┃ち┃つ┃
┣━╋━╋━╋━╋━╋━┫
┃て┃と┃て┃と┃て┃と┃
┣━╋━╋━╋━╋━╋━┫
┃ち┃つ┃ち┃つ┃ち┃つ┃
┣━╋━╋━╋━╋━╋━┫
┃て┃と┃て┃と┃て┃と┃
┣━╋━╋━╋━╋━╋━┫
┃ち┃つ┃ち┃つ┃ち┃つ┃
┣━╋━╋━╋━╋━╋━┫
┃て┃と┃て┃と┃て┃と┃
┗━┻━┻━┻━┻━┻━┛
1 vertical domino covers ち+て (type1) or つ+と (type2).
1 horizontal domino covers ち+つ (type3) or て+と (type4).
If k type1 dominos exist then 9-k type2 dominos exist. They cover 9 ち and 9-k つ, so 9-k ち and k つ must be covered by type3 dominos. But 9 is an odd number so 9-k and k are not equal. Therefore, 8×8 board has no solution.

For (4n)×(4n) board, there are (4n-2)(4n-2) = 16n^2-16n+4 inner squares. So the number of each of ち,つ,て,と is 4n^2-4n+1. It is an odd number, so (4n)×(4n) board has no solution.

↓ Former answer ↓

I prove that (4n+2)×(4n+2) boards have solutions for n = 0,1,2, ...
To simplify, I show the proof when n = 2. For other n, the proof is similar.

Step1. divide the board into four square sub-boards of the same size.

あああああいいいいい
あああああいいいいい
あああああいいいいい
あああああいいいいい
あああああいいいいい
うううううえええええ
うううううえええええ
うううううえええええ
うううううえええええ
うううううえええええ

Step2. Think a Hamiltonian path on upper-right sub-board, between top-left corner and bottom-right corner. Any path can be used. For example,

あああああ・┏━━┓
あああああ┃┃┏┓┃
あああああ┃┃┃┃┃
あああああ┃┗┛┃┃
あああああ┗━━┛・
うううううえええええ
うううううえええええ
うううううえええええ
うううううえええええ
うううううえええええ

Step3. Think other Hamiltonian paths on other sub-boards using 90° rotation.

┏━━━・・┏━━┓
┃┏━━┓┃┃┏┓┃
┃┗━┓┃┃┃┃┃┃
┗━━┛┃┃┗┛┃┃
・━━━┛┗━━┛・
・┏━━┓┏━━━・
┃┃┏┓┃┃┏━━┓
┃┃┃┃┃┃┗━┓┃
┃┗┛┃┃┗━━┛┃
┗━━┛・・━━━┛

Step4. Connect 4 Hamiltonian paths by 4 moves.

Then we can find a Hamiltonian circuit with the same number of horizontal moves and vertical moves. (Figure is omitted)

Samwise · Answer

There must be something missing in your description of the constraints. 
 
I base that on your claim you can prove it's impossible on a 4x4 board. 
What's invalid about this sequence? 
from a1: a2, a3, a4, b4, b3, b2, c2, c3, c4, d4, d3, d2, d1, c1, b1, a1 
 
It moves to each square once, with the 16th move returning to its starting square. 
If that's valid, a similar approach should work for any rectangular board with an even number of squares on each side.

Trending News

Is there a Hamiltonian circuit on a chess board with a lame rook, with equal # of horizontal and vertical steps?

2 Answers