算法

八皇后问题

八皇后问题是一个经典的回溯算法案例。 国际西洋棋棋手马克斯·贝瑟尔于1848年提出:在8×8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。 解法1 因为皇后不能在同一行中,所以可以排除掉行这一因素,所以可以使用一个数组c[n]来表示皇后的放法,如c[i]=j,表示第i行的皇后在j列 则判断皇后位置是否冲突的方法就只需要判断是否在同一列或同一斜线,如果c[a]=c[b],则第a行的皇后与第b行的皇后在同一列中; 如果|a-b|=|c[a]-c[b]|,则**a和b之间行的差等于列的差,

  • zgljl2012
5 min read
Java

【LeetCode】52. N-Queens II

问题描述 https://leetcode.com/problems/n-queens-ii/#/description Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 比N-Queens反倒容易一点了,因为不需要存储解法,只需要计算数目。 算法分析 两个皇后不能在同一行、同一列和同一斜线上。 解法1 因为皇后不能在同一行中,所以可以排除掉行这一因素,

  • zgljl2012
5 min read
2693491512@qq.com