力扣第五十二题——N皇后II

内容介绍

n 皇后问题 研究的是如何将 n 个皇后放置在 n × n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回 n 皇后问题 不同的解决方案的数量。

示例 1：
输入：n = 4
输出：2
解释：如上图所示，4 皇后问题存在两个不同的解法。
示例 2：
输入：n = 1
输出：1
提示：

1 <= n <= 9

完整代码

 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×N的棋盘上放置N个皇后，使得它们互不攻击。也就是说，任何两个皇后都不能处于同一行、同一列或同一斜线上。

二、解题思路

表示棋盘：
- 使用哈希表来表示棋盘，其中每个键代表棋盘上的一列，值代表该列上皇后的位置。
回溯算法：
- 采用回溯法尝试在每一行放置一个皇后，并递归地检查后续行的放置情况。
冲突检测：
- 使用三个哈希表columns、diagonals1和diagonals2分别表示列和两个方向的斜线是否已被占用。
- 在放置皇后时，检查新皇后是否与已放置的皇后冲突。

三、代码详解

哈希表定义：
- hashTable结构体包含一个整型键和哈希处理句柄。

struct hashTable {int key;UT_hash_handle hh;
};

查找操作：
- find函数用于在哈希表中查找指定键的值。

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

插入操作：
- insert函数用于在哈希表中插入一个新的键值对。

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);}
}

删除操作：
- erase函数用于从哈希表中删除指定键的值。

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);}
}

回溯函数：
- backtrack函数是回溯算法的核心，它尝试在每一行放置一个皇后，并递归地检查后续行的放置情况。

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;}
}

主函数：
- totalNQueens函数初始化哈希表，并调用backtrack函数开始回溯过程。

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

知识点精炼

一、核心概念

回溯算法：一种通过尝试所有可能的情况来解决问题的算法，适用于组合问题。
哈希表：一种基于键值对的数据结构，用于存储和查找数据。
冲突检测：在放置皇后时，确保新放置的皇后不与已放置的皇后在同一列或同一斜线上。

二、知识点精炼

棋盘表示：
- 使用哈希表来表示棋盘，其中键表示列号，值表示在该列上皇后的位置。
冲突检测哈希表：
- 使用三个哈希表columns、diagonals1和diagonals2分别表示列和两个方向的斜线是否已被占用。
回溯函数：
- backtrack函数递归地尝试在每一行放置一个皇后，并在放置后进行冲突检测。
- 如果所有皇后都成功放置，则返回1；否则，返回0。
递归终止条件：
- 当所有行都已放置皇后时，表示找到一个有效解决方案。
状态重置：
- 在回溯时，需要将当前行的皇后位置从哈希表中删除，以便尝试其他可能的放置。
解决方案计数：
- 记录找到的解决方案数量，并在回溯过程中累加。

三、性能优化

空间优化：使用哈希表替代整型数组进行冲突检测，减少内存使用。
时间优化：通过提前终止递归路径来减少不必要的计算。

四、实际应用

组合问题：N皇后问题是一种典型的组合问题，其解法可以推广到其他类似的组合优化问题。
算法竞赛：在算法竞赛中，掌握回溯算法对于解决组合类问题非常有帮助。

五、代码实现要点

动态内存分配：在生成哈希表和解决方案计数时，需要动态分配内存。
内存释放：在实际应用中，需要确保在适当的时候释放分配的内存，避免内存泄漏。

其他解法方案

深度优先搜索（DFS）：
- 类似于回溯算法，DFS尝试所有可能的皇后放置位置，并在发现冲突时回溯。
- 区别在于，DFS不使用哈希表来跟踪已放置的皇后，而是使用递归栈来回溯。
位运算：
- 使用位运算来替代哈希表进行冲突检测，可以减少内存使用并提高速度。
- 位运算使用整型变量来表示列和斜线是否已被占用，通过位掩码（bitmask）来表示皇后的位置和攻击范围。
分治法：
- 将棋盘分为四部分，分别放置皇后，然后合并解决方案。
- 适用于较小规模的问题，对于N皇后问题，分治法通常不如回溯法高效。
启发式算法：
- 例如遗传算法、模拟退火等，这些算法可以用来寻找N皇后问题的近似解，而不是精确解。
并行算法：
- 使用并行计算来加速N皇后问题的求解，尤其是当问题的规模非常大时。
动态规划：
- 动态规划通常用于解决最优解问题，对于N皇后问题，动态规划不是最优的选择，因为问题的解不是最优解。

每种解法都有其适用场景和优缺点。回溯算法因其简单性和效率而成为解决N皇后问题的常见方法。其他方法可能在特定情况下提供更优的性能，但通常需要更复杂的实现和更长的学习曲线。在选择解法时，应根据具体问题和性能要求来决定。