15 replies to this topic

[jashsayani]

Hi,

Its been a long time since I have used backtracking so I was brushing up my skills. I wrote a quick 4 Queens program (smaller board than 8 Queens) but there seems to be an error, most likely in my solve method.

Would be great if someone went through the code and pointed it out. Thanks.

public class QueensFour
{
	static char[][] grid = new char[4][4];
	static Queue result = new Queue();
	static int queensPlaced = 0;
	

public static void main(String[] args)
	{
     int col = 0; // Use 0 to 3
		     boolean complete = solve(col);
		
		     if(complete)
			          printResult();
	}


	
	static boolean solve(int col)
	{
		     if(queensPlaced == 4) return true; // Base Case
		
		     
     for(int row=0; row<3; row++)
		     {
			          if(canMove(grid, col, row))
			          {
				               // Place queen
				               grid[col][row] = 'Q';
				               addToResult(col, row);
				               queensPlaced++;
				
				
               if(!(solve(col+1))) // Cannot solve next one
				               {
					                    // Remove queen
					                    grid[col][row] = ' ';
					                    removeFromResult();
					                    queensPlaced--;
				               }
			          }
		     }
		
		     return false; // Failed
	}


	
	static boolean canMove(char[][] g, int col, int row)
	{
		     for(int i=0; i<4; i++)
		     {
			     for(int j=0; j<4; j++)
			     {
				     if(g[i][j] == 'Q' && j == row) // Same row
					          return false;
				     if(g[i][j] == 'Q' && i == col) // Same col
					          return false;
				     if(g[i][j] == 'Q' && (i-j) == (col-row)) // Diagonal
					          return false;
			     }
		     }
		
		
return true; // Legal move
	}
	
	
static void addToResult(int col, int row)
	{
		String resultValue = "[" + col + "," + row + "]";
		result.enqueue(resultValue);
	}
	
	static void removeFromResult()
	{
		try {
			result.dequeue();
		}
		catch(Exception e)
		{
			System.out.println("Error in Dequeue");
		}
	}
	
	static void printResult()
	{
		while(!(result.isEmpty()))
		{
			try {
				String move = result.dequeue().toString();
				System.out.println(move);
			}
			
			catch(Exception e)
			{
				System.out.println("Error in Dequeue");
			}
		}
	}
}

[wim DC]

I will post more later when I'm at home (Another 7 hrs from now :p)
But to start with:
Diagonal check is wrong.
removeFromResult should reduce the queensPlaced value.

[fread]

Its a long time since I've seen it too. I have a solution for this but it is not like yours. In an attempt to help you think you can post the Queue class? I'm being lazy :P

[wim DC]

You can do:

import java.util.Queue;
...
static Queue<String> result = new LinkedList<String>();
...
result.add() instead of enqueue()
result.remove() instead of dequeue()

[fread]

Cool.:thumbup1:.
Edit: @WimDC: By chance you making any progress? Before i dive headfirst and waste a few hours.

[wim DC]

I completed it at work between the server's building times :P

[fread]

I struggled for a long time with your canMove() method. I find the compact nature of this code very hard to trace errors in recursion, or maybe I am a bit slow . I any case I stretched out your canMove method:

your canMove():

static boolean canMove(char[][] g, int col, int row)
        {
            for(int i=0; i<4; i++)
            {
        for(int j=0; j<4; j++)
                {
                        if(g[i][j] == 'Q' && j == row) // Same row
                            return false;
                        if(g[i][j] == 'Q' && i == col) // Same col
                            return false;
                        if(g[i][j] == 'Q' && (i-j) == (col-row)) // Diagonal
                            return false;
                 }
            }
            return true; // Legal move
    }

my canMove():

public static boolean canMove(char [][]grid, int col, int row)
        {
                if(col == 0) return true;  //first queen
                int i, j;

                //scan column rows for a queen; go up to the columnth queen
                
                for(i = 0; i < col; i++)
                      if(grid[i][row] == 'Q') return false;

                
                //up and left; once, b/c the queen is at this position
                
                i = col-1;
                j = row - 1;

                //keep going up and left and check for a queen in this diagonal
                
                while(i > -1 && j > -1 && grid[i][j] == ' ')
                {
                        i -= 1;
                        j -= 1;
                 }

                if(i < 0 || j < 0) //out of bounds
                {
                            //up and right; once, b/c the queen is at this position
                            
                            i = col-1;
                            j = row + 1;
                            
                            //now keep going up and right and check for a queen in this diagonal
                            while(i >= 0 && j < numQueens && grid[i][j] == ' ')
                            {
                                    i -= 1;
                                    j += 1;
                             }
                             
                            //no queen in the diagonals nor in this column (out of bounds); this is a partial solution
                             if(i < 0 || j >= numQueens) return true;
                }
                return false;
        }

I realize it is a much longer than yours but to me its easier to trace logic errors.

I added this method to represent an initial state of the board:

public static void initGrid()
        {
            for(int i = 0; i < numQueens; i++)
                for(int j = 0; j < numQueens; j++)
                    grid[i][j] = '  ';
        }

I also added this method to make the output more 'pretty':

 public static void printBoard(char [][]B)
        {
             int i, j;
             for(i = 0; i < numQueens; i++)
             {
                       for(j = 0; j < numQueens; j++)
                       {
                                     if(B[i][j] == 'Q') System.out.print("   " + 'Q'); //printf("%3c", 'Q');
                                     else System.out.print("   " + '-');//printf("<", '-');
                       }
                       System.out.println("\n");//printf("\n\n");
             }
        }

So the only major change was the canMove() method. The run time of the algorithm is also unchanged.

Final result

public class QueensFour
{
        static int numQueens = 12;
        static char[][] grid = new char[numQueens][numQueens];
        static Queue result = new LinkedList<String>();;
        static int queensPlaced = 0;
        


        public static void main(String[] args)
        {
              int col = 0; // Use 0 to 3
              initGrid();
              boolean complete = solve(grid,col);

               if(complete)
               {
                   printResult();
                   printBoard(grid); /* I added this method to make the solution more visible */
                 
              }
        }

        public static void initGrid()
        {
            for(int i = 0; i < numQueens; i++)
                for(int j = 0; j < numQueens; j++)
                    grid[i][j] = ' ';
        }



    static boolean solve(char[][] grid, int col)
    {
             for(int row = 0; row < numQueens; row++)
             {
                     grid[col][row] = 'Q'; //place a queen here

                     //test for partial soluton
                     if(   canMove(grid, col, row)  )
                     {
                            addToResult(col, row);

                            /* we have place the last queen; numQueens - 1 since we our arrays start at zero */
                            if(col == numQueens - 1) return true; 
                            if(!solve(grid, col+1)) removeFromResult();//partial solution thus far try placing another queen
                            else  return true;  
                     }
                     grid[col][row] = ' '; /* removing queen: queen could not be placed in this row try placing in the next row */
             }
             return false;
             
    }
        
        public static boolean canMove(char [][]grid, int col, int row)
        {
                if(col == 0) return true;  //first queen
                int i, j;

                //scan column rows for a queen; go up to the columnth queen

                for(i = 0; i < col; i++)
                      if(grid[i][row] == 'Q') return false;

                
                //up and left; once, b/c the queen is at this position

                i = col-1;
                j = row - 1;

                //keep going up and left and check for a queen in this diagonal

                while(i > -1 && j > -1 && grid[i][j] == ' ')
                {
                        i -= 1;
                        j -= 1;
                 }

                if(i < 0 || j < 0) //out of bounds
                {
                            //up and right; once, b/c the queen is at this position

                            i = col-1;
                            j = row + 1;

                            //now keep going up and right and check for a queen in this diagonal
                            while(i >= 0 && j < numQueens && grid[i][j] == ' ')
                            {
                                    i -= 1;
                                    j += 1;
                             }

                            //no queen in the diagonals nor in this column (out of bounds); this is a partial solution
                             if(i < 0 || j >= numQueens) return true;
                }
                return false;
        }

        static void addToResult(int col, int row)
        {
            String resultValue = "[" + col + "," + row + "]";
            result.add(resultValue);
        }

        static void removeFromResult()
        {
            try {
                    result.remove();
            }
            catch(Exception e)
            {
                    System.out.println("Error in Dequeue");
            }
        }

        /* I added this method to make the solution more visible */
       public static void printBoard(char [][]B)
        {
             int i, j;
             for(i = 0; i < numQueens; i++)
             {
                       for(j = 0; j < numQueens; j++)
                       {
                                     if(B[i][j] == 'Q') System.out.print("   " + 'Q'); //printf("<", 'Q');
                                     else System.out.print("   " + '-');//printf("<", '-');
                       }
                       System.out.println("\n");//printf("\n\n");
             }
        }



        static void printResult()
        {
                while(!(result.isEmpty()))
                {
                        try {
                                String move = result.remove().toString();
                                System.out.println(move);
                        }
                        catch(Exception e)
                        {
                                System.out.println("Error in Dequeue");
                        }
                }
        }
}

Backtracking is uUuUUUuuGgGgGGggLLLLLLLyyyYYYYYYYyY!

[wim DC]

This is mine:

    static boolean canMove(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (grid[i][col] == 'Q') {
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j < grid[i].length ; i--, j++) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }


        return true;
    }

3 for loops:

• Vertical check
  
• diagonal - up left
  
• diagonal - up right

Since I, just like you, fill the field from up to down, there's no need to check down left, down right, or further down than row in the vertical check loop

---------- Post added at 10:06 AM ---------- Previous post was at 09:33 AM ----------

Oh and I actually used a Stack instead of LinkedList / Queue, because if you go back using remove(), the Queue's remove remove's the first item you added,
on a Stack that's the last item which was added. I needed the latter.

[fread]

Quote

Oh and I actually used a Stack instead of LinkedList / Queue, because if you go back using remove(), the Queue's remove remove's the first item you added,
on a Stack that's the last item which was added. I needed the latter.

Well to be honest, I left the remove() method there and tried not to mess with it b/c that was part of his code. When I did it in school we only had to print the board after, so we never used a stack, queue or list.

[wim DC]

Ah, well I used the value that comes out of the Stack to remove the latest added queen again.

import java.awt.*;
import java.util.Stack;

public class QueensEight {
    public static final int MAX_QUEENS = 8;
    static char[][] grid = new char[8][8];
    static Stack<Point> result = new Stack<Point>();
    static int queensPlaced = 0;

    public static void main(String[] args) {
        solve(0);
        printResult();
    }

    static boolean solve(int row) {
        for (int col = 0; col < grid[row].length && queensPlaced != MAX_QUEENS; col++) {
            if (isLegalPosition(row, col)) {
                addToResult(row, col);
                printGrid();
                if (queensPlaced != MAX_QUEENS && !solve(row + 1)) {
                    removeFromResult();
                }
            }
        }

        return queensPlaced == MAX_QUEENS;
    }

    private static void printGrid() {
        for (char[] row : grid) {
            for (char character : row) {
                System.out.print("  ");
                System.out.print(character == 'Q' ? 'Q' : '_');
                System.out.print("  ");
            }
            System.out.println("\n");
        }
        System.out.println("****************\n****************");
    }

    static boolean isLegalPosition(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (grid[i][col] == 'Q') {
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }
        for (int i = row, j = col; i >= 0 && j < grid[i].length; i--, j++) {
            if (grid[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    static void addToResult(int row, int col) {
        result.add(new Point(row, col));
        grid[row][col] = 'Q';         
        queensPlaced++;
    }

    static void removeFromResult() {
        Point point = result.pop();
        grid[point.x][point.y] = ' ';
        queensPlaced--;
    }

    static void printResult() {
        while (!(result.isEmpty())) {
            Point move = result.pop();
            System.out.println("[" + move.x + ", " + move.y + "]");
        }
    }
}

[fread]

A lot of output. Very helpful for debugging. I did that as well, in my original C version and while fixing his. Good Job :thumbup1:

[wim DC]

Found a shorter canMove() --(isLegalPosition() in my code)

    static boolean isLegalPosition(int row, int col) {
        for (Point point : result) {
            if(point.x == row || point.y == col){
                return false;
            }
            if(Math.abs(point.x - row) == Math.abs(point.y-col)){
                return false;
            }
        }


        return true;
    }

Notes:

• My result stores Point objects (x,y) of the previously placed queens.

• The 2nd if checks diagonals.