How to solve the Eight Queens puzzle without recursion?

[kiregad]

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? :)

[gcalvin]

Please post your code here if you want help. I, for one, don't want to follow your links.

-Gary-

[kiregad]

Sure :)

Queens:

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;
    }
}

And Moves:

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();
	}
	
}

I am using php tags because with code tags so much whitespace is generated.