C++

Forum

 
What's wrong with my Knight's Tour program?

codem (1)
Here's my code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>

using namespace std;

int board [8][8];
int count = 1;

void printBoard()
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
        {
            if (board[i][j] > 9)
                cout << board[i][j] << " ";
            else
                cout << board[i][j] << "  ";
        }
        cout << endl;
    }
}

bool solveBoard(int x, int y)
{
    bool found = false;
    if (x < 0 || y < 0 || x > 7 || y > 7 || board[x][y] != 0)
        return false;
    board[x][y] = count++;
    if (count == 63)
        return true;
    if (!found)
        found = solveBoard(x + 2, y + 1);
    if (!found)
        found = solveBoard(x + 1, y + 2);
    if (!found)
        found = solveBoard(x - 1, y - 2);
    if (!found)
        found = solveBoard(x - 2, y - 1);
    if (!found)
        found = solveBoard(x + 2, y - 1);
    if (!found)
        found = solveBoard(x + 1, y - 2);
    if (!found)
        found = solveBoard(x - 1, y + 2);
    if (!found)
        found = solveBoard(x - 2, y + 1);
    if (!found)
    {
        board[x][y] = 0;
        count--;
    }
    return found;
}

int main ()
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            board[i][j] = 0;
    if (solveBoard(0,0))
        printBoard();
}


If i change the line "if (count == 64)" (line 32) to 63 or smaller, the program takes no time to present me a solution that shows the knight touring 62 spaces in a row. However, if I change it to 64 or 65 to find a solution touring 63 and 64 spaces in a row respectively, the program doesn't seem to end. What's wrong with my program?
Disch (13742)
Nothing. It's just slow.

Your program is brute-forcing (slow) a problem that may only have one solution in ~64^8 (281474976710656). So unless you get really lucky and find the correct path early on, it's going to take a really long time.

The reason it isn't slow with 62 moves is because there are many more possible solutions, so you're much more likely to find one that works early on.
namcs (30)
Hi codem, this is a very interesting problem. Like Disch said, it's just slow. Perhaps your can optimize it, using some heuristic technique on the Internet. Another possible way is not to use recursive but a queue or stack instead.
Topic archived. No new replies allowed.