leetcode

commit 0de5f10d9d2131ef67cae00d79600bf3196fb219
parent 3c79695b02706c19e3090b017aa37c29939b7753
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sat, 27 May 2023 18:59:09 -0500

Completed nqueens using dart, backtracking, and recursion

Diffstat:
A
n-queens/n-queens.dart
 | 
65
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 65 insertions(+), 0 deletions(-)
diff --git a/n-queens/n-queens.dart b/n-queens/n-queens.dart
@@ -0,0 +1,65 @@
+//Given a number n return all possible configurations of queens
+//on a chess board such that none can take another assuming they are all on their
+//own teams where the chess board is size n*n. To do this I used 
+//1's to denote places that are reserved by other queens that have been previously placed.
+//Given this I iterated through the current row to find all possible spaces that are not being taken
+//by another queen. If they are safe to place a piece in I did and continued on iterating through the rest 
+//of the rows until either reaching the end or running out of safe spaces to place queens.
+//Then I returned all possible configurations back to my function called nQueenControl. 
+//The purpose of this function was to replace all of the ones with "."'s and return the final strings
+//to the solveNQueens function.
+//Time: 312ms Beats: 25.71%
+//Memory: 151.1MB Beats: 7.14%
+
+class Solution {
+  List<List<String>> solveNQueens(int n) {
+      List<String> init_mat = [];
+      for(int i = 0 ; i < n ; ++i){
+          init_mat.add("."*n);
+      }
+      List<List<String>> ret_list = nQueenControl(init_mat , 0);
+      return ret_list;
+  }
+  List<List<String>> nQueenControl(List<String> matrix, int row){
+      List<List<String>> ret_list = nQueens(matrix , row);
+      for(int i = 0 ; i < ret_list.length ; ++i){
+        for(int x = 0 ; x < ret_list[i].length ; ++x){
+          ret_list[i][x] = ret_list[i][x].replaceAll('1' , '.');
+        }
+      }
+      return ret_list;
+  }
+  List<List<String>> nQueens(List<String> matrix , int row){
+    if(row == matrix.length){
+      return [matrix];
+    }
+    List<List<String>> return_list = [];
+    for(int i = 0 ; i < matrix[row].length ; ++i){
+      if(matrix[row][i] == '1'){
+        continue;
+      }
+      List<String> new_matrix = List.from(matrix);
+      List<String> current_row = matrix[row].split('');
+      current_row[i] = 'Q';
+      new_matrix[row] = current_row.join('');
+      int itr = 1;
+      for(int x = row + 1 ; x < matrix.length ; ++x){
+        List<String> next_row = matrix[x].split('');
+        next_row[i] = '1';
+        if(i - itr >= 0){
+          next_row[i - itr] = '1';
+        }
+        if(i + itr < matrix.length){
+          next_row[i + itr] = '1';
+        }
+        itr += 1;
+        new_matrix[x] = next_row.join('');
+      }
+      List<List<String>> nQu = nQueens(new_matrix , row + 1);
+      for(int i = 0 ; i < nQu.length ; ++i){
+        return_list.add(nQu[i]);
+      }
+    }
+    return return_list;
+  }
+}