RecursionAndBacktracking/NQueenProblem.java at main · adv11/RecursionAndBacktracking · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
packageRecursionAndBacktracking;

importjava.util.ArrayList;
importjava.util.List;
importjava.util.Scanner;

/**
 * LeetCode link (59 Hard) : https://leetcode.com/problems/n-queens/
 * The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.
 * Given an integer n, return all distinct solutions to the n-queens puzzle. You may return the answer in any order.
 * Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate
 * a queen and an empty space, respectively.
 *
 * Example 1:
 *
 * Input: n = 4
 * Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 * Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above
 * Example 2:
 *
 * Input: n = 1
 * Output: [["Q"]]
 *
 * Constraints:
 *
 * 1 <= n <= 9
 */
publicclassNQueenProblem {

// Approach 1 : Brute force - taking space TC for searching valid place to place the queen
// This canPlace() method takes extra space as it is taking O(N) for searching on left side upward diagonal
// O(N) time for searching on left side row and similarly O(N) time for searching on left side
// downward diagonal.
// So, we have to reduce this time complexity by using Hashing.
// public static boolean canPlace_bruteForce(int row, int column, char[][] board, int n){
// int duplicateRow = row, duplicateColumn = column;
//
// // checking left side upward diagonal
// while(row>=0 && column>=0){
// if(board[row][column] == 'Q'){
// return false;
// }
// row--;
// column--;
// }
//
// row = duplicateRow;
// column = duplicateColumn;
//
// // checking the left side straight row
// while(column>=0){
// if(board[row][column] == 'Q'){
// return false;
// }
// column--;
// }
//
// column = duplicateColumn;
//
// // checking left side downward diagonal
// while(row<n && column>=0){
// if(board[row][column] == 'Q'){
// return false;
// }
// row++;
// column--;
// }
// return true;
// }
publicstaticvoidsolve(intcolumn, List<List<String>> ans, char[][] board, intn, int[] leftRow, int[] leftLowerDiagonal, int[] leftUpperDiagonal){
// Base case : if col == n then it mean we have filled all the queens
if(column == n){
// creating temporary list for storing the elements of particular row
List<String> ds = newArrayList<>();

// adding characters from board array
for(introw=0 ; row<n ; row++){
Strings = "";
for(intcol=0 ; col<n ; col++){
s += board[row][col];
 }
ds.add(s);
 }

// adding ds list into the final ans list
ans.add(ds);
return;
 }

// recursive call
for(introw=0 ; row<n ; row++){
// checking if we can place queen or not : Brute force approach
// if(canPlace_bruteForce(row, column, board, n)){
// board[row][column] = 'Q'; // place the queen
// solve(column+1, ans, board, n); // call recursion for column+1
// board[row][column] = '.'; // remove the queen (Backtracking step)
// }


// Approach 2 : Optimised using Hashing : Search for valid place in just O(1) time
// Optimised Approach using Hashing
if(leftRow[row] == 0 && leftLowerDiagonal[row+column] == 0 && leftUpperDiagonal[(n-1)+(column-row)] == 0){
// place the queen
board[row][column] = 'Q';

// fill the hash arrays with 1 - means there is a queen
leftRow[row] = 1;
leftLowerDiagonal[row+column] = 1;
leftUpperDiagonal[(n-1)+(column-row)] = 1;

// recursion call for next column
solve(column+1, ans, board, n, leftRow, leftLowerDiagonal, leftUpperDiagonal);

// Backtracking step : empty board and put 0 in hash arrays
board[row][column] = '.';
leftRow[row] = 0;
leftLowerDiagonal[row+column] = 0;
leftUpperDiagonal[(n-1)+(column-row)] = 0;
 }
 }
 }
publicstaticList<List<String>> solveQueens(intn){
List<List<String>> ans = newArrayList<>();
// creating empty board of size n*n
char[][] board = newchar[n][n];
for(introw=0 ; row<n ; row++){
for(intcol=0 ; col<n ; col++){
board[row][col] = '.'; // . means empty space
 }
 }


// Hashing array for left row, left upper diagonal and left lower diagonal
int[] leftRow = newint[n];
int[] leftUpperDiagonal = newint[2*n-1];
int[] leftLowerDiagonal = newint[2*n-1];

// method definition : solve(column, ans, board, n)
solve(0, ans, board, n, leftRow, leftLowerDiagonal, leftUpperDiagonal);
returnans;
 }
publicstaticvoidmain(String[] args) {
Scannersc = newScanner(System.in);
System.out.println("Enter the number of testcases:");
intnumberOfTestcases = sc.nextInt();
while (numberOfTestcases-- > 0){
System.out.println("Enter the dimension of board(N):");
intn = sc.nextInt();

List<List<String>> finalBoard = solveQueens(n);
for(Listlist : finalBoard){
System.out.println(list);
 }
 }
 }
}