Leecode刷题C语言之N皇后②

执行结果:通过

执行用时和内存消耗如下：

struct hashTable {
    int key;
    UT_hash_handle hh;
};

struct hashTable* find(struct hashTable** hashtable, int ikey) {
    struct hashTable* tmp = NULL;
    HASH_FIND_INT(*hashtable, &ikey, tmp);
    return tmp;
}

void insert(struct hashTable** hashtable, int ikey) {
    struct hashTable* tmp = NULL;
    HASH_FIND_INT(*hashtable, &ikey, tmp);
    if (tmp == NULL) {
        tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey;
        HASH_ADD_INT(*hashtable, key, tmp);
    }
}

void erase(struct hashTable** hashtable, int ikey) {
    struct hashTable* tmp = NULL;
    HASH_FIND_INT(*hashtable, &ikey, tmp);
    if (tmp != NULL) {
        HASH_DEL(*hashtable, tmp);
        free(tmp);
    }
}

struct hashTable *columns, *diagonals1, *diagonals2;

int backtrack(int n, int row) {
    if (row == n) {
        return 1;
    } else {
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (find(&columns, i) != NULL) {
                continue;
            }
            int diagonal1 = row - i;
            if (find(&diagonals1, diagonal1) != NULL) {
                continue;
            }
            int diagonal2 = row + i;
            if (find(&diagonals2, diagonal2) != NULL) {
                continue;
            }
            insert(&columns, i);
            insert(&diagonals1, diagonal1);
            insert(&diagonals2, diagonal2);
            count += backtrack(n, row + 1);
            erase(&columns, i);
            erase(&diagonals1, diagonal1);
            erase(&diagonals2, diagonal2);
        }
        return count;
    }
}

int totalNQueens(int n) {
    columns = diagonals1 = diagonals2 = NULL;
    return backtrack(n, 0);
}

解题思路：

这段代码是用来解决经典的N皇后问题的，它利用了哈希表来高效地存储和查询在N皇后问题中已经被占用的列、主对角线和副对角线的信息。下面是代码的详细思路：

数据结构定义

1. 哈希表结构：
   • struct hashTable：定义了一个哈希表节点，包含一个整型key用于存储列、主对角线或副对角线的标识符，以及一个UT_hash_handle hh，这是uthash库用来管理哈希表节点的内部字段。

哈希表操作函数

1. 查找函数find：
   • 输入：指向哈希表头指针的指针hashtable和要查找的键ikey。
   • 功能：在哈希表中查找键为ikey的节点。
   • 输出：返回找到的节点指针，如果未找到则返回NULL。
2. 插入函数insert：
   • 输入：指向哈希表头指针的指针hashtable和要插入的键ikey。
   • 功能：如果哈希表中不存在键为ikey的节点，则创建一个新节点并插入到哈希表中。
   • 输出：无。
3. 删除函数erase：
   • 输入：指向哈希表头指针的指针hashtable和要删除的键ikey。
   • 功能：从哈希表中删除键为ikey的节点，并释放该节点的内存。
   • 输出：无。

解决N皇后问题的函数

1. 回溯函数backtrack：
   • 输入：棋盘的大小n和当前正在放置皇后的行row。
   • 功能：尝试在每一行放置一个皇后，并递归地尝试放置下一行的皇后，直到所有行都成功放置了皇后（即找到一个解），或者所有可能的放置方式都尝试完毕。
   • 辅助数据结构：使用三个哈希表columns、diagonals1和diagonals2分别记录被占用的列、主对角线和副对角线的标识符。
   • 输出：返回找到的解的数量。
2. 主函数totalNQueens：
   • 输入：棋盘的大小n。
   • 功能：初始化三个哈希表，并调用回溯函数backtrack开始求解。
   • 输出：返回N皇后问题的解的总数。

解决方案思路

• 初始化：创建三个哈希表来跟踪哪些列、主对角线和副对角线已被占用。
• 回溯：对于每一行，尝试在该行的每一列放置一个皇后。
  • 检查当前列是否已被占用。
  • 计算当前位置所在的主对角线和副对角线的标识符，并检查它们是否已被占用。
  • 如果当前位置可行（即所在列、主对角线和副对角线都未被占用），则标记这些位置为已占用，并递归地尝试放置下一行的皇后。
  • 如果成功放置了所有行的皇后，则找到一个解，增加解计数器。
  • 回溯时，撤销对当前位置及其所在列、主对角线和副对角线的占用标记。
• 结果：通过回溯所有可能的放置方式，最终得到N皇后问题的解的总数。