2 replies to this topic

[chili5]

I've been playing around with the N queens problem and came up with a recursive algorithm that solves the N queens problem.

Basically I place a queen on a square, go to the next row and try to place a queen on that square, if there is a queen on the same row, column or diagonal as the square I am trying to put a queen on, I go to the next column. If I get to the end of the row without placing a queen, I go back a row and remove a queen and try to put it somewhere else.

This works and isn't very complicated to code, my solution is:

package ss12;

/**

 *

 * @author James

 */

public class e7 {

    public static int[] DX = {1,1,-1,-1};

    public static int[] DY = {-1,1,1,-1};


    public static void main(String[] args) {

        char[][] arcQueens = new char[8][8];

        for (int i=0;i<8;i++) {

            for (int x=0;x<8;x++) {

                arcQueens[i][x] = '.';

            }

        }

        

        if(tryQueen(arcQueens,8,0)) {

            display(8,arcQueens);

        }

    }


    public static boolean tryQueen(char[][] arcQueens, int nSize, int nRow) {

        if (nRow >= nSize) {

            return true; // we have gotten to the last row so stop

        }

        boolean sol;


        for (int col=0;col<nSize;col++) {

            if (!checkConflict(arcQueens,nSize,nRow,col)) {

                arcQueens[nRow][col] = 'q';

                sol = tryQueen(arcQueens,nSize,nRow+1);

                if (sol) {

                    return true; // we were successfully able to place a piece

                } else {

                    arcQueens[nRow][col] = '.'; // an error has occured so don't place queen

                }

            }

            

            

        }


        return false;

    }


    public static boolean checkConflict(char[][] arcBoard, int nSize, int nRow, int nCol) {

        // check row for a queen

        // check col for a queen

        // check diagonal for a queen

        for (int i=0;i<nSize;i++) {

            if (arcBoard[nRow][i] == 'q') {

                return true; // there is a queen in the same row as the piece we tried to place

            }

        }

        

        for (int i=0;i<nSize;i++) {

            if (arcBoard[i][nCol] == 'q') {

                return true;// there is a queen in the same col as the piece we tried to place

            }

        }


        // check if there is a conflict on a diagonal

        for (int nDir=0;nDir<4;nDir++) {

            if (isDiagonalConflict(arcBoard,nDir,nRow,nCol)) {

                return true;

            }

        }

        

        return false;

    }

    

    public static void display(int nSize, char[][] arcBoard) {

        for (int i=0;i<nSize;i++) {

            for (int x=0;x<nSize;x++) {

                System.out.print(arcBoard[i][x] + " ");

            }

            System.out.println();

        }

    }


    public static boolean isDiagonalConflict(char[][] arcBoard, int nDir, int x, int y) {

        if(x < 0 || x >= arcBoard.length || y < 0 || y >= arcBoard[0].length) {

            return false;

        }


        if (arcBoard[x][y] == 'q') {

            return true;

        }


        return isDiagonalConflict(arcBoard,nDir,x+DX[nDir],y+DY[nDir]);

    }


}

This gives me one solution, but I'm completely stuck as to how I can generate all solutions for this problem. If someone can give me a pointer for something that can help, that would be great. :) I was maybe thinking it has something to do with graphs? I know how backtracking works but I don't get how to count all solutions for some problem?

Any suggestions would be great. Thanks!

[WingedPanther]

What I would do (completely different) is use a variable to keep track of the row I'm trying to place, an array to keep track of the position of the queen in each row, and a counter for filled positions.

For the outer loop (cause I don't like recursion if I can avoid it), use WHILE (array[0]<9) as that means you haven't advanced the first queen off the row. If you are working on array[7] and successfully place the queen, you increment your counter, and continue trying positions.

You may be able to get away with a single WHILE, now that I think about it.

[dumisan]

There are 2 kind of backtraking algorithms the ones you used that gives only 1 solution(the first on to be found) and there are some that after geting a solution go back a step and try to build up an other solution.
Works like that let's say your algorithm creates a solution and print it then goes back a row and trys to make a new solution if it can;t be done goes back to the next row so on ....
But there are some other ways to deal with this problem. you don;t need a square for that.
Here is an implementation that gives all the solutions useing regular arrays,

 System.out.println("give n");

    java.util.Scanner in = new java.util.Scanner(System.in);

    int n = in.nextInt();

    in.close();

    if((n==2)||(n==3)) System.out.println("The problem have no solutions");

    else {

    int sp = 1;

    int[] x = new int[n];

    int k = 0;

    x[0] = 0;

    while (k >= 0) {

        x[k] = x[k] + 1;

        if (x[k] > n) {  

            k = k - 1; 

        } else {

            sp = 1;

            for (int i = 0; i <= k-1; i++)

                if ((x[i] == x[k])||(Math.abs(x[k]-x[i])==Math.abs(k-i)))

                    sp = 0;

            if (sp == 1) {

                if (k == n-1 ) {

                    for (int i = 0; i < n; i++) {

                        System.out.print(x[i]);

                    } //end of the for

                    System.out.println();

                } // if (k==n-1)

                else {

                    k = k + 1;

                    x[k] = 0;

                    } // else from if(k==n)

            } //if(sp==1)

        } // else from if(x[k]==n)

    } //end of the while

    }//end of if n==2 || n==3

well this involves a bit of math :D