/* knight.c: knight's tour of a chess board. */
/* Takes about an hour to find the 8 by 8 circuit. */
/* knight 8 8 - - */

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

static char circuit = 0;
static char leftright = 0;
static char width, height;
static char x0, y0; // starrt position
static char mx[200], my[200]; // knight moves
static int level;
static char board[16][8];

// this is only for the 8 by 8 board
static char range[8][8] = {
{2,3,4,4,4,4,3,2},
{3,4,7,7,7,7,4,3},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{4,6,8,8,8,8,6,4},
{3,4,7,7,7,7,4,3},
{2,3,4,4,4,4,3,2},
};

static void makemove(void)
{
int i, m;
char lx, ly; // last xy position
char nx, ny; // next xy position
static const char jx[8] = {2,1,-1,-2,-2,-1,1,2};
static const char jy[8] = {1,2,2,1,-1,-2,-2,-1};
char cx[8], cy[8];
int choices, c1;

if(level == width * height - 1) {
for(i=0; i<=level; ++i)
printf("%c%d ", "abcdefghijklmnop"[mx[i]], my[i]+1);
printf("\n");
exit(0);
return;
}

lx = mx[level], ly = my[level];
choices = 0, c1 = -1;
for(m=0; m<8; ++m) {
nx = lx + jx[m];
ny = ly + jy[m];
if(nx < 0 || nx >= width || ny < 0 || ny >= height)
continue;
if(board[nx][ny]) continue;
if(height == 8 && width == 8 && range[nx][ny] == 1) {
if(c1 >= 0) return;
c1 = choices;
}
if(height == 4) {
char gg = 0;
if((ly == 1 || ly == 2) && (ny == 1 || ny == 2)) gg = 1;
if(gg ^ (level == width*height/2-1)) continue;
}
cx[choices] = nx, cy[choices] = ny;
++choices;
}

if(!choices) return;
if(c1 >= 0)
cx[0] = cx[c1], cy[0] = cy[c1], choices = 1;

++level;
if(width == 8 && height == 8) {
for(m=0; m<choices; ++m) {
nx = cx[m], ny = cy[m];
--range[nx][ny];
}
}

for(m=0; m<choices; ++m) {
nx = cx[m], ny = cy[m];

if(circuit) {
if(nx == 1 && ny == 2 && level < width*height-1) continue;
}

if(leftright) {
if(level == width*height-1 && nx < width-1) continue;
}

mx[level] = nx, my[level] = ny;
board[nx][ny] = 1;
makemove();
board[nx][ny] = 0;
}

if(width == 8 && height == 8) {
for(m=0; m<choices; ++m) {
nx = cx[m], ny = cy[m];
++range[nx][ny];
}
}

--level;
}

int main(int argc, char **argv)
{
if(argc != 5) {
fprintf(stderr, "usage: knight width height (x0 y0 | - - | - +)\n");
exit(1);
}

level = 0;
width = atoi(argv[1]);
height = atoi(argv[2]);
if(width <= 0 || width > 16 || height <= 0 || height > 8) {
fprintf(stderr, "width or height is out of range\n");
exit(1);
}

if(!strcmp(argv[3], "-") && !strcmp(argv[4], "-")) {
x0 = y0 = 0;
circuit = 1;
if(width&height&1) {
fprintf(stderr, "cannot have a circuit on an odd board\n");
exit(1);
}
} else if(!strcmp(argv[3], "-") && !strcmp(argv[4], "+")) {
x0 = y0 = 0;
leftright = 1;
} else {
x0 = atoi(argv[3]);
y0 = atoi(argv[4]);
if(x0 < 0 || x0 >= width || y0 < 0 || y0 >= height) {
fprintf(stderr, " start point is out of range\n");
exit(1);
}
if(height == 4 && (y0 == 1 || y0 == 2)) exit(1);
}

mx[0] = x0, my[0] = y0, board[x0][y0] = 1;
if(circuit) {
mx[1] = 2, my[1] = 1, board[2][1] = 1;
++level;
}

makemove();

exit(1);
}