Knight's Tour Backtrack

[Erland]

Can you help me with this? This code keep running for more than one hour. Though if I change the base case to s == 64 it work but not for all possible coordinate, but it will stop at 63. If s == 65 it will only work for 4 corner.

#include <iostream>
using namespace std;

int xs[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int ys[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int b[12][12];

bool knighttour(int x, int y, int s)
{
    if (s == 64){
        return true;
    }
    for (int i=0; i<8; i++){
        if (b[x+xs[i]][y+ys[i]] == 0){
            b[x+xs[i]][y+ys[i]] = s;
            if (knighttour(x+xs[i], y+ys[i], s+1)){
                return true;
            }
            else{
                b[x+xs[i]][y+ys[i]] = 0;
            }
        }
    }
    return false;
}

int main()
{
    for (int i=0; i<12; i++){
        for (int j=0; j<12; j++){
            if (i>1 && i<10 && j>1 && j<10){b[j][i] = 0;}
            else {b[j][i] = 1;}
        }
    }

    int x, y;

    cout << "Initial Coordinate (x y): ";
    cin >> x >> y;
    x += 1; y += 1;
    b[x][y] = 1;

    knighttour(x, y, 2);

    for (int i=2; i<10; i++){
        for (int j=2; j<10; j++){
            if (b[j][i]<10){cout << " " << b[j][i] << " ";}
            else {cout << b[j][i] << " ";}
        }
        cout << endl;
    }

    return 0;
}

[cire]

A brute force algorithm is going to take a very, very long time to solve this problem.

See: http://en.wikipedia.org/wiki/Knight%27s_tour
Pay particular attention to the section on algorithms.