Tutorial 14

---- N Queen Logic Code: 


#include <iostream>

using namespace std;


bool isSafe(int** arr, int ROW, int COL, int rows, int cols)

 {

    // Check row and diagonal conflicts

    for (int row = 0; row < ROW; row++) 

    {

        if (arr[row][COL] == 1) {

            return false;

        }

    }

    int row = ROW, col = COL;

    while (row >= 0 && col >= 0)

     {

        if (arr[row][col] == 1)

         {

            return false;

        }

        row--;

        col--;

    }


    // Check upward-right diagonal

    row = ROW, col = COL;

    while (row >= 0 && col < cols) 

    {

        if (arr[row][col] == 1) {

            return false;

        }

        row--;

        col++;

    }


    return true;

}


bool nQueen(int** arr, int Row, int rows, int cols) {

    if (Row >= cols) {

        return true;

    }


    for (int col = 0; col < cols; col++) {

        if (isSafe(arr, Row, col, rows, cols)) {

            arr[Row][col] = 1;


            if (nQueen(arr, Row + 1, rows, cols)) {

                return true;

            }


            arr[Row][col] = 0; // Backtracking

        }

    }


    return false;

}


int main() {

    int rows, cols;

    cout << "Enter the number of rows: ";

    cin >> rows;

    cout << "Enter the number of columns: ";

    cin >> cols;


    // Dynamically allocate memory for the board

    int** arr = new int*[rows];

    for (int i = 0; i < rows; i++) 

    {

        arr[i] = new int[cols];

    }


    // Initialize the board

    for (int i = 0; i < rows; i++) 

    {

        for (int j = 0; j < cols; j++)

         {

            arr[i][j] = 0;

        }

    }


    if (nQueen(arr, 0, rows, cols)) 

    {

        for (int i = 0; i < rows; i++)

         {

            for (int j = 0; j < cols; j++) 

            {

                cout << arr[i][j] << " ";

            }

            cout << endl;

        }

    } else {

        cout << "No solution exists." << endl;

    }


    // Deallocate memory

    for (int i = 0; i < rows; i++) {

        delete[] arr[i];

    }

    delete[] arr;


    return 0;

}

No comments:

Post a Comment

Fell free to write your query in comment. Your Comments will be fully encouraged.