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

    Default Need help with the Eight Queens game

    I cant wrap my head around to find a way to check all possible diagonals.
    I recently started java programming, så no smart or clever solutions please. I have to understand the code :)

    PHP Code:
    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];
    
    		for(int i=0;i < 8;i++) {
    
    				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);
    						break;
    					}
    				}
    		}
    		p(grid);
    	}
    
    	public static boolean isLegal(int y, int x, int[][] grid) {
    		// check that column
    		for(int i=0;i < grid[0].length;i++) {
    			if(grid[y][i] == 1)
    				return false;
    		}
    
    		// check that row
    		for(int i=0;i < grid.length;i++) {
    			if(grid[i][x] == 1)
    				return false;
    		}
    
    		// check diagonally here
    
    		return true;
    	}
    
    	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;
    	}
    }
    I used the php tag, because the code tag generated so much space between the code lines.
    Java beginner.

  2. #2
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Think of what diagonal's indices look like.

    Suppose your Queen is at [3,5]. Then one diagonal is
    [0,2] [1,3] [2,4] [3,5] [4,6] [5,7]

    And the other is
    [1,7] [2,6] [3,5] [4,4] [5,3] [6,2] [7,1]

    The first one is easy: y-x=2
    The second one is also easy: y+x=8

    make sure to check the array-index-out-of-bounds properly...

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

    Default

    I think I understand that. But cant get it down in code.
    Java beginner.

  4. #4
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by kiregad View Post
    I think I understand that. But cant get it down in code.
    Two points (x,y) and (x', y') are on the same row iff y == y'; they're on the same column iff x == x'; they're on the same 'upgoing' diagonal iff x-y == x'-y' and they're on the same 'downgoing' diagonal iff x+y == x'+y'. Also see the previous example posted here.

    kind regards,

    Jos

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

    Default

    My problem is that I cant see how this works inside my head. And then I cant write any code for it.

    PHP Code:
     // check diagonally here
            for(int i=0;i < grid.length;i++) {
            	for(int j=0;j < grid.length;j++) {
            		if(x+y == i+j && grid[i][j] == 1) {
            			System.out.println("lal");
            			return false;
            			
            		}
            	}
            }
    I came up with this, but did not work.
    Java beginner.

  6. #6
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Java Code:
    // first diagonal
    int d = x-y;
    // in my example, d = -2
    for (i = 0; i < grid.length; i ++) {
      int j = i - d;
      if (j >= 0 && j < grid.length) {
        // then grid [i][j] is on the diagonal
      }
    }
    
    // second diagonal
    int d = x+y;
    // in my example, d = 8
    for (i = 0; i < grid.length; i ++) {
      int j = d - i;
      if (j >= 0 && j < grid.length) {
        // then grid [i][j] is on the diagonal
      }
    }

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

    Default

    One of the challenges of programming in any language is keeping things clear for yourself while translating them into code. Let me suggest re-writing your isLegal() method this way:
    Java Code:
        public static boolean isLegal(int y, int x, int[][] grid) {
            if (isThreatenedVertically(int y, int x, int[][] grid)) return false; 
            if (isThreatenedHorizontally(int y, int x, int[][] grid)) return false; 
            if (isThreatenedDiagonally(int y, int x, int[][] grid)) return false; 
            return true; 
        }
    (I would also rename "isLegal" to "isSafe" as I think it's clearer and more accurate, but that is a quibble.)

    Now you have three more methods to write, but I think each of them is simpler and clearer, because each "isThreatened...()" method is easy to understand.
    Java Code:
        public static boolean isThreatenedVertically(int y, int x, int[][] grid) {
            // check above
            for (int i = 0; i < y; i++) {
                if (grid[x][i] == 1) return true;
            }
            // check below
            for (int i = y + 1; i < grid.length; i++) {
                if (grid[x][i] == 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[i][y] == 1) return true;
            }
            // check right
            for (int i = x + 1; i < grid.length; i++) {
                if (grid[i][y] == 1) return true;
            }
            return false;
        }
    Checking diagonally is still tricky, but at least clearer now.
    Java Code:
        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[dx--][dy--] == 1) return true;
            }
            // check below and right
            dx = x + 1;
            dy = y + 1;
            while (dx < grid.length && dy < grid.length) {
                if (grid[dx++][dy++] == 1) return true;
            }
            // check above and right
            dx = x + 1;
            dy = y - 1;
            while (dx < grid.length && dy > 0) {
                if (grid[dx++][dy--] == 1) return true;
            }
            // check below and left
            dx = x - 1;
            dy = y + 1;
            while (dx > 0 && dy < grid.length) {
                if (grid[dx--][dy++] == 1) return true;
            }
            return false;
        }
    (I haven't tested this, but if I've made mistakes they should be easy to find.)

    Hope that helps,

    -Gary-
    Last edited by gcalvin; 03-26-2010 at 04:41 PM. Reason: oops... I did forget some important code

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

    Default

    Java | package JEG_SKAL_BLI_PRO; i - Anonymous - EfpChPFz - Pastebin.com

    I followed your advice. Changed some code yes.

    But now another exciting problem remains. How can I bruteforce a solution? I want to use the easiest solution first, and I think that is backtracking?

    So when no cell are free at some point, how do I backtrack? Must I save all previous step in an array?
    Java beginner.

  9. #9
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    oh, that's a whole different questions isn't it :)

    your algorithm should be along these lines:

    Java Code:
    putQueens (Grid, rowNumber):
      if rowNumber >= Grid.size:
        return true
      
      int [] columns = findAllPlacesToPutQueenOnRow (Grid, rowNumber)
    
      for each int column in columns:
        Grid.setQueenAt (rowNumber, column)
        queenPut = putQueens (Grid, rowNumber + 1)
        if (!queenPut): 
          // this means with the current setting, there's now way to put queens, 
          //so try another location at this row
          Grid.removeQueenAt (rowNumber, column)
        else:
          //if we're here, all queens were successfully put!
          return true
         
      // if we're here, that means there was no column to put the queen
      // at the current row - so the previous queen was wrong...
      return false

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

    Default

    Thats recursion. Havent gotten that far in java yet. Other options? :p
    Java beginner.

  11. #11
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Heh.

    Well, as a Law #42 of Computer Science, whatever can be done with recursion can also be done without recursion, so there you go :)

    It would be harder though... You should indeed keep a 1-D array of where your queens are, go up the array when back-tracking and attempt to advance the queen further from the place she's at already...

  12. #12
    JosAH's Avatar
    JosAH is online now Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,457
    Blog Entries
    7
    Rep Power
    20

    Default

    Java still is a sissy language when it comes to some real hard core obfuscation. C or C++ are much better at that:

    Java Code:
    public class Q8 {
    
    	private static void p(int[] x) {
    	
    		StringBuilder sb= new StringBuilder();
    		
    		for (int i= 0; i < 8; i++) {
    			sb.append("........").setCharAt(x[i]-1, '*');
    			System.out.println(sb);
    			sb.setLength(0);
    		}
    		System.out.println();
    		System.out.println();
    	}
    
    	private static void s(int[] x, int p) {
    		
    		if ( p == 8)
    			p(x);
    		else
    			for (int i= 0; i < 8; i++)
    				if (x[i+8]+x[16+i+p]+x[38+i-p] == 0) {
    					x[i+8]= x[p]= i+1; x[16+i+p]++; x[38+i-p]++;
    					s(x, p+1);
    					x[i+8]= 0; x[16+i+p]--; x[38+i-p]--;
    				}
    	}
    	
    	public static void main(String[] args) {
    		
    		s(new int[46], 0);
    	}
    }
    kind regards,

    Jos ;-)

Similar Threads

  1. Replies: 2
    Last Post: 08-05-2010, 04:49 AM
  2. Pruning?? (N-Queens problem)
    By n00neimp0rtant in forum New To Java
    Replies: 1
    Last Post: 02-14-2010, 06:41 AM
  3. Game 21
    By aRTx in forum Advanced Java
    Replies: 3
    Last Post: 04-04-2009, 12:33 AM
  4. 2D strategy game or 2D war game
    By led1433 in forum Java 2D
    Replies: 5
    Last Post: 02-10-2009, 06:00 AM
  5. game
    By amith in forum AWT / Swing
    Replies: 0
    Last Post: 05-19-2008, 05:16 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
  •