LeetCode //C - 51. N-Queens

51. 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. You may return the answer in any order.

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 1:

Input: n = 4
Output: [[“.Q…”,“…Q”,“Q…”,“…Q.”],[“…Q.”,“Q…”,“…Q”,“.Q…”]]
Explanation： There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [[“Q”]]

Constraints:

• 1 <= n <= 9

From: LeetCode
Link: 51. N-Queens

---

Solution:

Ideas：

Key Points in This Solution

• Correctly Allocate Memory: Allocate exactly the amount of memory needed, ensuring we don’t access memory out of bounds.
• Safe Queen Placement: Implement logic to check if a queen can be safely placed in a given position without being attacked by other queens.
• Backtracking Algorithm: Utilize a backtracking algorithm to explore all possible configurations, only keeping those that solve the puzzle.
• Avoid Global Variables: Use function parameters to pass necessary data, preventing unforeseen side effects.

Algorithm Overview

1. Initialize Structures: Prepare structures to hold the board state and solutions.
2. Backtracking Function: Recursively attempt to place queens on the board, backtracking whenever we encounter an invalid state.
3. Solution Recording: Once a valid configuration is found (all queens are placed safely), record the current board state as a solution.

Caode:

// Function to create a new board instance
char** createNewBoard(int n) {
    char** board = malloc(n * sizeof(char*));
    for (int i = 0; i < n; i++) {
        board[i] = malloc((n + 1) * sizeof(char)); // +1 for null terminator
        for (int j = 0; j < n; j++) {
            board[i][j] = '.';
        }
        board[i][n] = '\0'; // Ensure string is null-terminated
    }
    return board;
}

// Function to check if a queen can be safely placed at (row, col)
int isSafe(char** board, int row, int col, int n) {
    // Check vertical direction
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return 0;
    }
    // Check left diagonal
    for (int i = row, j = col; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return 0;
    }
    // Check right diagonal
    for (int i = row, j = col; i >= 0 && j < n; i--, j++) {
        if (board[i][j] == 'Q') return 0;
    }
    return 1; // Safe to place queen
}

// Utility function to copy the board state
char** copyBoard(char** board, int n) {
    char** newBoard = createNewBoard(n);
    for (int i = 0; i < n; i++) {
        strncpy(newBoard[i], board[i], n);
    }
    return newBoard;
}

// Recursive function to solve the N-Queens problem
void solveNQueensRec(int n, int row, char** board, char**** solutions, int* returnSize, int** columnSizes) {
    if (row == n) {
        (*solutions)[*returnSize] = copyBoard(board, n);
        (*columnSizes)[*returnSize] = n;
        (*returnSize)++;
        return;
    }
    for (int col = 0; col < n; col++) {
        if (isSafe(board, row, col, n)) {
            board[row][col] = 'Q'; // Place queen
            solveNQueensRec(n, row + 1, board, solutions, returnSize, columnSizes);
            board[row][col] = '.'; // Remove queen (backtrack)
        }
    }
}

// Main solver function
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes) {
    *returnSize = 0;
    int maxSolutions = 1000; // Arbitrary large number to initialize the arrays
    char*** solutions = malloc(maxSolutions * sizeof(char**));
    *returnColumnSizes = malloc(maxSolutions * sizeof(int));
    char** board = createNewBoard(n);

    solveNQueensRec(n, 0, board, &solutions, returnSize, returnColumnSizes);

    // Cleanup
    for (int i = 0; i < n; i++) {
        free(board[i]);
    }
    free(board);

    return solutions;
}

原文地址：https://blog.csdn.net/navicheung/article/details/136223790

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！