Results 1 to 12 of 12
 03252010, 07:29 PM #1Member
 Join Date
 Mar 2010
 Posts
 23
 Rep Power
 0
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; } }
Java beginner.
 03252010, 07:44 PM #2Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 5
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: yx=2
The second one is also easy: y+x=8
make sure to check the arrayindexoutofbounds properly...
 03262010, 04:19 PM #3Member
 Join Date
 Mar 2010
 Posts
 23
 Rep Power
 0
I think I understand that. But cant get it down in code.
Java beginner.
 03262010, 04:26 PM #4
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,785
 Blog Entries
 7
 Rep Power
 21
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 xy == 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
 03262010, 04:51 PM #5Member
 Join Date
 Mar 2010
 Posts
 23
 Rep Power
 0
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; } } }
Java beginner.
 03262010, 04:59 PM #6Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 5
Java Code:// first diagonal int d = xy; // 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 } }
 03262010, 05:37 PM #7Senior Member
 Join Date
 Mar 2010
 Posts
 952
 Rep Power
 5
One of the challenges of programming in any language is keeping things clear for yourself while translating them into code. Let me suggest rewriting 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; }
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; }
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; }
Hope that helps,
GaryLast edited by gcalvin; 03262010 at 05:41 PM. Reason: oops... I did forget some important code
 03262010, 06:25 PM #8Member
 Join Date
 Mar 2010
 Posts
 23
 Rep Power
 0
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.
 03262010, 07:01 PM #9Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 5
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
 03262010, 07:11 PM #10Member
 Join Date
 Mar 2010
 Posts
 23
 Rep Power
 0
Thats recursion. Havent gotten that far in java yet. Other options? :p
Java beginner.
 03262010, 07:28 PM #11Senior Member
 Join Date
 Mar 2010
 Posts
 266
 Rep Power
 5
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 1D array of where your queens are, go up the array when backtracking and attempt to advance the queen further from the place she's at already...
 03262010, 07:50 PM #12
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 13,785
 Blog Entries
 7
 Rep Power
 21
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+ip] == 0) { x[i+8]= x[p]= i+1; x[16+i+p]++; x[38+ip]++; s(x, p+1); x[i+8]= 0; x[16+i+p]; x[38+ip]; } } public static void main(String[] args) { s(new int[46], 0); } }
Jos ;)
Similar Threads

Implementing "Game Over" in Minesweeper game based on Gridworld framework.
By JFlash in forum New To JavaReplies: 2Last Post: 08052010, 05:49 AM 
Pruning?? (NQueens problem)
By n00neimp0rtant in forum New To JavaReplies: 1Last Post: 02142010, 07:41 AM 
Game 21
By aRTx in forum Advanced JavaReplies: 3Last Post: 04042009, 01:33 AM 
2D strategy game or 2D war game
By led1433 in forum Java 2DReplies: 5Last Post: 02102009, 07:00 AM 
game
By amith in forum AWT / SwingReplies: 0Last Post: 05192008, 06:16 PM
Bookmarks