Results 1 to 3 of 3
  1. #1
    kiregad is offline Member
    Join Date
    Mar 2010
    Posts
    23
    Rep Power
    0

    Default 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? :)
    Java beginner.

  2. #2
    gcalvin is offline Senior Member
    Join Date
    Mar 2010
    Posts
    953
    Rep Power
    5

    Default

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

    -Gary-

  3. #3
    kiregad is offline Member
    Join Date
    Mar 2010
    Posts
    23
    Rep Power
    0

    Default

    Sure :)

    Queens:

    PHP Code:
    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:

    PHP Code:
    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.
    Java beginner.

Similar Threads

  1. Need help with the Eight Queens game
    By kiregad in forum New To Java
    Replies: 11
    Last Post: 03-26-2010, 06:50 PM
  2. Pruning?? (N-Queens problem)
    By n00neimp0rtant in forum New To Java
    Replies: 1
    Last Post: 02-14-2010, 06:41 AM
  3. recursion and tail-recursion differences
    By OptimusPrime in forum New To Java
    Replies: 2
    Last Post: 12-28-2009, 06:26 PM
  4. N-Puzzle Help!
    By evan42781 in forum New To Java
    Replies: 12
    Last Post: 04-29-2009, 11:34 PM
  5. Need help with Trees...(8-puzzle)
    By ventrue in forum New To Java
    Replies: 2
    Last Post: 03-23-2009, 11:04 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •