Some trouble with backtracking

Question

I've spent the better part of the past couple days trying to wrap my head around recursive backtracking. Conceptually I think I understand it, but I can't seem to implement it for things more involved than something like n-queen. The challenge is to solve a 5x5 puzzle by filling in alphabets beginning with A and ending with Y. Each letter must be adjacent to the letters directly before and after it (diagonals count as adjacent).

Additionally, around the edges of the puzzle are "clues" defining where the subsequent alphabets must be in relation to the outer-most edges of the "gameboard" as it were. For example, letter B must appear either horizontally or vertically "B" on the clue part of the board, while letter "P" will appear diagonally from the "P" on the clue part of the board, since the clue for "P" is in a corner. I currently have the board laid out as a 7x7 array which includes the clues on the outside to keep it organized as follows.

 T X Y N F E J 
 V 0 0 0 0 0 O 
 R 0 0 0 0 0 Q 
 L 0 0 0 0 0 C  
 K 0 0 0 0 0 H 
 G 0 0 0 0 0 I 
 P W U S D B M 

The "A" can appear anywhere within the board (the area marked with 0's). I began with A at array[3][5] and began attempting to populate the rest of the gameboard from there. I manage to make it to letter F before it stops working, so my board currently looks like this.

  T X Y N F E J 
  V 0 0 0 F E O 
  R 0 0 0 D B Q 
  L 0 0 0 C A C 
  K 0 0 0 0 0 H 
  G 0 0 0 0 0 I 
  P W U S D B M 

The following is mode code thus far. I'm currently using a character stack to hold all the letters (B on the top, Y on the bottom):

  public boolean solver(int currRow, int currCol){ //sets current focus
  nt column=0;
  int row=0;

  if(abcs.empty()) //the base case, returns true when abc stack is empty
     return true;

  for(row=currRow-1;row<=(currRow+1);row++) //cycles through the spaces
                                            //adjacent to the focus spot
        {

        for(column=currCol-1;column<=(currCol+1);column++)
           {

           if(promising(row,column,abcs.peek())) //invokes a method
              {                     // designed to check the clues
              prevChar=array[row][column]; //saves char just in case
              array[row][column]=abcs.pop(); //pops stack and adds to board

              solver(row,column); //my attempt at recursion
              }
           else    //haven't quite figured out what needs to be here
              ;     



             } 
           }


        display();

        abcs.push(prevChar);   //these steps are for replacing the array
                            //values if no legit adjacent spots are found
        if(array[currRow][currCol]!='A') //(unsure if necessary)
           array[currRow][currCol]='0';



     return(false);}  //the false return that is supposed to begin                        
                      //backtracking
 public void display() //prints the 2d array in a grid
  {
  String holder="";
  for(int i = 0; i<7;i++)
     {
     for(int k = 0; k<7; k++)
        {
        holder=holder + array[i][k] + " ";
        }
     holder=holder + "\n";
     }
  System.out.println(holder);

  }

I've researched backtracking, and it seems like this problem is somewhere between a general "maze traversal" and "sudoku". It seems to be necessary that I store which parts of the grid I've visited before hand, but I'm not sure what method would be best for that while still considering this to be recursion. I'm open to being told "you've gone about this the completely wrong way", because I'm honestly not sure what else to try at this point. Any advise would be appreciated.

Answer 1

Basically, backtracking works as follows:

-Pick a starting point
-While the problem isn't solved
       -For each path from the starting point
             -Set that as the starting point and recurse
             -If it returns true, then return true
       -Undo the current move (since none of the options panned out)
       -Return false

I can't clearly make out where you 'undo'? You can implement this either by pushing the state to a stack each move and popping it on undo, or by undoing a move on the board.

I would start anew and try to make the Java code mimick the algorithm above. Also, I would introduce more ObjectOriented code to it.

You could implement methods like isSolved(), getValidMoves(), and the main method doNextMove(), which will be called recursivly.

If I would have to implement this, I would create something like a Board class that contains the state.

The Board class can have the getValidMoves(), isSolved() and doMove() methods.

Your BackTracker class should implement the recursive logic, and would look something like this.

public static void iterate(Board b, char c)
{
    List<Move> moves = b.getValidMoves(c);


    for (Move m : moves)
    {
        Board n = Board.copyOf(b);
        n.doMove(m, c);
        if (n.isSolved())
        {
            System.out.println(n.toString());
        }
        else
        {
            iterate(n, (char) (c+1));
        }
    }

}
public static void main(String[] args) {

    Board b = Board.create();
    iterate(b, 'a');
}

Btw. I got 3 solutions. (in 7296 iterations)