Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool GameBoard::KT_Heuristic(unsigned row, unsigned column)
- {
- // only iterate if a tour hasn't been found yet
- if( !success )
- {
- int position = Convert2D(row, column); // find 1D position
- PlaceKnight(row, column); // place the knight
- // if a tour wasn't found
- if( !success )
- {
- // find all possible moves from current position
- std::vector<int> possible_moves = FindPossibleMoves(position);
- // list of possible moves sorted into a linear fashion
- std::list<int> sorted_moves;
- // if there are possible moves
- if( possible_moves.size() )
- {
- // for each possible move
- for( unsigned i = 0; i < possible_moves.size(); ++i )
- {
- // update the heuristics table
- --hTable_[possible_moves[i]];
- // if there are already items in the sorted moves list
- if( sorted_moves.size() )
- {
- unsigned size = sorted_moves.size(); // check size (to see if it changes)
- // for each item in the sorted list
- for( std::list<int>::iterator iter = sorted_moves.begin(); iter != sorted_moves.end(); ++iter )
- {
- // check to see where it should be inserted
- if( !CompareHTable((*iter), possible_moves[i]) )
- {
- // insert the move into the list where it belongs
- sorted_moves.insert(iter, possible_moves[i]);
- break; // cut out
- }
- }
- // if the size didn't change, then no insert; it belongs at the end
- if( size == sorted_moves.size() )
- sorted_moves.push_back(possible_moves[i]); // add it to the end
- }
- else // otherwise if the list is empty
- sorted_moves.push_back(possible_moves[i]); // start the list
- }
- // for each possible sorted move
- for( std::list<int>::iterator iter = sorted_moves.begin(); iter != sorted_moves.end(); ++iter )
- {
- int n_row, n_column;
- ConvertBack((*iter), n_row, n_column); // find the 2D point
- // if the possible move is empty
- if( board_[(*iter)] == BLANK )
- success = KT_Heuristic(n_row, n_column); // follow recursion through the new spot
- }
- }
- else // otherwise
- {
- success = false; // the tour is not successful
- }
- if( !success ) // if the path was not successful
- RemoveKnight(row,column); // backtrack
- }
- }
- return success; // return if the tour was successful or not
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement