Thread: Need help with the Eight Queens game

1. Member
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;
}
}```
I used the php tag, because the code tag generated so much space between the code lines.

2. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
7
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. Member
Join Date
Mar 2010
Posts
23
Rep Power
0
I think I understand that. But cant get it down in code.

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. Member
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;

}
}
}```
I came up with this, but did not work.

6. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
7
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. Senior Member
Join Date
Mar 2010
Posts
952
Rep Power
7
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 05:41 PM. Reason: oops... I did forget some important code

8. Member
Join Date
Mar 2010
Posts
23
Rep Power
0
Java | package JEG_SKAL_BLI_PRO; i - Anonymous - EfpChPFz - Pastebin.com

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?

9. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
7
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. Member
Join Date
Mar 2010
Posts
23
Rep Power
0
Thats recursion. Havent gotten that far in java yet. Other options? :p

11. Senior Member
Join Date
Mar 2010
Posts
266
Rep Power
7
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. 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 ;-)

Posting Permissions

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