Need help with the Eight Queens game

[kiregad]

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

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.

[iluxa]

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

[kiregad]

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

[JosAH]

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

[kiregad]

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

 // 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.

[iluxa]

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

[gcalvin]

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:

    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.

    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.

    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-

[kiregad]

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?

[iluxa]

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

your algorithm should be along these lines:

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

[kiregad]

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

[iluxa]

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

[JosAH]

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

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