#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[move1],colArray[move1],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,rootRow2,rootCol+1)) { board[rootRow2][rootCol+1]=move; rowArray[move]=rootRow2; colArray[move]=rootCol+1; moveType[rootRow2][rootCol+1]=1; //cout << "placed " << move << " on " << rootRow2 << "," << rootCol+1 << " by moveType 1" << endl; move++; after=0; return; } } if (after <2) { if (onBoardAndEmpty(board,rootRow1,rootCol+2)) { board[rootRow1][rootCol+2]=move; rowArray[move]=rootRow1; colArray[move]=rootCol+2; moveType[rootRow1][rootCol+2]=2; //cout << "placed " << move << " on " << rootRow1 << "," << 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,rootCol1)) { board[rootRow+2][rootCol1]=move; rowArray[move]=rootRow+2; colArray[move]=rootCol1; moveType[rootRow+2][rootCol1]=5; //cout << "placed " << move << " on " << rootRow+2 << "," << rootCol1 << " by moveType 5" << endl; move++; after=0; return; } } if (after <6) { if (onBoardAndEmpty(board,rootRow+1,rootCol2)) { board[rootRow+1][rootCol2]=move; rowArray[move]=rootRow+1; colArray[move]=rootCol2; moveType[rootRow+1][rootCol2]=6; //cout << "placed " << move << " on " << rootRow+1 << "," << rootCol2 << " by moveType 6" << endl; move++; after=0; return; } } if (after <7) { if (onBoardAndEmpty(board,rootRow1,rootCol2)) { board[rootRow1][rootCol2]=move; rowArray[move]=rootRow1; colArray[move]=rootCol2; moveType[rootRow1][rootCol2]=7; //cout << "placed " << move << " on " << rootRow1 << "," << rootCol2 << " by moveType 7" << endl; move++; after=0; return; } } if (after <8) { if (onBoardAndEmpty(board,rootRow2,rootCol1)) { board[rootRow2][rootCol1]=move; rowArray[move]=rootRow2; colArray[move]=rootCol1; moveType[rootRow2][rootCol1]=8; //cout << "placed " << move << " on " << rootRow2 << "," << rootCol1 << " 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 " << move1 << " after "; after = moveType[rowArray[move1]][colArray[move1]]; //cout << after << endl; removeMove(board,move1); 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. */
9 Replies  2422 Views  Last Post: 30 May 2012  06:45 PM
#1
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 programmerdefined 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??
Replies To: How to make my Knight's Tour solution more efficient?
#2
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?
#3
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.
#4
Re: How to make my Knight's Tour solution more efficient?
Posted 30 May 2012  03:33 PM
bennigan88, 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.
#5
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.
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.
#6
Re: How to make my Knight's Tour solution more efficient?
Posted 30 May 2012  05:12 PM
Skydiver, 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.
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.
#7
Re: How to make my Knight's Tour solution more efficient?
Posted 30 May 2012  05:30 PM
Your bounds checks are lines 226229. 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.
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.
#8
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
#9
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
#10
Re: How to make my Knight's Tour solution more efficient?
Posted 30 May 2012  06:45 PM
More like
or
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); }
Page 1 of 1
