#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2005
    Posts
    219
    Rep Power
    9

    N-queens problem (stack overflowing)


    Hey guys. I have this program which is the infamous N-Queens problem. I think it works, but I keep getting a stack over flow error. If anyone could help me figure out why I would appreciate it. I also would like any comments which could make my code more effecient and such
    Code:
    import javax.swing.*;
    
    class nQueens {
      static int  n = 0;
      static int solutions = 0;
    
      static boolean safe(int row, int column, int[] board) {
    //  Check whether it is safe to place a queen at row, column;
    //    i.e., is board[column]=row a safe configuration?
          for (int i=1; i<column; i++) {
             if (board[column-i] == row || board[column-i] == row-i || board[column-i] == row+i) {
                return false;
             }
          }
          return true;
       }
    
       static void place(int column, int[] board) {
    //  Place a queen in all safe positions of column c,
    //  then try placing a queen in the next column.
    //  If a position in column N is safe, print the board.
          for (int row = 1; row <= n; row++) {
             board[column] = row;
             if (safe(row, column, board)) {
                if (column==n) solutions++; // we have a solution
                else place(column++, board);   // try next column
             }
             board[column] = 0;           // unrecord that a queen was placed
          }
       }
    
       public static void main(String[] args) {
          System.out.println("nQueens loaded");
          n = Integer.parseInt(JOptionPane.showInputDialog("Enter in n "));
          try {          // override default from command line argument if any
             n = Integer.parseInt(args[0]);
          } catch (ArrayIndexOutOfBoundsException e) {
          } catch (NumberFormatException e) {
          }
          System.out.println("nQueens: N=" + n);
          int[] board = new int[n+1];  // N+1 since we need board[1]...board[N]
          place(1, board);
          System.out.println("nQueens: numSolutions=" + solutions);
          System.out.println("nQueens done");
       }
    }
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2005
    Posts
    191
    Rep Power
    82

    place(column++, board) is the problem...


    try place(column+1, board) instead, ie.

    The reason is that column++ is POST-increment, ie increment column AFTER the method call. I guess ++column would work OK too!

    Code:
    static void place(int column, int[] board) {
    //  Place a queen in all safe positions of column c,
    //  then try placing a queen in the next column.
    //  If a position in column N is safe, print the board.
          for (int row = 1; row <= n; row++) {
             board[column] = row;
             System.out.println("place:  row = " + row + ", column = " + column);
             if (safe(row, column, board)) {
                if (column==n) solutions++; // we have a solution
                else place(column+1, board);   // try next column
             }
             board[column] = 0;           // unrecord that a queen was placed
          }
       }
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Sep 2005
    Posts
    219
    Rep Power
    9
    is this a good way to do it?

IMN logo majestic logo threadwatch logo seochat tools logo