Session 16: Back Tracking 3

Original Session

Date: 04 Dec 2024

Topic: Back Tracking

1. Concept: Queens Problem

Program

1. 52. N-Queens II
   1. leetcode link

   class Solution {
   
       int sol;
       public int totalNQueens(int n) {
           
           boolean[][] board = new boolean[n][n];
           func(board, n, 0);
           return sol;
       }
   
       void func(boolean[][] board, int n, int row, char[][] s) {
   
           if (row == n) {
               sol++;
               return;
           }
   
           for (int col = 0; col < n; col ++) {
   
               board[row][col] = true;
   
               if (isValid(board, n, row, col)) {
                   func(board, n, row + 1);
               }
               board[row][col] = false;
           }
           return;
       }
   
       boolean isValid(boolean[][] board, int n, int row, int col) {
   
           for (int i=0; i<n; i++) {
   
               if (i!=row && board[i][col]) {
                   return false;
               }
           }
   
           for (int i=0; i<n; i++) {
   
               if (i!=col && board[row][i]) {
                   return false;
               }
           }
   
           int tr = row + 1;
           int tc = col + 1;
   
           while(tr < n && tc < n) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr ++;
               tc ++;
           }
   
           tr = row - 1;
           tc = col + 1;
   
           while(tr >= 0 && tc < n) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr --;
               tc ++;
           }
   
           tr = row - 1;
           tc = col - 1;
   
           while(tr >= 0 && tc >= 0) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr --;
               tc --;
           }
   
           tr = row + 1;
           tc = col - 1;
   
           while(tr < n && tc >= 0) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr ++;
               tc --;
           }
   
           return true;
       }
   }

2. 51. N-Queens
   1. leetcode link

   class Solution {
   
       List<List<String>> list = new ArrayList();
       public List<List<String>> solveNQueens(int n) {
           
           
           boolean[][] board = new boolean[n][n];
           func(board, n, 0);
           return list;
       }
   
       void func(boolean[][] board, int n, int row) {
   
           if (row == n) {
               list.add(boardToList(board));
               return;
           }
   
           for (int col = 0; col < n; col ++) {
   
               board[row][col] = true;
   
               if (isValid(board, n, row, col)) {
                   func(board, n, row + 1);
               }
               board[row][col] = false;
           }
           return;
       }
   
       boolean isValid(boolean[][] board, int n, int row, int col) {
   
           for (int i=0; i<n; i++) {
   
               if (i!=row && board[i][col]) {
                   return false;
               }
           }
   
           for (int i=0; i<n; i++) {
   
               if (i!=col && board[row][i]) {
                   return false;
               }
           }
   
           int tr = row + 1;
           int tc = col + 1;
   
           while(tr < n && tc < n) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr ++;
               tc ++;
           }
   
           tr = row - 1;
           tc = col + 1;
   
           while(tr >= 0 && tc < n) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr --;
               tc ++;
           }
   
           tr = row - 1;
           tc = col - 1;
   
           while(tr >= 0 && tc >= 0) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr --;
               tc --;
           }
   
           tr = row + 1;
           tc = col - 1;
   
           while(tr < n && tc >= 0) {
   
               if (board[tr][tc]) {
                   return false;
               }
               tr ++;
               tc --;
           }
   
           return true;
       }
   
       List<String> boardToList(boolean[][] board) {
           
           List<String> list = new ArrayList();
           for (int row=0;row<board.length;row++) {
   
               String s = "";
               for (int col=0;col<board[0].length;col++) {
   
                   s+=board[row][col] ? "Q" : ".";
               }   
   
               list.add(s);
           }
   
           return list;
       }
   }