騎士之旅C++

Question

我正在嘗試使用遞歸回溯來解決騎士之旅問題。有人可以幫助我優化我的代碼。我的代碼工作到6X6板。 。在N = 7之後，需要幾乎無限的時間來解決。 這裏是我的代碼：

#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; 
} 

我使用斯坦福106B庫（網格是2維向量） 的Visual Studio 2008與所需的庫文件https://docs.google.com/viewer?a=v&pid=explorer&chrome=true&srcid=0BwLe9NJT8IreNWU0N2M5MGUtY2UxZC00ZTY2LWE1YjQtMjgxYzAxMWE3OWU2&hl=en空白項目

Answer 1

我會說，一開始，擺脫這個：

Vector<position> nextSquareList = calulateNextSquare(board,square); 

創建一個向量在每一步都需要很多時間。你可以使用一個數組（固定大小，因爲你知道有8個可能的移動），或者unroll the loop entirely。與this version, similar to yours比較。

Answer 2

一些修改，我想建議：

#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 int chess[N][N]; // <------------- HERE 

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; 
} 
void calulateNextSquare(chess board,position square, Vector<position>& list) // <------------- HERE 
{ 
    // ------------- HERE 
    //Also, change this part to add only unvisited and not out-of-board positions. 
    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)); 
     } 
    } 
} 

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; // <------------- HERE 
    calulateNextSquare(board,square,nextSquareList); 
    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; 
} 

但請注意，您仍然有exponential的複雜性，並優化你的代碼不會改變它。

Answer 3

您正在傳遞董事會副本來計算下一個廣場，但看起來你並不需要這種方法。

另外，你在這個方法中返回一個向量，但是你應該通過引用來傳遞它。