Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.util.Scanner;
- import java.io.*;
- public class NQueens {
- public static int boardsize;
- public static final int empty = 0;
- public static final int queen = 1;
- private static int board[][];
- public static Scanner in;
- public static PrintWriter out1;
- public static void main(String args[]) throws IOException{
- String input = null;
- BufferedReader reader = null;
- try {
- File file = new File("sample-file.dat");
- reader = new BufferedReader(new FileReader("in.txt"));
- if((input = reader.readLine()) == null) {}
- } catch (IOException e) {
- e.printStackTrace();
- }finally {
- try {
- reader.close();
- } catch (IOException e) {
- e.printStackTrace();
- }
- }
- //['4' , '1' , '2']
- String[] in = input.split(" ");
- for(String s : in) {
- System.out.println(s);
- }
- //while(s.hasNextInt()) {
- int a = Integer.parseInt(in[0]);
- boardsize = a; //set board size
- int c = Integer.parseInt(in[1]); //row
- int b = Integer.parseInt(in[2]); //col
- board = new int[a][a];
- clearBoard();
- /** setQueen(2,2);
- System.out.println("Testing diag \\ 1,1 " +isUnderAttack(1,1));
- System.out.println("Testing up 2,1 " +isUnderAttack(2,1));
- System.out.println("Testing diag // 3,1 " +isUnderAttack(3,1));
- System.out.println("Testing left 1,2 " +isUnderAttack(1,2));
- System.out.println("Testing right 3,2 " +isUnderAttack(3,2));
- System.out.println("Testing diag // 1,3 " +isUnderAttack(1,3));
- System.out.println("Testing down 2,3 " +isUnderAttack(2,3));
- System.out.println("Testing diag \\ 3,3 " +isUnderAttack(3,3));
- System.out.println("Testing further down 2,4 " +isUnderAttack(2,4));
- System.out.println("Testing further diag \\ 4,4 " +isUnderAttack(4,4));
- System.out.println("Testing further right 4,2 " +isUnderAttack(4,2));
- */
- setQueen(b,c);
- placeQueens(b);
- printQueens();
- }
- //queens1.setQueen(2, 3);
- //queens1.setQueen(1, 2);
- //queens1.displayBoard();
- //System.out.println(queens1.isUnderAttack(1, 2));
- public NQueens() {
- // scan = new Scanner(System.in);
- // int i = scan.nextInt();
- board = new int[boardsize][boardsize];
- }
- public static void clearBoard() {
- int row = board.length;
- int col = board.length;
- for (int y = 0; y < col; y++) {
- for (int x = 0; x < row; x++) {
- board[x][y] = empty;
- }
- }
- }
- public void displayBoard() {
- int row = board.length;
- int col = board.length;
- for (int y = 0; y < row; y++) {
- System.out.println("");
- for (int x = 0; x < col; x++) {
- if (board[y][x] == empty) {
- System.out.print("0");
- } else {
- System.out.print("1");
- }
- }
- }
- }
- public static boolean placeQueens(int column) {
- if (column > boardsize) {
- return true; // base case
- } else {
- boolean queenPlaced = false;
- int row = 1; // number of square in column
- while (!queenPlaced && (row <= boardsize)) {
- // if square can be attacked
- printQueens();
- if (isUnderAttack(row, column)) {
- ++row; // consider next square in column
- } // end if
- else { // place queen and consider next column
- setQueen(row, column);
- queenPlaced = placeQueens(column + 1);
- // if no queen is possible in next column,
- if (!queenPlaced) {
- // backtrack: remove queen placed earlier
- // and try next square in column
- removeQueen(row, column);
- ++row;
- } // end if
- } // end if
- } // end while
- return queenPlaced;
- } // end if
- } // end placeQueens
- private static void setQueen(int row, int column) {
- board[row - 1][column - 1] = 1;
- }
- private static void removeQueen(int row, int column) {
- board[row - 1][column - 1] = empty;
- }
- private static boolean isUnderAttack(int row, int column) {
- int r = row - 1;
- int c = column - 1;
- for (int y = 0; y < board.length; y++) {
- if (board[y][c] == 1) {
- return true;
- }
- }
- r = row - 1;
- c = column - 1;
- for (int x = 0; x < board.length; x++) {
- if (board[r][x] == 1) {
- return true;
- }
- }
- r = row - 1;
- c = column - 1;
- while(r < board.length && c < board.length) {
- if (board[r][c] == 1) {
- return true;
- }
- r++;
- c++;
- }
- r = row - 1;
- c = column - 1;
- while(r < board.length && c >= 0) {
- if (board[r][c] == 1) {
- return true;
- }
- r++;
- c--;
- }
- r = row - 1;
- c = column - 1;
- while(r >= 0 && c < board.length) {
- if (board[r][c] == 1) {
- return true;
- }
- r--;
- c++;
- }
- r = row - 1;
- c = column - 1;
- while(r >= 0 && c >= 0) {
- if (board[r][c] == 1) {
- return true;
- }
- r--;
- c--;
- }
- return false;
- }
- public static void printQueens() {
- String result = "";
- for(int x = 0; x < board.length; x++) {
- for(int y = 0; y < board.length; y++) {
- if (board[x][y]==0 ) // no queen
- {
- result += ".";
- }
- else //queen
- result += "Q";
- }
- result += "\n";
- }
- System.out.println(result);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement