Easy Chess
Time limit2sMemory limit512 MB
Find a path of exactly n rook moves on an 8x8 board from a1 to h8 that visits n+1 distinct cells.
- Level
Medium4 of 10
- Topics
- Implementation, Brute force, Simulation, Greedy
- Solved
- No attempts yet
Problem
Elma is learning chess pieces.
She learned that a rook can move either horizontally or vertically. To help her understand rook movement, Elma's grandmother gave her an 8 × 8 chess board and asked her to find a way to move the rook from a1 to h8 in exactly n moves so that all visited cells are different.
A visited cell is the starting cell a1 and each cell the rook lands on after a move.
Input
The input contains a single integer n (2 ≤ n ≤ 63), the desired number of moves.
Output
Output a space-separated list of the n+1 visited cells in the order the rook visits them. All cells must be different. The list must start with a1 and end with h8. A solution always exists.