# Backtracking: Famous Problems

---
title: Agenda
description:
duration: 300
card_type: cue_card
---

1. N Queen
2. Sudoku
3. Word Break Problem

---
title: Problem 1 N Queen
description:
duration: 600
card_type: cue_card
---

### Problem Statement

Given a N * N chessboards and N Queens Arrange the queens in a way that no queeen can attack the other queens.

N rows => N Queens

Example 1:

Input : N = 1

| Q |
| -------- |

Input : N = 2

Output: Impossible

Explanation:

| Q | - |
| -------- | -------- |
| - | - |

After Placing the first queen, here we cant able to place another queen, which makes it attack each other.

---
title: N Queen Observation
description:
duration: 600
card_type: cue_card
---

Process:
* Place a Queen at a cell
* Check whether the queen attacks any of the other queens.
* If Yes, then dont place it
* Else place the queen
* If there is no arrangement of queen is possible, then prune it.

### Dry Run

For N = 3

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/366/original/upload_80f2a7100f72e76ecf3adfee95d39651.png?1711631164" width="500px">

As we can see that, for N = 3 also, there is no arrangement exist.

Now, lets try with N = 4.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/374/original/upload_13637cb457e68a47dc636b9f19ac59d1.png?1711632544" width="500px">

As we can see that, when we place the Queen on Column 1 on Row 0, there is a possiblity of placing 4 queens in the 4 x 4 matrix.

### Observation

So now to check whether the queen attacks any other queen or not. It becomes a crutial part. If we check all the cells the queen can move, then it will consume more time.

We will place one queen on each row, it may attack on one of the possible ways.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/375/original/upload_2da9812fad1796aba22f098adcaf9129.png?1711632747" width="500px">

Now, lets focus on the Column move. For this, we can create a Hashset, and check whether there is any queen, which is already present or not.

HashSet<Int> cols

Lets focus on Difference Diagonal(top left - bottom right)

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/470/original/upload_d7bd9be48a6e441118d5e1509034ac0f.png?1711651528" width="500px">

Here we get the same value on each diagonal, when we substract col from row.

HashSet<Int> diffDiagonal

Now, Lets focus on the another diagonal (top right - bottom left)

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/471/original/57beca15-7a74-4c91-8ee7-26156a1c0fb1.jpg?1711651670" width="500px">

Here we can notice that, the sum of the row index and col index are same.

HashSet<Int> sumDiagonal

### Pseudo Code

Hashset<int> cols   N
Hashset<int> different diagonal   N
Hashset<int> same diagonal   N
    

bool check (row, col) {
     if(cols. containskey(col)){
          return False;
    }
    elseif(diffdiag.contains key(row - col)) {
          return False;
    }
    elseif(samediag.contains key(row + col)) {
          return False;
    }
    else {
         return True;
    }
}

ans [N][N] ={0}

bool NQueen (row, N){
    if (row == N){
         print(ans);
         return True;
    }
    for(col=0; col < N  ; col++ ){
        if(check(row, col) == True){
            ans[row][col] = 1;
            cols.insert(col);
            sumdiag.insert(row + col);
            diffdiag.insert(row - col);
    
       bool isValid = NQueen(row + 1, N);
           if(isValid){
               return True;
           }
           else{
                 ans[row][col] = 0;
                 cols.insert(col);
                 sumdiag.insert(row + col);
                 diffdiag.insert(row - col);
                 
          }
           
       }
    }
    return False;
 }

### Complexity

**Time Complexity**: O(N!)

**Space Complexity**: O(3N + N + N) = O(N2) = O(N)

---
title: Problem 2 Suduko
description:
duration: 600
card_type: cue_card
---

### Sudoku

You are given an 9x9 board, in which the cells contains numbers from 1 - 9.

You need to check the below conditions,

1.Each row must contain the numbers from 1 to 9 w/o repititions.

2.Each col must contain the numbers from 1 to 9 w/o repititions.

3.Each block of size 3 * 3 should contain all numbers from 1 to 9 w/o repitition.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/457/original/upload_2ea5e7ec30b3969557f5bcc767942458.png?1711650232" width="500px">

### Observation

For Each empty cell, we have 9 choices (1 - 9). After placing a number we need to check whether the particular number is present in the row, col or the belonging 3x3 square.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/458/original/upload_2d58789b02a2d80893bd461ee1c3be75.png?1711650322" width="500px">

### Pseudo Code

boolean sudoku (mat[][], i, j, g){
    if(j == 9){
        i = i+1;
        j = 0;
    }
    if(i == 9){
        return True;
    }
    if(mat[i][j]! = 0){
        if(sudoku(mat, i, j+1, 9)){
            return True;
        }
        else{
           return False;
    
        }
    }
    else{
        for(x = 1; x <= 9; x++){
          if(isValid(mat, i, j, x,g)){
               mat[i][j] = x;
               { do
               if(sudoku(mat, i, j+1, 9)){
                   return True;
               } 
              // undo
              mat[i][j] = 0;   
    
            { 
          }
       }
    }
    return False;
    
 }
                      
                      
boolean isValid(mat, i, j, x, 9){
    for(row = 0; row < 9; row++){
       if(mat[row][j] == x){
           return False;
      }
    }
    for(col = 0; col < 9; col++){
        if(mat[i][col] == x){
             return False;
        }
    }
    i = i - i % 3;
    j = j - j % 3;
    
    for(row = i; row < (i+3); row++){
        for(col = j; col < (j+3); col++      ){
             if(mat[row][col] == x){
                  return False;    
             }
        }
    }
    return True;
}

### Complexity

**Time Complexity**: (N$^2$ * N)
**Space Complexity**: O(N$^2$)

---
title: Problem 3 Word Break
description:
duration: 600
card_type: cue_card
---

### Problem Statement

Given a dictionary of words(strings) (Hashset) and a string A

Check if it is possible to break A into valid words from the dictionary.

Dict = {'i', 'like', 'mango', 'man', 'go'}

A = iamman

A = ilikemango

### Dryrun

Lets the string,
i l i k e m a n g o

Here, we need to create a recursive call, which makes the cuts.

Lets start from the end,
<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/459/original/upload_cc934933a1c7b8646a628fcefdd465d3.png?1711650384" width="500px">

Now lets try breaking on the last position

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/467/original/00bb17c5-a0ad-44c2-bfb3-a6695a494e47.jpg?1711650878" width ="500px">

Here "o" is not present in the dictionary, So we prune the call. Lets move ahead and try with another cut.

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/469/original/f9a984c0-3535-4cca-aae0-76db9bb6dbc0.jpg?1711650970" width = "500px">

As we can see that, "go" is present in our Dictionary.

Then we have two choices, either we can move, or lets make it as a cut itself.

Lets make it as a cut, then try making another cut

Likewise, we can make the cut recusively

<img src="https://d2beiqkhq929f0.cloudfront.net/public_assets/assets/000/069/466/original/8e5049e7-47cf-4c6c-8508-985b4a57a10d.jpg?1711650796" width="400px">

Each recursive Function will return the number of cuts it made