杂乱无章

当前位置:首页 > 技术世界 > 杂乱无章

【位运算经典应用】 N皇后问题

说到位运算的经典应用,不得不说N皇后问题。

学过程序设计的都知道N皇后问题,没听过也没关系。很简单,最传统的的N皇后问题是这个样子的,给你一个n * n大小的board,让你放n个皇后(国际象棋),要满足任意两个皇后不能在一条水平线上,不能在一条垂直线上,也不能在一条45度的斜线上。听起来似乎和数独挺像,其实N皇后的条件更苛刻,除了水平垂直线外,数独只有两条对角线,而N皇后有很多条斜线,这点需要注意。

为了判断程序的正确性,正好leetcode上有道题可以测试N-Queens II,也是最经典的N皇后问题,给出n求得摆法的数量。

常规解法


一个很显而易见的解法是递归求解,从上到下一行一行摆下去,并且记录每行摆的位置,因为下一行摆放的位置要根据上面的摆放情况来确定。这里我们定义了一个pos数组,pos[1]的值表示摆在第一行的皇后所在的列,pos[2]的值表示摆在第二行的皇后所在的列,以此类推,所以摆到第n行时,上面摆放的皇后的位置就可以很容易地得到,从而可以进行判断(该行什么位置可以摆放)。

当摆放到第r行时,我们遍历该行所有的n个位置,判断每个位置(r行c列)是否可以摆放,需要与前面摆放的每个皇后比较,是否在一条水平线上(这是不可能的),是否在一条垂直线上,是否在一条斜线上:

function check(r, c) {  for (var i = 1; i < r; i++) {    if (Math.abs(i - r) === Math.abs(pos[i] - c)) // 一条斜线上      return true;    if (c === pos[i]) // 一条竖直线上      return true;  }  return false;}

整个代码也就显而易见了:

var pos;function check(r, c) {  for (var i = 1; i < r; i++) {    if (Math.abs(i - r) === Math.abs(pos[i] - c)) // 一条斜线上      return true;    if (c === pos[i]) // 一条竖直线上      return true;  }  return false;}function dfs(r, n) {  if (r === n + 1)    return 1;  var ans = 0;    for (var i = 1; i <= n; i++) {    if (check(r, i)) continue;    pos[r] = i;    ans += dfs(r + 1, n);  }  return ans;}var totalNQueens = function(n) {  pos = [];  return dfs(1, n);};

位运算解法


在读下文前,请先阅读【位运算经典应用】标志位与掩码会事半功倍。

位运算解法,递归是避免不了的,能优化的在于check()函数部分。

假设一个4 * 4的board,我们在第一行第三列上摆了个皇后,其实它已经把第一行之后的6个位置给ko掉了:

- - o -- X X XX - X -- - X -

我们用flag=2(1<<2)记录第一行摆下的这个位置,在第二行中,很显然(1<<2)这个位置已经不能摆了,而(2<<1)这个位置也不能摆,(2>>1)这个位置也不能摆。如果要在第二行右起第1个摆下皇后,我们用flag2=1(1<<1)记录这个决定,我们只需用flag2和以上算出来的不能摆的位置去做个与运算,看看有没有冲突即可。结果(2>>1)&(1<<1)得到了非0的数,表示两者冲突,所以该位置摆放失败。

假设我们接着在第二行左起第一个摆放了皇后,对于第三行的摆放来说,第一行摆的皇后对它还是有影响的,比如它不能摆在第三行左起第一个位置,因为(2<<2)&(1<<4)!==0,冲突。而(2<<2)正是在第二排摆放决策中(2<<1)<<1。看到这里你也许应该有了思路,没错,我们可以维护三个数,l, r, c, 用来表示该行被右上角斜线,左上角斜线,正上方直线所影响而不能摆放的位置。三个数每次与欲摆放的位置作与运算,求解是否冲突,如没有,l和r分别左移右移后继续递归。

function dfs(l, r, c, index, n) {  if (index === n)     return 1;  var ans = 0;  for (var i = 0; i < n; i++) {    var tmp = 1 << i;    if ((tmp & l) || (tmp & r) || (tmp & c)) continue;    ans += dfs((tmp | l) << 1, (tmp | r) >> 1, tmp | c, index + 1, n);  }  return ans;}var totalNQueens = function(n) {  return dfs(0, 0, 0, 0, n);};

转载说明:欢迎转载本站所有文章,如需转载请注明来源于《绝客部落》。

本文链接:https://juehackr.net/zawen/82.html

相关内容

文章评论

表情

共 0 条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~