Prison Break

Alfie was a prisoner in mythland. Though Alfie was a witty and intelligent guy.He was confident of escaping prison.After few days of observation,He figured out that the prison consists of ($N\times N$) cells.i.e The shape of prison was ($N\times N$) matrix. Few of the cells of the prison contained motion detectors.So Alfie planned that while escaping the prison he will avoid those cells containing motion detectors.Yet before executing his plan,Alfie wants to know the total number of unique possible paths which he can take to escape the prison.Initially Alfie is in cell
($1,1$) while the exit of the cell ($N,N$).

note:->Alfie can move in all four direction{ if his current location is ($X,Y$), he can move to either
($X+1,Y$), ($X-1,Y$), ($X,Y+1$), ($X,Y-1$) }. If the first cell ($1,1$) and the last cell($N,N$) contain motion detectors,then Alfie can't break out of the prison.

Example:

Input:  n = 4, arr = {{0, 1, 1, 0}, {0, 0, 1, 0}, {0, 0, 0, 0}, {0, 1, 1, 0}}
Output: 2

Approach

C++

#include <bits/stdc++.h>
using namespace std;

const int N = 22;

int a[N][N];

bool vis[N][N];

//all four directions
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
int ans, n;

void dfs(int i, int j)
{

    //mark as visited
    vis[i][j] = 1;

    //if we reach to the destination
    if (i == n && j == n)
        ans++;

    for (int z = 0; z < 4; z++)
    {
        int x = i + dx[z], y = j + dy[z];

        //check for valid cell
        if (x >= 1 && x <= n and y >= 1 && y <= n)
        {

            //if not visited and value is 0
            //then call for dfs
            if (!a[x][y] and !vis[x][y])
                dfs(x, y);
        }
    }

    //mark as unvisited (backtrack)
    vis[i][j] = 0;
}

int main()
{

    ans = 0;

    n = 4;
    vector<vector<int>> arr = {{0, 1, 1, 0},
                               {0, 0, 1, 0},
                               {0, 0, 0, 0},
                               {0, 1, 1, 0}};

    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            a[i][j] = arr[i - 1][j - 1];
        }
    }
    dfs(1, 1);

    cout << ans << "\n";

    return 0;
}

Implement an efficient sudoku solver

Sudoku is a puzzle where you're given a partially-filled 9 by 9 grid with digits. The objective is to fill the grid with the constraint that every row, column, and box (3 by 3 subgrid) must contain all of the digits from 1 to 9.

Implement an efficient sudoku solver.

Example:

Input:  {{0, 9, 0, 0, 0, 0, 8, 5, 3}, {0, 0, 0, 8, 0, 0, 0, 0, 4}, {0, 0, 8, 2, 0, 3, 0, 6, 9}, {5, 7, 4, 0, 0, 2, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 9, 0, 0, 6, 3, 7}, {9, 4, 0, 1, 0, 8, 5, 0, 0}, {7, 0, 0, 0, 0, 6, 0, 0, 0}, {6, 8, 2, 0, 0, 0, 0, 9, 0}}

Output:

-------------------------------------
 2 | 9 | 7 | 6 | 1 | 4 | 8 | 5 | 3 |    
-------------------------------------
 1 | 3 | 6 | 8 | 5 | 9 | 7 | 2 | 4 |
-------------------------------------
 4 | 5 | 8 | 2 | 7 | 3 | 1 | 6 | 9 |
-------------------------------------
 5 | 7 | 4 | 3 | 6 | 2 | 9 | 1 | 8 |
-------------------------------------
 3 | 6 | 9 | 7 | 8 | 1 | 2 | 4 | 5 |
-------------------------------------
 8 | 2 | 1 | 9 | 4 | 5 | 6 | 3 | 7 |
-------------------------------------
 9 | 4 | 3 | 1 | 2 | 8 | 5 | 7 | 6 |
-------------------------------------
 7 | 1 | 5 | 4 | 9 | 6 | 3 | 8 | 2 |
-------------------------------------
 6 | 8 | 2 | 5 | 3 | 7 | 4 | 9 | 1 |
-------------------------------------

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

#define LINE "|"
#define NEWROW "-------------------------------------"

// Prints the Soduko grid
void printGrid(int grid[9][9])
{
    for (int i = 0; i < 9; i++)
    {
        cout << "    \n";
        cout << NEWROW << endl;
        for (int j = 0; j < 9; j++)
        {
            cout << " ";

            //empty cell of the grid
            if (grid[i][j] == 0)
            {
                cout << " ";
            }

            //otherwise print that
            else
            {
                cout << grid[i][j];
            }
            cout << " ";
            cout << LINE;
        }
    }
    cout << "\n"
         << NEWROW << "\n"
         << "\n";
}

//check for valid row by assigning value to any
//cell
bool isValidRow(int grid[9][9], int row, int num)
{
    for (int col = 0; col < 9; col++)
        if (grid[row][col] == num)
        {
            return true;
        }
    return false;
}

//check for valid col by assigning value  by assigning
//any cell
bool isValidCol(int grid[9][9], int col, int num)
{
    for (int row = 0; row < 9; row++)
        if (grid[row][col] == num)
        {
            return true;
        }
    return false;
}

//check if the box of 3x3 is valid ot not
bool isValidBox(int grid[9][9], int boxStartRow, 
  int boxStartCol, int num)
{
    for (int row = 0; row < 3; row++)
        for (int col = 0; col < 3; col++)
            if (grid[row + boxStartRow][col + boxStartCol] == num)
            {
                return true;
            }
    return false;
}

//check whether it will be legal to assign
// num to the given row,col location.
bool isSafe(int grid[9][9], int row, int col, int num)
{
    // Check if 'num' is not already placed in current row,
    // current column and current 3x3 box
    return !isValidRow(grid, row, num) &&
           !isValidCol(grid, col, num) &&
           !isValidBox(grid, row - row % 3, col - col % 3, num);
}

//check for empty cell
pair<int, int> getEmptyLocation(int grid[9][9])
{
    for (int row = 0; row < 9; row++)
        for (int col = 0; col < 9; col++)
            if (grid[row][col] == 0)
            {
                return make_pair(row, col);
            }
    return make_pair(9, 9);
}

//function to check if we can solve the sudoku
bool solveSudoku(int grid[9][9])
{
    // If the Soduko grid has been filled, we are done
    if (getEmptyLocation(grid) == make_pair(9, 9))
    {
        return true;
    }

    // Get an unassigned Soduko grid location
    std::pair<int, int> row_and_col = getEmptyLocation(grid);
    int row = row_and_col.first;
    int col = row_and_col.second;

    // Consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        //if by placing current value into
        //the current cell is valid then place it
        if (isSafe(grid, row, col, num))
        {
            //assign value to current cell
            grid[row][col] = num;

            //call recursively
            if (solveSudoku(grid))
            {
                return true;
            }
            //backtrack
            grid[row][col] = 0;
        }
    }
    //if not valid then return false;
    return false;
}
int main()
{

    int grid[9][9] = {{0, 9, 0, 0, 0, 0, 8, 5, 3},
                      {0, 0, 0, 8, 0, 0, 0, 0, 4},
                      {0, 0, 8, 2, 0, 3, 0, 6, 9},
                      {5, 7, 4, 0, 0, 2, 0, 0, 0},
                      {0, 0, 0, 0, 0, 0, 0, 0, 0},
                      {0, 0, 0, 9, 0, 0, 6, 3, 7},
                      {9, 4, 0, 1, 0, 8, 5, 0, 0},
                      {7, 0, 0, 0, 0, 6, 0, 0, 0},
                      {6, 8, 2, 0, 0, 0, 0, 9, 0}};

    if (solveSudoku(grid))
    {
        printGrid(grid);
    }
    else
    {
        cout << "No solution exists for the given Soduko\n";
    }

    return 0;
}

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.

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:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

Approach:

C++

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> ans;

bool isValid(vector<string> &curr, int r, int c)
{
    for (int i = r; i >= 0; i--)
    {
        if (curr[i][c] == 'Q')
            return false;
    }
    for (int i = r, j = c; i >= 0 && j >= 0; i--, j--)
    {
        if (curr[i][j] == 'Q')
            return false;
    }
    for (int i = r, j = c; i >= 0 && j < curr.size(); i--, j++)
    {
        if (curr[i][j] == 'Q')
            return false;
    }
    return true;
}

void dfs(vector<string> &curr, int r)
{
    if (curr.size() == r)
    {
        ans.push_back(curr);
        return;
    }
    for (int i = 0; i < curr.size(); i++)
    {
        if (isValid(curr, r, i))
        {
            curr[r][i] = 'Q';
            dfs(curr, r + 1);
            curr[r][i] = '.';
        }
    }
}

vector<vector<string>> solveNQueens(int n)
{
    vector<string> curr(n, string(n, '.'));
    dfs(curr, 0);
    return ans;
}

int main()
{
    int n = 4;

    vector<vector<string>> queens = solveNQueens(n);

    cout << "[";
    for (int i = 0; i < queens.size(); i++)
    {
        cout << "[";
        for (int j = 0; j < queens[i].size(); j++)
        {
            cout << queens[i][j];
            if (j != queens[i].size() - 1)
                cout << ", ";
        }
        cout << "]";
        if (i != queens.size() - 1)
            cout << ", ";
    }
    cout << "]";

    return 0;
}