Advertisement
Guest User

Untitled

a guest
Oct 16th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 6.40 KB | None | 0 0
  1. import java.util.Scanner;
  2. import java.io.*;
  3.  
  4. public class NQueens {
  5. public static int boardsize;
  6. public static final int empty = 0;
  7. public static final int queen = 1;
  8. private static int board[][];
  9.  
  10. public static Scanner in;
  11. public static PrintWriter out1;
  12.  
  13. public static void main(String args[]) throws IOException{
  14. String input = null;
  15. BufferedReader reader = null;
  16.  
  17. try {
  18. File file = new File("sample-file.dat");
  19. reader = new BufferedReader(new FileReader("in.txt"));
  20.  
  21. if((input = reader.readLine()) == null) {}
  22.  
  23. } catch (IOException e) {
  24. e.printStackTrace();
  25. }finally {
  26. try {
  27. reader.close();
  28. } catch (IOException e) {
  29. e.printStackTrace();
  30. }
  31. }
  32.  
  33. //['4' , '1' , '2']
  34. String[] in = input.split(" ");
  35. for(String s : in) {
  36. System.out.println(s);
  37. }
  38.  
  39. //while(s.hasNextInt()) {
  40. int a = Integer.parseInt(in[0]);
  41. boardsize = a; //set board size
  42. int c = Integer.parseInt(in[1]); //row
  43. int b = Integer.parseInt(in[2]); //col
  44. board = new int[a][a];
  45. clearBoard();
  46. /** setQueen(2,2);
  47. System.out.println("Testing diag \\ 1,1 " +isUnderAttack(1,1));
  48. System.out.println("Testing up 2,1 " +isUnderAttack(2,1));
  49. System.out.println("Testing diag // 3,1 " +isUnderAttack(3,1));
  50. System.out.println("Testing left 1,2 " +isUnderAttack(1,2));
  51. System.out.println("Testing right 3,2 " +isUnderAttack(3,2));
  52. System.out.println("Testing diag // 1,3 " +isUnderAttack(1,3));
  53. System.out.println("Testing down 2,3 " +isUnderAttack(2,3));
  54. System.out.println("Testing diag \\ 3,3 " +isUnderAttack(3,3));
  55. System.out.println("Testing further down 2,4 " +isUnderAttack(2,4));
  56. System.out.println("Testing further diag \\ 4,4 " +isUnderAttack(4,4));
  57. System.out.println("Testing further right 4,2 " +isUnderAttack(4,2));
  58. */
  59. setQueen(b,c);
  60.  
  61. placeQueens(b);
  62. printQueens();
  63.  
  64.  
  65. }
  66.  
  67.  
  68. //queens1.setQueen(2, 3);
  69. //queens1.setQueen(1, 2);
  70. //queens1.displayBoard();
  71. //System.out.println(queens1.isUnderAttack(1, 2));
  72.  
  73. public NQueens() {
  74. // scan = new Scanner(System.in);
  75. // int i = scan.nextInt();
  76.  
  77. board = new int[boardsize][boardsize];
  78. }
  79.  
  80. public static void clearBoard() {
  81.  
  82. int row = board.length;
  83. int col = board.length;
  84.  
  85. for (int y = 0; y < col; y++) {
  86. for (int x = 0; x < row; x++) {
  87. board[x][y] = empty;
  88. }
  89. }
  90.  
  91. }
  92.  
  93. public void displayBoard() {
  94.  
  95. int row = board.length;
  96. int col = board.length;
  97.  
  98. for (int y = 0; y < row; y++) {
  99. System.out.println("");
  100. for (int x = 0; x < col; x++) {
  101. if (board[y][x] == empty) {
  102. System.out.print("0");
  103. } else {
  104. System.out.print("1");
  105. }
  106. }
  107. }
  108. }
  109.  
  110. public static boolean placeQueens(int column) {
  111. if (column > boardsize) {
  112. return true; // base case
  113. } else {
  114. boolean queenPlaced = false;
  115. int row = 1; // number of square in column
  116. while (!queenPlaced && (row <= boardsize)) {
  117. // if square can be attacked
  118. printQueens();
  119. if (isUnderAttack(row, column)) {
  120. ++row; // consider next square in column
  121. } // end if
  122. else { // place queen and consider next column
  123. setQueen(row, column);
  124. queenPlaced = placeQueens(column + 1);
  125. // if no queen is possible in next column,
  126. if (!queenPlaced) {
  127. // backtrack: remove queen placed earlier
  128. // and try next square in column
  129. removeQueen(row, column);
  130. ++row;
  131. } // end if
  132. } // end if
  133. } // end while
  134. return queenPlaced;
  135. } // end if
  136. } // end placeQueens
  137.  
  138. private static void setQueen(int row, int column) {
  139. board[row - 1][column - 1] = 1;
  140. }
  141.  
  142. private static void removeQueen(int row, int column) {
  143. board[row - 1][column - 1] = empty;
  144. }
  145.  
  146. private static boolean isUnderAttack(int row, int column) {
  147. int r = row - 1;
  148. int c = column - 1;
  149.  
  150. for (int y = 0; y < board.length; y++) {
  151. if (board[y][c] == 1) {
  152. return true;
  153. }
  154. }
  155.  
  156. r = row - 1;
  157. c = column - 1;
  158. for (int x = 0; x < board.length; x++) {
  159. if (board[r][x] == 1) {
  160. return true;
  161. }
  162. }
  163.  
  164. r = row - 1;
  165. c = column - 1;
  166. while(r < board.length && c < board.length) {
  167. if (board[r][c] == 1) {
  168. return true;
  169. }
  170. r++;
  171. c++;
  172. }
  173.  
  174. r = row - 1;
  175. c = column - 1;
  176. while(r < board.length && c >= 0) {
  177. if (board[r][c] == 1) {
  178. return true;
  179. }
  180. r++;
  181. c--;
  182. }
  183.  
  184. r = row - 1;
  185. c = column - 1;
  186. while(r >= 0 && c < board.length) {
  187. if (board[r][c] == 1) {
  188. return true;
  189. }
  190. r--;
  191. c++;
  192. }
  193.  
  194. r = row - 1;
  195. c = column - 1;
  196. while(r >= 0 && c >= 0) {
  197. if (board[r][c] == 1) {
  198. return true;
  199. }
  200. r--;
  201. c--;
  202. }
  203. return false;
  204. }
  205.  
  206. public static void printQueens() {
  207. String result = "";
  208. for(int x = 0; x < board.length; x++) {
  209. for(int y = 0; y < board.length; y++) {
  210. if (board[x][y]==0 ) // no queen
  211. {
  212. result += ".";
  213. }
  214. else //queen
  215. result += "Q";
  216. }
  217. result += "\n";
  218. }
  219. System.out.println(result);
  220. }
  221. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement