谜题

谜题

复制代码 代码如下:

谜题

三阶幻方。试将1~9这9个不同整数填入一个3×3的表格,使得每行、每列以及每条对角线上的数字之和相同。

穷举一个数组中各个元素的排列

l = [6, 2, 4, 1, 98, 34, 5, 9, 23, 8, 10, 32]

N皇后问题。将N个皇后放置在NxN的国际象棋棋盘上,其中没有任何两个皇后处于同一行、同一列或同一对角线上,以使得它们不能互相攻击。

策略

策略

       
//冒泡排序
/*function bubbleSort(arr) {
    newarr = arr.slice()
    if (newarr.length <= 2) return newarr
    for (var i = 0; i < newarr.length – 1; i++) {
        for (var j = 0; j < newarr.length – i – 1; j++) {
            if (newarr[j] > newarr[j + 1]) {
                newarr[j] = [newarr[j + 1], newarr[j + 1] =
newarr[j]][0]

策略

穷举搜索。列出所有的整数填充方案,然后进行过滤。

减而治之、递归

            }
        }
    }
    return newarr
}

回溯法。

JavaScript解

JavaScript解

console.log(l)
result = bubbleSort(l)
console.log(result)*/

JavaScript解

复制代码 代码如下:

       
//快速排序
/*function quickSort(arr) {
    if (arr.length <= 1) return arr;
    var left = [],
        right = [],
        middle = [];
    var mid = arr[Math.floor(arr.length / 2)]
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < mid) {
            left.push(arr[i]);
        } else if (arr[i] > mid) {
            right.push(arr[i]);
        } else {
            middle.push(mid);
        }
    }
    return [].concat(quickSort(left), middle, quickSort(right))

以8皇后问题为例:

/**
 * Created by cshao on 12/28/14.
 */

复制代码 代码如下:

}

复制代码 代码如下:

function getPermutation(arr) {
  if (arr.length == 1) {
    return [arr];
  }

/**
 * Created by cshao on 12/23/14.
 */

var results = quickSort(l)
console.log(results)

/**
 * Created by cshao on 12/28/14.
 */

  var permutation = [];
  for (var i=0; i<arr.length; i++) {
    var firstEle = arr[i];
    var arrClone = arr.slice(0);
    arrClone.splice(i, 1);
    var childPermutation = getPermutation(arrClone);
    for (var j=0; j<childPermutation.length; j++) {
      childPermutation[j].unshift(firstEle);
    }
    permutation = permutation.concat(childPermutation);
  }
  return permutation;
}

function getPermutation(arr) {
  if (arr.length == 1) {
    return [arr];
  }

       
*/

function getNQueens(order) {
  if (order < 4) {
    console.log(‘N Queens problem apply for order bigger than 3’);
    return;
  }

function validateCandidate(candidate) {
  var sum = candidate[0] + candidate[1] + candidate[2];
  for (var i=0; i<3; i++) {
    if (!(sumOfLine(candidate,i)==sum && sumOfColumn(candidate,i)==sum))
{
      return false;
    }
  }
  if (sumOfDiagonal(candidate,true)==sum &&
sumOfDiagonal(candidate,false)==sum) {
    return true;
  }
  return false;
}
function sumOfLine(candidate, line) {
  return candidate[line*3] + candidate[line*3+1] +
candidate[line*3+2];
}
function sumOfColumn(candidate, col) {
  return candidate[col] + candidate[col+3] + candidate[col+6];
}
function sumOfDiagonal(candidate, isForwardSlash) {
  return isForwardSlash ? candidate[2]+candidate[4]+candidate[6] :
candidate[0]+candidate[4]+candidate[8];
}

  var permutation = [];
  for (var i=0; i<arr.length; i++) {
    var firstEle = arr[i];
    var arrClone = arr.slice(0);
    arrClone.splice(i, 1);
    var childPermutation = getPermutation(arrClone);
    for (var j=0; j<childPermutation.length; j++) {
      childPermutation[j].unshift(firstEle);
    }
    permutation = permutation.concat(childPermutation);
  }
  return permutation;
}

//选择排序
/*function selectSort(arr) {
    var min = 9999,
        minindex = 0;
    var left = [],
        right = arr.slice();
    if (arr.length <= 1) return arr;
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] <= min) {
            min = arr[i];
            minindex = i;
        }
    }
    left.push(min);   
    right.splice(minindex, 1);
    return [].concat(left, selectSort(right))
}

  var nQueens = [];
  var backTracking = false;
  rowLoop:
  for (var row=0; row<order; row++) {
    if (nQueens[row] === undefined) {
      nQueens[row] = [];
    }

var permutation = getPermutation([1,2,3,4,5,6,7,8,9]);
var candidate;
for (var i=0; i<permutation.length; i++) {
  candidate = permutation[i];
  if (validateCandidate(candidate)) {
    break;
  } else {
    candidate = null;
  }
}
if (candidate) {
  console.log(candidate);
} else {
  console.log(‘No valid result found’);
}

var permutation = getPermutation([‘a’,’b’,’c’]);
console.dir(permutation);

       
var results = selectSort(l)
console.log(results)*/

    for (var col=0; col<order; col++) {
      if (nQueens[row][col] === 0) {
        continue;
      } else if (backTracking && nQueens[row][col] == 1) {
        if (col === order-1) {
          resetRow(nQueens, order, row);
          row = row – 2;
          continue rowLoop;
        }
        nQueens[row][col] = 0;
        backTracking = false;
        continue;
      }
     
      nQueens[row][col] = 1;
      if (isQueenValid(nQueens, row, col)) {
        continue rowLoop;
      } else if (col == order-1) {
        backTracking = true;
        resetRow(nQueens, order, row);
        row = row – 2;
        continue rowLoop;
      } else {
        nQueens[row][col] = 0;
        continue;
      };
    }
  }

Author

发表评论

电子邮件地址不会被公开。 必填项已用*标注