// Problem#: 1153

// Submission#: 3079805

// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License

// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/

// All Copyright reserved by Informatic Lab of Sun Yat-sen University

//

//  main.cpp

//  馬的周游

//

//  Created by liujan on 10/24/14.

//  Copyright (c) 2014 liujan. All rights reserved.

//

include <iostream>
include "vector"
include "memory.h"
include "algorithm"
using namespace std;
bool isvisited[8][8];

int move_x[8] = { -2, -1, 1, 2, -2, -1, 1, 2 };

int move_y[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };

vector<int>route;
struct Node{

  int x, y;

  int child;

};
bool cmp(Node a, Node b){

  return a.child < b.child;

}

vector<Node> nextMove(Node current){

  int y = current.y;

  int x = current.x;

  vector<Node>next;

  for (int i = 0; i < 8; i++){

    int tmpx = x + move_x[i];

    int tmpy = y + move_y[i];

    if (tmpx >= 0 && tmpx <= 7 && tmpy <= 7 && tmpy >= 0 && !isvisited[tmpy][tmpx]){

      Node tmp;

      tmp.x = tmpx;

      tmp.y = tmpy;

      tmp.child = 0;

      next.push_back(tmp);

    }

  }

  return next;

}

bool move(Node pos){

  if (route.size() == 64){

    for (size_t i = 0; i < route.size() - 1; i++){

      cout << route[i] << " ";

    }

    cout << route[route.size() - 1] << endl;

    return true;

  }

  else{

    vector<Node> next = nextMove(pos);

    for (int i = 0; i < next.size(); i++){

      next[i].child = nextMove(next[i]).size();

    }

    sort(next.begin(), next.end(),cmp);

for (size_t i = 0; i < next.size(); i++){  
  int y = next[i].y;  
  int x = next[i].x;  
  isvisited[y][x] = true;  
  route.push_back(y * 8 + x + 1);  
  bool result = move(next[i]);  
  if (!result){  
    isvisited[y][x] = false;  
    route.pop_back();  
  }  
  else{  
    return true;  
  }  
}  
return false;  

}

}

int main(){

  int n;

  while (cin >> n && n != -1)

  {

    for (int i = 0; i < 8; i++){

      for (int j = 0; j < 8; j++)

        isvisited[i][j] = false;

    }

    route.clear();

    int y = (n - 1) / 8;

    int x = n - y * 8 - 1;

    Node head;

    head.x = x;

    head.y = y;

    isvisited[y][x] = true;

    route.push_back(n);

    move(head);

  }

}             </pre>