nQueens

The challenge of arranging n queens on a n × n chessboard so that no two queens attack one another is known as the "n-queens puzzle."

Return every unique solution to the n-queens puzzle given an integer n. The answer can be returned in any sequence.

Every solution has a unique board arrangement for the placement of the n-queens, where 'Q' and '.' stand for a queen and an empty space, respectively.

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

 bool isPlaceAble(vector<string> &board, int row, int col)
    {
        int r = row, c = col;
        while (r >= 0 && c >= 0)
        {
            if (board[r][c] == 'Q')
            {
                return false;
            }
            r--;
            c--;
        }
        r = row;
        c = col;
        while (c >= 0)
        {
            if (board[r][c] == 'Q')
            {
                return false;
            }
            c--;
        }
        r = row;
        c = col;
        while (c >= 0 && r < board.size())
        {
            if (board[r][c] == 'Q')
            {
                return false;
            }
            r++;
            c--;
        }
        r = row;
        c = col;
        return true;
    }
    void func(int pos, vector<vector<string>> &ans, vector<string> &board)
    {
        if (pos == board.size())
        {
            ans.push_back(board);
            return;
        }
        for (int r = 0; r < board.size(); r++)
        {
            if (isPlaceAble(board, r, pos))
            {
                board[r][pos] = 'Q';
                func(pos + 1, ans, board);
                board[r][pos] = '.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n)
    {
        vector<vector<string>> ans;
        vector<string> board(n, string(n, '.'));

        func(0, ans, board);
        return ans;
    }

Sudoku Solver

Create a program that fills in the blank cells in a Sudoku puzzle to solve it. (We all know the rules so not mentioned here)

 bool canFill(vector<vector<char>> &board, char digit, int row, int col)
    {
        for (int i = 0; i < 9; i++)
        {
            if (board[row][i] == digit || board[i][col] == digit)
                return false;
        }

        int sr = (row / 3) * 3;
        int sc = (col / 3) * 3;
        for (int i = sr; i < sr + 3; i++)
        {  
            for (int j = sc; j < sc + 3; j++)
            {
                if (board[i][j] == digit)
                    return false;
            }
        }
        return true;
    }
    bool solve(vector<vector<char>> &board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    for (char d = '1'; d <= '9'; d++)
                    {
                        if (canFill(board, d, i, j))
                        {
                            board[i][j] = d;
                            if (solve(board))
                                return true;
                            else
                                board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }

Word Search

Given a grid of n x m dimension grid of characters board and a string word.The word can be created by assembling the letters of successively surrounding cells, whether they are next to each other vertically or horizontally. It is forbidden to use the same letter cell more than once.

Return true if the word exists in the grid otherwise false.

Example:
// Input : board = [ ["A", "B", "C", "E"] , ["S" ,"F" ,"C" ,"S"] , ["A", "D", "E", "E"] ] , word = "ABCCED"

 bool check(vector<vector<char>> &board, string word, int i, int j, int k)
    {
        if (k == word.size())
            return true;
        if (i < 0 || j < 0 || i >= board.size() || j >= board[0].size() ||
            word[k] != board[i][j])
            return false;

        char c = board[i][j];
        board[i][j] = ' '; // mark as visited
        bool ans = false;
        // check all four directions
        ans |= check(board, word, i + 1, j, k + 1);
        ans |= check(board, word, i - 1, j, k + 1);
        ans |= check(board, word, i, j + 1, k + 1);
        ans |= check(board, word, i, j - 1, k + 1);

        board[i][j] = c; // unmark the cell for backtracking

        return ans;
    }
    bool exist(vector<vector<char>> &board, string word)
    {
        for (int i = 0; i < board.size(); i++)
        {
            for (int j = 0; j < board[0].size(); j++)
            {
                if (board[i][j] == word[0])
                {
                    if (check(board, word, i, j, 0))
                        return true;
                }
            }
        }
        return false;
    }

Letter Combinations of a Phone Number

Given a string consisting of digits from 2 to 9 (inclusive). Return all possible letter combinations that the number can represent.

Example:
// Input : digits = "34"
// Output : [ "dg", "dh", "di", "eg", "eh", "ei", "fg", "fh", "fi" ]