Advertisement
Guest User

Untitled

a guest
Oct 17th, 2017
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.84 KB | None | 0 0
  1. import java.io.*; // import for in and out files
  2. import java.util.Scanner; // scanner to input files
  3. import java.util.*;
  4.  
  5. public class NQueens{
  6.  
  7. public static int qrow; // row of chessboard
  8. public static int cols; // column of chessboard
  9. public static int[][] board; // boardsize
  10. public static PrintWriter out; // creates files
  11.  
  12.  
  13. public static boolean freeQ(int col, int row, int[][] board){ // row col size check. {
  14. for (int i = 0; i < board.length; i++){
  15. if (board[i][col] == 1){
  16.  
  17. return false;
  18. }
  19. }
  20. for (int i = 0; i < board.length; i++){
  21. for (int j = 0; j < board.length; j++){ // make sure they dont line up with each other.
  22. if (col - row == i - j && board[j][i] == 1){
  23. return false; // if statement is true return queens as false
  24. }
  25. if (row + col == i + j && board[j][i] == 1){
  26. return false;
  27. }
  28. }
  29. }
  30. return true;
  31. } // diagonalzation
  32.  
  33. public static boolean rQueens(int nq, int n){ // recursive part of the NQueens
  34. if (nq == n){
  35. return true;
  36. }
  37. if (nq == qrow){
  38. nq += 1;
  39. }
  40. for (int col = 0; col < n; col++){
  41. if (freeQ(col, nq, board) == true){ // compares all queens and has a backtrack. Make sure its true so it can backtrack correctly
  42. board[nq][col] = 1;
  43. if (rQueens(nq + 1, n) == true){
  44. return true;
  45. }
  46. board[nq][col] = 0;
  47. }
  48. }
  49. return false;
  50. }
  51.  
  52. public static void main(String[] args) throws IOException{ // IO exception for the input and output files.
  53.  
  54. // check number of command line arguments is at least 2
  55. if(args.length < 2){
  56. System.out.println("Usage: java –jar NQueens.jar <input file> <output file>"); // max of two files only
  57. System.exit(1);
  58. }
  59.  
  60. // open files
  61. Scanner in = new Scanner(new File(args[0])); // put in file 1 aka test-input.txt
  62. PrintWriter out = new PrintWriter(new FileWriter(args[1])); // creates file 2 aka test-output.txt
  63.  
  64. // read lines from in, extract and print tokens from each line
  65. while( in.hasNextLine() ){
  66.  
  67.  
  68. String line = in.nextLine(); // reads numbers in the input file. Splits each of the numbers up
  69. String[] token = line.split("\\s+");
  70.  
  71. int boardsize = Integer.parseInt(token[0]); // each of the number arguments 0 , 1 , 2 = first num , sec num , third num.
  72. qrow = Integer.parseInt(token[1]);
  73. int qcols = Integer.parseInt(token[2]);
  74.  
  75. qrow--; // de increments
  76. qcols--;
  77. board = new int[boardsize][boardsize]; // col and row for the board
  78. for (int i = 0; i < boardsize; i++){
  79. for (int j = 0; j < boardsize; j++){
  80. board[i][j] = 0;
  81. }
  82. }
  83. board[qrow][qcols] = 1;
  84.  
  85. if (rQueens(0, boardsize) == true){ // everything under this is like the solution of the nQueens problem.
  86. for (int i = 0; i < boardsize; i++){
  87. for (int j = 0; j < boardsize; j++){
  88. if (board[i][j] == 1){
  89. out.print(Integer.toString(i+1) + " " + Integer.toString(j+1));
  90. out.println();
  91. }
  92. }
  93. }
  94. }
  95. else{
  96. out.println("No Solution");
  97. }
  98. }
  99.  
  100. // close files
  101. in.close();
  102. out.close();
  103.  
  104.  
  105. }
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement