I'm trying to write my first game, and in order to do so, I need to design a recursive algorithm with backtracking capabilities.

In the game, there is a grid of tiles. Some of these tiles back be moved to; however, a few of them are impassable. The goal of the player is to travel to each open tile once, which means that he must travel to every tile without crossing his path.

At any given point, a player may have a maximum of 3 choices of direction to move, except on the first move, during which the player will have 4 choices, and a minimum of 1 choice. Since the player travels from one block to the next but is unable to cross his path, he cannot travel backwards. So, in essence, the player can travel up, down, left or right minus one possibility (the direction you came from).

here is some psuedo code I wrote

bool GenBoard(class Tile pBoard[pBoard.GetRows][pBoard.GetColumns].itsCheck,[])
{
	//base case
	 if (w == []){ 
		return true;
	 }
	 for all a in w{
		 if OK(a) //if the player has not moved to this tile
			 GenBoard(w-{a}, p + {a});  //(w - {a}) removes a from boolean set w | (p + a) = append a to list p.
				return true;
	 }
	 //backtrack
	 return false
 }

I figured I would have 2 sets, w and p. w holds all possible tiles that have not been traveled to and that are not impassable.
p is a list of those tiles that have been traveled to.
a is the element of the set that the player is considering to move to
once set w is empty, then a solvable maze has been generated (the base case).

...my first conundrum is will this strategy even work. And if it will, how in the world do I even go about implementing it?

Thanks for the help

bool GenBoard(w,[])

accidentally messed up the function arguments. here is a modified version

I guess I'll post what I've done so far. The last bit is psuedocode. I just need someone to tell me if I'm on the right track or not.

bool GenBoard(class Tile *pBoard[pBoard.GetRows()][pBoard.GetColumns()])
	 {
		 // Base case
		 //Check to see if every cell has been visited yet
		 for (int i = 0; i < pBoard.GetRows(); i++)
		 {
			 for (int j = 0; i < pBoard.GetColumns(); i++)
			 {
				 if (pBoard.GetUnvisted()) == true)
					 break;
				 else return true; //Everything was visited. Board is complete
			 }
		 }

		// See if we were forced to re-visit a location.  That means that the current location has been visited
		if (pBoard.GetUnvisited() == pBoard.GetCurrentPosition())
		{
			return false;
		}
		for location in adjacentTo(currentLocation)
		{
			if checkIfSolvable(location, unvisitedLocations - location)
				return true;
		}
		return false // a solution cannot be reached by moving somewhere from this point
}
This article has been dead for over six months. Start a new discussion instead.