Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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;
- 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
- break;
- }
- }
- // check if a queen was placed. Do backtracking here!
- if(! success) {
- // System.out.println("failure");
- }
- }
- p(grid);
- }
- 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;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement