fork(1) download
copy 
  1. /**
  2.  * N Queen Problem Using backtracing(backtracing is achieved by overriting.
  3.  * @author Prateek
  4.  */
  5.  class NQueen {
  6.  
  7. 	int[][] chess;
  8. 	int size;  // matrix is sqaure
  9. 	int[] sol; // contains value of columns
  10.  
  11. 	public NQueen(int[][] matrix){
  12.  
  13. 		this.chess=matrix;
  14. 		this.size = matrix.length;
  15.  
  16. 		this.sol=new int[matrix.length];
  17. 	}
  18.  
  19. 	/**
  20. 	 * Check if Queen can be placed for a given row,col
  21. 	 * @return true if queen can be placed
  22. 	 */
  23. 	private boolean isValidPlacement(int[][] chess, int givenRow , int givenCol) {
  24.  
  25. 		for(int currentRow=0;currentRow < givenRow ; currentRow ++)
  26. 		{
  27. 			//  column check
  28. 			if (sol[currentRow]==givenCol)
  29. 				return false;
  30.  
  31. 			//diagonal check condition
  32. 			if(Math.abs(sol[currentRow ] - givenCol) == Math.abs(currentRow - givenRow))
  33. 				return false;
  34. 		}
  35. 		return true;
  36. 	}
  37.  
  38. 	/**
  39. 	 * Iterates over the a given row , for all columns
  40. 	 * @param chess : input chess board
  41. 	 * @param givenRow 
  42. 	 * @param size : length or breadth of matrix for a N x N matrix
  43. 	 */
  44. 	private void solveNQueen(int chess[][] , int givenRow , int size) {
  45.  
  46. 		for(int currentCol=0;currentCol < size ; currentCol ++)
  47. 		{
  48. 			if(isValidPlacement(chess, givenRow ,  currentCol) == true)
  49. 			{
  50. 				sol[givenRow] = currentCol ;
  51.  
  52.  				if(givenRow == size - 1) // this was the last row , print soln
  53. 					printSolution(sol);
  54.  
  55. 				else  // proceed with next row
  56. 				{
  57. 					int nextRow=givenRow + 1 ;
  58. 					solveNQueen(chess, nextRow, size) ;
  59. 				}
  60. 			}
  61. 		}
  62. 	}
  63.  
  64. 	/*private void printSolution(int[]sol) {
  65. 		int len=sol.length;
  66. 		System.out.println("-------------------------");
  67. 		for(int i=0 ; i  < len ;i++ )
  68. 		{
  69. 			System.out.println(i +"  " + sol[i]);
  70. 		}
  71. 		System.out.println("-------------------------");
  72. 	}*/
  73.  
  74. 	private void printSolution(int[]sol) {
  75. 		System.out.println("-------------------------");
  76. 		for (int i = 0; i < size; i++)
  77. 		{
  78. 			for (int j = 0; j < size; j++) {
  79. 				if(sol[i] == j)
  80. 					System.out.print("1");
  81. 				else
  82. 					System.out.print("0");
  83. 				System.out.print("\t");
  84. 			}
  85.  
  86. 			System.out.println();
  87. 		}
  88. 		System.out.println("-------------------------");
  89. 	}
  90.  
  91.  
  92.  
  93. 	public static void main(String[] args) {
  94. 		int chess[][] = { {0, 0, 0, 0},
  95. 				{0, 0, 0, 0},
  96. 				{0, 0, 0, 0},
  97. 				{0, 0, 0, 0}
  98. 		};
  99.  
  100. 		NQueen obj=new NQueen(chess) ;
  101. 		obj.solveNQueen( chess,  0, chess.length) ;
  102. 	}
  103. }
  104.  
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
-------------------------
0	1	0	0	
0	0	0	1	
1	0	0	0	
0	0	1	0	
-------------------------
-------------------------
0	0	1	0	
1	0	0	0	
0	0	0	1	
0	1	0	0	
-------------------------
https://ideone.com/3EF0vV
language:
Java (12.0.1)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!