StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POKnight Tour C++
primarykey
Id
7676593
data
AcceptedAnswerId
7676950
AnswerCount
3
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2011-10-06T15:24:40.273
FavoriteCount
0
LastActivityDate
2011-10-06T15:55:49.737
LastEditDate
LastEditorUserId
0
OwnerUserId
982371
ParentId
0
PostTypeId
1
Score
0
ViewCount
1565
LastEditorDisplayName
text
Body
<p>I am trying to solve Knight Tour Problem using recursive Backtracking. Can someone help me optimize my code. My code works till 6X6 board. . After N=7 it takes almost infinite time to solve . Here is my code :</p> <pre><code>#include <iostream> #include "genlib.h" #include "grid.h" #include "vector.h" #include <iomanip> const int NOT_VISITED = -1; //Size of the board const int N = 6; const int N2 = N*N; typedef Grid<int> chess; struct position{ int row; int col; }; //Initializes the board and makes each and every //square value as NOT_VISITED void initializeBoard(chess &board) { for(int i=0;i<board.numRows();i++) for(int j=0;j<board.numCols();j++) board[i][j] = NOT_VISITED; } //Returns true if the square is visited; bool visited(chess &board,position square) { return board[square.row][square.col ] != NOT_VISITED; } //Returns true if the givien position variable is outside the chess board bool outsideChess(chess &board, position square) { if(square.row <board.numRows() && square.col <board.numCols() && square.row >=0 && square.col >=0) return false; return true; } void visitSquare(chess &board,position square,int count) { board[square.row] [square.col] = count; } void unVisitSquare(chess &board,position square) { board[square.row] [square.col] = NOT_VISITED; } position next(position square,int irow, int icol) { square.row += irow; square.col += icol; return square; } Vector<position> calulateNextSquare(chess board,position square) { Vector<position> list; for(int i=-2;i<3;i=i+4) { for(int j=-1;j<2;j=j+2) { list.add(next(square,i,j)); list.add(next(square,j,i)); } } return list; } bool knightTour(chess &board,position square, int count) { //cout<<count<<endl; //Base Case if the problem is solved; if(count>N2) return true; if(outsideChess(board,square)) return false; //return false if the square is already visited if(visited(board,square)) return false; visitSquare(board,square,count); Vector<position> nextSquareList = calulateNextSquare(board,square); for(int i=0;i<nextSquareList.size();i++) if(knightTour(board, nextSquareList[i], count+1)) return true; unVisitSquare(board,square); return false; } void printChess(chess &board) { for(int i=0;i<board.numRows();i++) { for(int j=0;j<board.numCols();j++) cout<<setw(4)<<board[i][j]; cout<<endl; } } int main() { chess board(N,N); initializeBoard(board); position start; start.row = 0; start.col = 0; if(knightTour(board,start,1)) printChess(board); else cout<<"Not Possible"; return 0; } </code></pre> <p>i am using Stanford 106B Libraries( grid is a 2 dimensional vector ) Visual studio 2008 Blank project with required library files <a href="https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&hl=en" rel="nofollow">https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&hl=en</a></p>
Tags
<c++><optimization>
Title
Knight Tour C++
singulars
PostAcceptedAnswerId
1. PO
  singulars
  PostTypePostTypeId
  PTAnswer
PostParentId
1. This table or related slice is empty.
PostTypePostTypeId
1. PTQuestion
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USGanesh
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. PO
  singulars
  PostTypePostTypeId
  PTAnswer
2. PO
  singulars
  PostTypePostTypeId
  PTAnswer
3. PO
  singulars
  PostTypePostTypeId
  PTAnswer
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. CO"Almost infinite"?
  singulars
  PostPostId
  POKnight Tour C++
  UserUserId
  USspraff
2. CORan for half an hour still couldn't get output for 8X8..Even though its not infinity but still its lot of time for such a problem ...
  singulars
  PostPostId
  POKnight Tour C++
  UserUserId
  USGanesh

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.