9 Replies - 2422 Views - Last Post: 30 May 2012 - 06:45 PM Rate Topic: -----

#1 bennigan88  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 07-April 12

How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 02:20 PM

Ok my program successfully finds the *first* solution (if one is possible) to the knight's tour problem on an n x n board with a programmer-defined value for n. Any ideas to make it faster? It's fine for n=6 but 7 and 8 start to get really slow. I've already added in some arrays to store data for faster access, I was thinking of scrapping the whole 2 dimensional array all together and just using two single dimension arrays... any thoughts??


#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

const int n=4;
void printBoard(int board[][n]); //works
void clearBoard(int board[][n]); //works
void removeMove(int board[][n], int move); //works
bool onBoardAndEmpty(int board[][n], int row, int col); //works
int rowOfMove(int board[][n], int move); //works
int colOfMove(int board[][n], int move); //works




void place(int board[][n], int moveType[][n], int& move, int rootRow, int rootCol, int& after, int rowArray[], int colArray[]);


int main()
{
    int board[n][n];
    int moveType[n][n];
    int max=pow(n,2);
    int rowArray[max];
    int colArray[max];

    /* initializing boardspace */
    //cout << "Initializing board..." << endl << endl;
    clearBoard(board);
    int startRow=1;
    int startCol=1;
    board[startRow][startCol]=0;
    rowArray[0]=startRow;
    colArray[0]=startCol;
    //printBoard(board);



    /* paramaters for place() */
    int move=1,after=0;

    /* while board still has emtpy spaces */
    while (move<(pow(n,2)))
    {

    place(board,moveType,move,rowArray[move-1],colArray[move-1],after,rowArray,colArray);
    //printBoard(board);
    //system("PAUSE");
    //cout << endl;

    }

    printBoard(board);






    return 0;
}





void place(int board[][n], int moveType[][n], int& move, int rootRow, int rootCol, int& after, int rowArray[], int colArray[])
{
    if (move==0)
    {
        cout << endl << endl << "couln't solve with this starting square" << endl;
        exit(1);
        /* this will just increment 0 through all coordinates so that all possible combinations are considered */
    }
    else
    {
        /* move is some integer */
        if (after <1)
        {
            if (onBoardAndEmpty(board,rootRow-2,rootCol+1))
            {
                board[rootRow-2][rootCol+1]=move;
                rowArray[move]=rootRow-2;
                colArray[move]=rootCol+1;
                moveType[rootRow-2][rootCol+1]=1;
                //cout << "placed " << move << " on " << rootRow-2 << "," << rootCol+1 << " by moveType 1" << endl;
                move++;
                after=0;
                return;
            }
        }
        if (after <2)
        {
            if (onBoardAndEmpty(board,rootRow-1,rootCol+2))
            {
                board[rootRow-1][rootCol+2]=move;
                rowArray[move]=rootRow-1;
                colArray[move]=rootCol+2;
                moveType[rootRow-1][rootCol+2]=2;
                //cout << "placed " << move << " on " << rootRow-1 << "," << rootCol+2 << " by moveType 2" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <3)
        {
            if (onBoardAndEmpty(board,rootRow+1,rootCol+2))
            {
                board[rootRow+1][rootCol+2]=move;
                rowArray[move]=rootRow+1;
                colArray[move]=rootCol+2;
                moveType[rootRow+1][rootCol+2]=3;
                //cout << "placed " << move << " on " << rootRow+1 << "," << rootCol+2 << " by moveType 3" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <4)
        {
            if (onBoardAndEmpty(board,rootRow+2,rootCol+1))
            {
                board[rootRow+2][rootCol+1]=move;
                rowArray[move]=rootRow+2;
                colArray[move]=rootCol+1;
                moveType[rootRow+2][rootCol+1]=4;
                //cout << "placed " << move << " on " << rootRow+2 << "," << rootCol+1 << " by moveType 4" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <5)
        {
            if (onBoardAndEmpty(board,rootRow+2,rootCol-1))
            {
                board[rootRow+2][rootCol-1]=move;
                rowArray[move]=rootRow+2;
                colArray[move]=rootCol-1;
                moveType[rootRow+2][rootCol-1]=5;
                //cout << "placed " << move << " on " << rootRow+2 << "," << rootCol-1 << " by moveType 5" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <6)
        {
            if (onBoardAndEmpty(board,rootRow+1,rootCol-2))
            {
                board[rootRow+1][rootCol-2]=move;
                rowArray[move]=rootRow+1;
                colArray[move]=rootCol-2;
                moveType[rootRow+1][rootCol-2]=6;
                //cout << "placed " << move << " on " << rootRow+1 << "," << rootCol-2 << " by moveType 6" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <7)
        {
            if (onBoardAndEmpty(board,rootRow-1,rootCol-2))
            {
                board[rootRow-1][rootCol-2]=move;
                rowArray[move]=rootRow-1;
                colArray[move]=rootCol-2;
                moveType[rootRow-1][rootCol-2]=7;
                //cout << "placed " << move << " on " << rootRow-1 << "," << rootCol-2 << " by moveType 7" << endl;
                move++;
                after=0;
                return;
            }

        }
        if (after <8)
        {
            if (onBoardAndEmpty(board,rootRow-2,rootCol-1))
            {
                board[rootRow-2][rootCol-1]=move;
                rowArray[move]=rootRow-2;
                colArray[move]=rootCol-1;
                moveType[rootRow-2][rootCol-1]=8;
                //cout << "placed " << move << " on " << rootRow-2 << "," << rootCol-1 << " by moveType 8" << endl;
                move++;
                after=0;
                return;
            }

        }
        /* only gets to this code if no available square is found and causes function to return */
        //cout << "can't place move " << move << endl;
        if (move==1)
        {
            cout << "need new starting square ://>" << endl;
            exit(1);
        }
        if (move>1)
        {
            //cout << "need new square for move " << move-1 << " after ";
            after = moveType[rowArray[move-1]][colArray[move-1]];
            //cout << after << endl;
            removeMove(board,move-1);
            move--;
        }



    }
}

bool onBoardAndEmpty(int board[][n], int row, int col)
{
    bool empty=0, validRow=0, validCol=0;

    if (board[row][col]==-1)
        empty=1;
    if ((row>-1)&&(row<n))
        validRow=1;
    if ((col>-1)&&(col<n))
        validCol=1;
    if ((empty)&&(validRow)&&(validCol))
        return 1;
    else
        return 0;

    /* THIS CODE IS FOR TESTING onBoardAndEmpty()
    int row=0, col=0;
    cout << "square " << row << "," << col << " is ";
    if (!onBoardAndEmpty(board,row,col))
        cout << "not ";
    cout << "an empty square!" << endl; */
}


void removeMove(int board[][n], int move)
{
    for (int row=0; row<n; row++){
        for (int col=0; col<n; col++){
            if (board[row][col]==move)
                board[row][col]=-1;
        }

    }
}







void clearBoard(int board[][n])
{
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            board[i][j]=-1;
        }
    }
}
void printBoard(int board[][n])
{
    for (int i=0; i<n; i++){
        for (int j=0; j<n; j++){
            if (board[i][j]==-1)
                cout << "[  ] ";
            else
            {
                cout << "[";
                if ((board[i][j]<10)&&(board[i][j]>-1))
                    cout << " ";
                cout << board[i][j] << "] ";
            }
        }
        cout << endl << endl << endl;;
    }
}

/*

[24] [15] [ 6] [ 1] [18]


[ 5] [ 0] [17] [14] [ 7]


[16] [23] [10] [19] [ 2]


[11] [ 4] [21] [ 8] [13]


[22] [ 9] [12] [ 3] [20]



Process returned 0 (0x0)   execution time : 158.303 s
Press any key to continue.

*/


/*
[20] [11] [ 6] [ 1] [18]


[ 5] [16] [19] [12] [ 7]


[10] [21] [ 0] [17] [ 2]


[15] [ 4] [23] [ 8] [13]


[22] [ 9] [14] [ 3] [24]



Process returned 0 (0x0)   execution time : 33.117 s
Press any key to continue.
*/

/*
[24] [ 1] [12] [ 7] [22]


[11] [ 6] [23] [ 2] [13]


[ 0] [17] [14] [21] [ 8]


[ 5] [10] [19] [16] [ 3]


[18] [15] [ 4] [ 9] [20]



Process returned 0 (0x0)   execution time : 74.021 s
Press any key to continue.
*/

/*
[35] [44] [51] [ 0] [27] [38] [11] [ 2]


[52] [41] [36] [39] [50] [ 1] [28] [ 9]


[45] [34] [43] [26] [37] [10] [ 3] [12]


[42] [53] [40] [49] [24] [29] [ 8] [17]


[33] [46] [25] [54] [61] [18] [13] [ 4]


[58] [55] [48] [23] [30] [ 7] [16] [19]


[47] [32] [57] [60] [21] [62] [ 5] [14]


[56] [59] [22] [31] [ 6] [15] [20] [63]



Process returned 0 (0x0)   execution time : 26.095 s
Press any key to continue.




*/



Is This A Good Question/Topic? 0
  • +

Replies To: How to make my Knight's Tour solution more efficient?

#2 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3535
  • View blog
  • Posts: 10,943
  • Joined: 05-May 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 02:29 PM

Have you run a profiler to find where all the time is spent?
Was This Post Helpful? 0
  • +
  • -

#3 bennigan88  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 07-April 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 03:06 PM

I've never done that before. I'm using codeblocks as my editor.
Was This Post Helpful? 0
  • +
  • -

#4 mojo666  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 352
  • View blog
  • Posts: 770
  • Joined: 27-June 09

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 03:33 PM

View Postbennigan88, on 30 May 2012 - 03:20 PM, said:

Any ideas to make it faster? It's fine for n=6 but 7 and 8 start to get really slow. I've already added in some arrays to store data for faster access, I was thinking of scrapping the whole 2 dimensional array all together and just using two single dimension arrays... any thoughts??

I'm having trouble following the code, but I assume you are just using simple brute force (checking every possible path until you hit a solution).
Things such as switching the types of arrays for faster data access is going to have minimal effect on the run time. Your program takes a certain number of steps for a certain sized input. You are trying to make each step faster. Such a strategy quickly proves to be futile since the number of steps grows exponentially as input grows. For example, suppose you figure out how to make it reasonably fast for all boards 8x8 and less. You now try 9x9. The number of steps will at least double eliminating all the benefit of your optimizations. It is usually much more productive to try and find short cuts that eliminate whole branches of steps in the first place. For example, There may be more than one way to reach a certain position. If you somehow store positions you can prevent repeating fruitless searches, just return the result of your first search.
I think an effective strategy you can try is to keep track of how many ways there are to get to each unmarked square. For example, there are two ways to get to a corner. If both these squares are removed and the corner remains unvisited, you can be certain you are trying a wrong path and all the effort put forward from that point will be fruitless. So, just keep track of this number for every square and if a square falls to 0 then it either must be the next move or you need to back track and try a different path.
I hope this gives you some ideas.
Was This Post Helpful? 2
  • +
  • -

#5 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3535
  • View blog
  • Posts: 10,943
  • Joined: 05-May 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 04:02 PM

Excellent advice from @mojo666! A better algorithm will often help more than a better data structure (provided the data structure is compatible with the algorithms' access patterns).

A tiny bit though on micro optimizations, though:
On line 45, you use pow() which involves a floating point computation each time you loop through. Why can't you just compute "int targetMoves = n * n;" once, and be done with it?
In your onBoardAndEmpty() empty function, you should check the bounds first and bail out early before checking the contents. Local variable comparisons (often put in registers by the compiler) are faster than memory access (like indexing into an array). Also the bounds checks will protect you for overrunning or under running your array.
Was This Post Helpful? 0
  • +
  • -

#6 bennigan88  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 07-April 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 05:12 PM

View PostSkydiver, on 30 May 2012 - 04:02 PM, said:

Excellent advice from @mojo666! A better algorithm will often help more than a better data structure (provided the data structure is compatible with the algorithms' access patterns).

A tiny bit though on micro optimizations, though:
On line 45, you use pow() which involves a floating point computation each time you loop through. Why can't you just compute "int targetMoves = n * n;" once, and be done with it?
In your onBoardAndEmpty() empty function, you should check the bounds first and bail out early before checking the contents. Local variable comparisons (often put in registers by the compiler) are faster than memory access (like indexing into an array). Also the bounds checks will protect you for overrunning or under running your array.


I'm not sure what you mean by checking the bounds first and bailing. Also, in response to the other post, I could take a look at adding heuristics, but the way my program looks is it checks in clockwise order for blank squares, and when backtracking it does not check squares that have already been checked from a specific node, it picks up on the *next* move type...if that makes any sense.
Was This Post Helpful? 0
  • +
  • -

#7 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3535
  • View blog
  • Posts: 10,943
  • Joined: 05-May 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 05:30 PM

Your bounds checks are lines 226-229. You set validRow or validCol to true. But if you look at the logic on line 230, the only way to return true is if both are true. So by logic, if either of your bounds checks fails, you can return false right away.

Additionally, on lines 224 you access the array. If row or col is less than 0 or greater than or equal to n, you have overrun the extents of your array. Hence you want to do your bounds checks first, then try to check the array contents.
Was This Post Helpful? 0
  • +
  • -

#8 bennigan88  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 07-April 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 05:36 PM

Is this what you meant?

bool onBoardAndEmpty(int board[][n], int row, int col)
{
   if (!(row>-1))
        return 0;
    if (!(row<n))
        return 0;
    if (!(col<n))
        return 0;
    if (!(col>-1))
        return 0;
    if (board[row][col]!=-1)
        return 0;
    return 1;
}


This post has been edited by bennigan88: 30 May 2012 - 05:45 PM

Was This Post Helpful? 0
  • +
  • -

#9 bennigan88  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 40
  • Joined: 07-April 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 05:44 PM

err, and of course assuming i take out the ';' after one of the if statements, and take out the variable declarations
Was This Post Helpful? 0
  • +
  • -

#10 Skydiver  Icon User is offline

  • Code herder
  • member icon

Reputation: 3535
  • View blog
  • Posts: 10,943
  • Joined: 05-May 12

Re: How to make my Knight's Tour solution more efficient?

Posted 30 May 2012 - 06:45 PM

More like
bool onBoardAndEmpty(int board[][n], int row, int col)
{
    if ((row < 0) || (row >= n))
        return false;
    if ((col < 0) || (col >= n))
        return false;
    return board[row][col] == -1;
}



or

bool onBoardAndEmpty(int board[][n], int row, int col)
{
    return ((row >= 0) && (row < n)) &&
           ((col >= 0) && (col < n)) &&
           (board[row][col] == -1);
}


Was This Post Helpful? 0
  • +
  • -

Page 1 of 1