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;
- Moves moves = new Moves();
- 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
- Integer[] move = {i ,j}; // autoboxing
- moves.push(move); // push the move onto the stack
- break;
- }
- // check if a queen was placed. Or if not enough queens have been placed
- if( (! success && j == 7) || (i == 7 && j == 7 && moves.length() < 8)) {
- // System.out.println("failure");
- Integer[] lastMove = moves.pop();
- int lastY = lastMove[0];
- int lastX = lastMove[1];
- grid[lastY][lastX] = 0; // remove the last placed queen
- j = lastX + 1;
- i = lastY;
- // System.out.println("backtracking!");
- }
- }
- }
- p(grid);
- // moves.printMoves();
- }
- 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