8皇后以及N皇后算法探究，回溯算法的JAVA实现，递归方案（一）

八皇后问题，是一个古老而著名的问题，是回溯算法的典型案例。该问题是国际西洋棋棋手马克斯·贝瑟尔于1848年提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。计算机发明后，有多种计算机语言可以解决此问题。---------以上节选自百度百科。

算法思考，初步思路：

构建二维int或者short型数组，内存中模拟棋盘

chess[r][c]=0表示：r行c列没有皇后，chess[r][c]=1表示：r行c列位置有一个皇后

从第一行第一列开始逐行摆放皇后

依题意每行只能有一个皇后，遂逐行摆放，每行一个皇后即可

摆放后立即调用一个验证函数（传递整个棋盘的数据），验证合理性，安全则摆放下一个，不安全则尝试摆放这一行的下一个位置，直至摆到棋盘边界

当这一行所有位置都无法保证皇后安全时，需要回退到上一行，清除上一行的摆放记录，并且在上一行尝试摆放下一位置的皇后（回溯算法的核心）

当摆放到最后一行，并且调用验证函数确定安全后，累积数自增1，表示有一个解成功算出

验证函数中，需要扫描当前摆放皇后的左上࿰

文章来源: aaaedu.blog.csdn.net，作者：tea_year，版权归原作者所有，如需转载，请联系作者。

原文链接：aaaedu.blog.csdn.net/article/details/84642774