{"id":896,"date":"2024-10-14T14:17:28","date_gmt":"2024-10-14T08:47:28","guid":{"rendered":"https:\/\/codexplained.in\/?p=896"},"modified":"2025-11-24T15:47:07","modified_gmt":"2025-11-24T10:17:07","slug":"solving-of-n-queens-problem-using-backtracking","status":"publish","type":"post","link":"https:\/\/codexplained.in\/?p=896","title":{"rendered":"Solving of N-Queens Problem using Backtracking"},"content":{"rendered":"\n

Problem Statement<\/h3>\n\n\n\n

Given an integer N, your goal is to find all possible arrangements to place N queens on an N\u00d7N chessboard. This can be solved using backtracking, a technique that tries to build a solution incrementally and abandons a solution as soon as it determines that it cannot be valid.<\/p>\n\n\n\n

Key Concepts<\/h3>\n\n\n\n
    \n
  1. Backtracking<\/strong>: This algorithm explores all possible placements of queens row by row and backtracks when it encounters a conflict.<\/li>\n\n\n\n
  2. Safety Check<\/strong>: Before placing a queen, we need to ensure that it doesn\u2019t threaten other queens already placed on the board.<\/li>\n<\/ol>\n\n\n\n

    Steps to Solve the Problem<\/h3>\n\n\n\n
      \n
    1. Board Representation<\/strong>: Use a 2D array to represent the chessboard.<\/li>\n\n\n\n
    2. Placement<\/strong>: For each row, attempt to place a queen in every column.<\/li>\n\n\n\n
    3. Validation<\/strong>: Check if placing the queen is valid (i.e., no queens threaten each other).<\/li>\n\n\n\n
    4. Recursive Call<\/strong>: If placing the queen is valid, make a recursive call to place queens in the next row.<\/li>\n\n\n\n
    5. Backtrack<\/strong>: If a placement doesn\u2019t lead to a solution, remove the queen and try the next column.<\/li>\n<\/ol>\n\n\n\n

      C Program to Solve the N-Queens Problem<\/h3>\n\n\n
      \n#include <stdio.h>\n#include <stdbool.h>\n\n#define N 8 \/\/ Change this value to solve for different sizes\n\n\/\/ Function to print the chessboard\nvoid printBoard(int board[N][N]) {\n    for (int i = 0; i < N; i++) {\n        for (int j = 0; j < N; j++) {\n            printf("%d ", board[i][j]);\n        }\n        printf("\\n");\n    }\n    printf("\\n");\n}\n\n\/\/ Function to check if a queen can be placed at board[row][col]\nbool isSafe(int board[N][N], int row, int col) {\n    \/\/ Check this column on upper rows\n    for (int i = 0; i < row; i++)\n        if (board[i][col]) return false;\n\n    \/\/ Check upper diagonal on the left side\n    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--)\n        if (board[i][j]) return false;\n\n    \/\/ Check upper diagonal on the right side\n    for (int i = row, j = col; i >= 0 && j < N; i--, j++)\n        if (board[i][j]) return false;\n\n    return true;\n}\n\n\/\/ Function to solve the N-Queens problem using backtracking\nbool solveNQUtil(int board[N][N], int row) {\n    \/\/ Base case: If all queens are placed\n    if (row >= N) {\n        printBoard(board);\n        return true;\n    }\n\n    \/\/ Try placing a queen in each column of the current row\n    for (int col = 0; col < N; col++) {\n        if (isSafe(board, row, col)) {\n            \/\/ Place queen\n            board[row][col] = 1;\n\n            \/\/ Recursively place the rest of the queens\n            if (solveNQUtil(board, row + 1)) {\n                return true; \/\/ If successful, return true\n            }\n\n            \/\/ Backtrack: Remove the queen\n            board[row][col] = 0;\n        }\n    }\n    return false; \/\/ No valid position found\n}\n\n\/\/ Main function\nint main() {\n    int board[N][N] = {0}; \/\/ Initialize the board with 0s\n\n    printf("Solutions for %d-Queens Problem:\\n", N);\n    if (!solveNQUtil(board, 0)) {\n        printf("No solution exists\\n");\n    }\n\n    return 0;\n}\n\n<\/pre><\/div>\n\n\n
      Explanation of the Code<\/h3>\n\n\n\n
        \n
      1. Board Representation<\/strong>: A 2D array board[N][N]<\/code> is used to represent the chessboard. A value of 1<\/code> indicates a queen is placed in that position, and 0<\/code> indicates an empty position.<\/li>\n\n\n\n
      2. Printing the Board<\/strong>: The printBoard<\/code> function displays the current state of the board.<\/li>\n\n\n\n
      3. Safety Check<\/strong>: The isSafe<\/code> function checks whether a queen can be placed at a given position (row, col) by checking the column and the diagonals.<\/li>\n\n\n\n
      4. Backtracking Function<\/strong>: The solveNQUtil<\/code> function attempts to place queens row by row. If it successfully places all queens, it prints the board configuration. If it cannot place a queen in any column, it backtracks by removing the last placed queen.<\/li>\n\n\n\n
      5. Main Function<\/strong>: Initializes the board and starts the backtracking process. It prints all possible solutions.<\/li>\n<\/ol>\n\n\n\n
        Input and Output Example<\/h3>\n\n\n\n
        Input<\/h4>\n\n\n\n
        The program is currently set to solve the 8-Queens problem (N=8) as defined by the macro #define N 8<\/code>.<\/p>\n\n\n\n
        Output<\/h4>\n\n\n\n
        The program outputs all possible configurations for placing 8 queens on the board.<\/p>\n\n\n\n
        Example output:<\/p>\n\n\n\n
        codeSolutions for 8-Queens Problem:
        0 0 0 0 1 0 0 0 
        0 0 0 0 0 0 1 0 
        1 0 0 0 0 0 0 0 
        0 0 0 1 0 0 0 0 
        0 0 0 0 0 1 0 0 
        0 1 0 0 0 0 0 0 
        0 0 0 0 0 0 0 1 
        0 0 1 0 0 0 0 0 

        ... (more solutions)
        <\/code><\/pre>\n\n\n\n
        Explanation of the Output<\/h3>\n\n\n\n
        Each configuration shows a possible arrangement of the queens on the chessboard, where 1<\/code> represents a queen and 0<\/code> represents an empty space. The output may contain multiple solutions depending on the size of N.<\/p>\n\n\n\n
        Conclusion<\/h3>\n\n\n\n
        This program effectively implements the N-Queens problem using backtracking. It showcases how to systematically explore possible placements and use recursion to find all valid solutions. You can modify the value of N to solve for different sizes of the chessboard.<\/p>\n