COMCB - Complete Chess Boards

no tags 

BuggyD has always been fascinated with chess boards (though he really sucks at chess). He makes an observation that a chess board is complete with respect to knights and rooks and incomplete with respect to bishops (unless the dimensions are 1 × 1). A complete chess board is one in which it is possible to traverse all the squares starting from one possible square. Knights have always been his favourite pieces and he has decided to analyze completeness with respect to knights. Given the dimesions of the chess board help BuggyD find the lexicographically first path that visits all squares of a chess board with a knight.

Each square must be traversed only once. Note that a knight can only move two squares in one direction and one square perpendicular to the previous direction.


The first line of the input contains an integer t, the number of test cases. t test cases follow.

Each test case consists of a single line cotaining two integers (X and Y) separated by a single space, specifying the dimensions of the chess board. The numbers 1 to X denote rows and the capital letters A to Y denote the coloumns. Each square is represented by its column index followed by it's row index - for example, B4 denotes the square in the 4th row and 2nd column.

The total number of squares on the chess board will be no more than 26.


For each test case output one line consisting of the lexicographically first path of the knight, or "-1" (quotes for clarity) if the chess board is incomplete with respect to a knight.


4 5


hide comments
Luv Karakoti: 2014-07-21 22:26:14

I am not able to comprehend the meaning of the phrase 'first lexicographical' path. Can please someone clarify this?
P.S.Are we ordering it in dictionary-wise? Because if we are ordering them as in the dictionary, then a sequence
A1B3C1A2B4C2 shall occur before

Legolas: 2014-01-12 17:19:59

4 5
isn't this a valid sequence and lexicographically smaller
than the output given?

It's wrong, because the input is of the format column*row.
@Mathew Reeder: It would be better if you can make the input in normal form.

Last edit: 2014-01-12 17:29:11
Krunal: 2011-03-04 00:37:56

What if input is given as:
0 0
0 12
12 0
output should be "-1". Judge is not checking that I guess.

Krunal: 2011-03-04 00:18:07

One Help: It is "Lexicographic order"
For example,
(1) 3 4 has possible outputs "A1C2A3B1D2B3C1D3B2D1C3A2" & "A1C2A3B1D2B3C1A2C3D1B2D3"...latter one is the answer. I got two WAs :( , Be careful.
(2) For 4 6 "A1B3C1A2B4C2D4E2F4D3E1F3D2B1A3C4B2A4C3E4F2D1E3F1"

Last edit: 2011-03-04 00:38:48

Added by:Matthew Reeder
Time limit:0.391s
Source limit:30000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:Al-Khawarizm 2006