The ultimate guide to coding interviews. Developed by FAANG engineers. Boost problem-solving skills with number theory, dynamic programming, and graph theory. Get interview-ready in just a few hours.

Competitive Programming - Crack Your Coding Interview.png

Whether you’re gearing up for online coding challenges, code-a-thons, or interviews, then this course is for you. With this course, you will solidify your problem-solving skills ensuring a swift sail through any problem. 


You will be tasked with solving some of the most frequently asked questions that are brought up in FAANG interviews. You will start with the concepts of Number Theory and Divide and Conquer, and gradually move towards more complex problems like dynamic programming and graph theory.


With each problem you solve, there will be insightful explanations and full implementation details to really hammer home the concepts. By the time you finish this course, you will have the confidence to solve any problem, no matter the difficulty.

Competitive Programming - Crack Your Coding Interview, C++

# Implementation
In the [N - Queens Problem](https://www.educative.io/courses/competitive-programming-intvw/n-queens-problem) lesson, we discussed the logic to solve this problem. Let's move to the coding part now.

#include <iostream>
using namespace std;

bool isSafe(int board[][10],int i, int j, int n){
    for(int row = 0; row<i; row++){
        if(board[row][j] == 1){
            return false;
        }
    }
    //Left Diagonal
    int x = i;
    int y = j;
    while(x>=0 && y>=0){
        if(board[x][y]==1)
            return false;
        x--;
        y--;
    }
    //Right Diagonal
    x = i;
    y = j;
    while(x>=0 && y<n){
        if(board[x][y]==1)
            return false;
        x--;
        y++;
    }
    return true;
}

bool solveNQueen(int board[][10],int i, int n){
    if(i==n){

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(board[i][j] == 1){
                    cout<<" Q ";
                }
                else{
                    cout<<" - ";
                }
            }
            cout<<endl;
        }
        cout<<endl<<endl;
        return true; //false to print all configurations
    }

    for(int j=0; j<n; j++){
        if(isSafe(board,i,j,n)){
            board[i][j] = 1;
            bool nextQueen = solveNQueen(board,i+1,n);
            if(nextQueen){
                return true;
            }
            board[i][j] = 0;
        }
    }

    return false;
}

int main() {
    int n = 4;
    int board[10][10] = {0};
    solveNQueen(board,0,n);

}


**Explanation:**

* On line 4, we define a function `isSafe()` to check whether the queen can be placed at position `(i, j)`.
* From lines 5 to 9, we check whether there is any queen already placed in that row. If there is any queen already placed, then we will return `false`.
* From lines 11 to 18, we check whether there is any queen placed in the Left diagonal, and if it is, we return `false`.
* From lines 20 to 28, we check whether there is any queen placed in the Right diagonal, and if it is, we return `false`.
* On line 28, if all the conditions are passed, we return `true`.
* On line 31, we define our function `solveNQueen()` to place a queen at an appropriate position.
* From lines 32 to 45, we perform the printing operation when the value of `i` becomes equal to the number of queens `n`. Initially, the value of `i` was `0` as no queen was placed on the board. 
* Also, on line 36, we check if the value of the particular cell of the board is `1`. If it is, we place the queen in that cell, otherwise, we do not place that queen.
* On line 46, you can return `false` if you want to print all the possible combinations.
* From lines 49 to 60, we check whether a particular cell of the board at `(i,j)` position is safe for the queen to be placed or not. If it is safe, we mark that position as `1`, or else, by default, the value will be `0`. 
* On line 52, we call the function recursively for the next queen and check whether it is safe to place the next queen or not. If it is safe, we return `true`. Otherwise, we will mark that position with `0` and return `false`. 
* In the `main()` function, we define the number of queens `n` and the board of size `10 * 10`.
> A constraint will be that the number of queens should not exceed the board size.

Implement the solution for the N-Queens problem.

Overview

Number Theory

Number Theory

Divide and Conquer

Greedy Algorithms

Greedy Algorithms

Recursion and Backtracking

Recursion and Backtracking

Dynamic Programming

Graphs

Bonus Lessons

N - Queens Problem - Implementation

Implementation