算法

八皇后问题

八皇后问题是一个经典的回溯算法案例。 国际西洋棋棋手马克斯·贝瑟尔于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
zgljl2012@gmail.com