# How to solve the Eight Queens puzzle without recursion?

• 03-26-2010, 11:55 PM
How to solve the Eight Queens puzzle without recursion?
I made one class to hold all the moves, so I can easily backtrack with pop(). The push() adds a move to the stack.

Queens: package JEG_SKAL_BLI_PRO; i - Anonymous - gax7trbT - Pastebin.com
Moves: package JEG_SKAL_BLI_PRO; i - Anonymous - A6FpZQ09 - Pastebin.com

I thought I got the logic correct. But when I run the program, it has only placed 7 queens. Does anyone see what is going wrong here? :)
• 03-27-2010, 02:52 AM
gcalvin

-Gary-
• 03-27-2010, 03:30 AM
```package JEG_SKAL_BLI_PRO; import java.util.Scanner; public class Queens {     public static void main(String[] a) {         Scanner in = new Scanner(System.in);         int[][] grid = new int[8][8];         boolean success;               Moves moves = new Moves();       for(int i=0;i < 8;i++) {                         success = false; // initially no queen is placed                                         for(int j=0;j < 8;j++) {                     /* THIS IS FOR DEBUGGING */                     /*  place(i,j,grid,4);                     p(grid);                     String s = in.nextLine();                     place(i,j,grid,0);  */                     if(isLegal(i,j,grid)) {                         place(i,j,grid);                         success = true; // A queen is placed                          Integer[] move = {i ,j};  // autoboxing                         moves.push(move); // push the move onto the stack                         break;                     }                                         // check if a queen was placed. Or if not enough queens have been placed                         if( (! success && j == 7) || (i == 7 && j == 7 && moves.length() < 8)) {                                 // System.out.println("failure");                                 Integer[] lastMove = moves.pop();                                 int lastY = lastMove[0];                                 int lastX = lastMove[1];                                 grid[lastY][lastX] = 0; // remove the last placed queen                                 j = lastX + 1;                                 i = lastY;                                 // System.out.println("backtracking!");                         }                 }         }         p(grid);               // moves.printMoves();     }     public static boolean isLegal(int y, int x, int[][] grid) {             if (isThreatenedVertically(y, x, grid)) return false;         if (isThreatenedHorizontally(y, x, grid)) return false;         if (isThreatenedDiagonally(y, x, grid)) return false;         return true;     }         public static boolean isThreatenedVertically(int y, int x, int[][] grid) {             // check above             for(int i=0;i < y;i++) {                     if(grid[i][x] == 1) return true;             }             // check below             for(int i=y+1;i < grid.length;i++) {                     // if(grid[i][x] == 1) return true;             }             return false;     }         public static boolean isThreatenedHorizontally(int y, int x, int[][] grid) {             // check left             for(int i=0;i < x;i++) {                     if(grid[y][i] == 1) return true;             }             // check right             for(int i=x+1;i < grid.length;i++) {                     if(grid[y][i] == 1) return true;             }             return false;     }         public static boolean isThreatenedDiagonally(int y, int x, int[][] grid) {             // check above and left             int dx = x - 1;             int dy = y - 1;             while(dx >= 0 && dy >= 0) {                     if(grid[dy--][dx--] == 1) return true;             }             // check below and right             dx = x + 1;             dy = y + 1;             while(dx < grid.length && dy < grid.length) {                     if(grid[dy++][dx++] == 1) return true;             }             // check above and right             dx = x + 1;             dy = y - 1;             while(dx < grid.length && dy >= 0) {                     if(grid[dy--][dx++] == 1) return true;             }             // check below and left             dx = x - 1;             dy = y + 1;             while(dx >= 0 && dy < grid.length) {                     if(grid[dy++][dx--] == 1) return true;             }             return false;     }             public static void p(int[][] grid) {         for(int i=0;i < grid.length;i++) {             for(int j=0;j < grid[0].length;j++) {                 System.out.print(grid[i][j]);             }             System.out.println();         }     }     public static void place(int y, int x, int[][] grid) {         grid[y][x] = 1;     }     // for debugging     public static void place(int y, int x, int[][] grid, int i) {             grid[y][x] = i;     } }```
```package JEG_SKAL_BLI_PRO; import java.util.ArrayList; public class Moves {         private ArrayList<Integer[]> list = new ArrayList<Integer[]>();                 public Moves() {                         }                 public Integer[] pop() {                 if(list.size() < 1) return new Integer[]{0, 0}; // empty stack                                 Integer[] lastMove = list.get(list.size()-1);                 list.remove(list.size()-1);                                 return lastMove;                        }                 public void push(Integer[] move) {                 list.add(move);         }                 public void printMoves() {                 for(int i=0;i < list.size();i++) {                         int y = list.get(i)[0];                         int x = list.get(i)[1];                                                 System.out.println((i+1)+": Queen placed at: "+y+","+x);                 }         }                 public int length() {                 return list.size();         }         }```