JavaScript解决八皇后问题

背景

皇后是国际象棋中最强的棋子,可以向任意合法方向攻击,黑白双方各有一枚,所以真正意义上的八皇后是不存在的。不过八皇后问题是一个回溯法(Backtracking)求解问题的例子,值得一玩。

八皇后问题(Eight queens puzzle)要求在8 × 8的国际象棋棋盘上放置八个皇后,使得他们无法互相攻击。推广到n皇后时,即在n x n的棋盘上解决此问题(n = 2和n = 3除外)。

JavaScript实现

对于8皇后问题,实际就是要保证横、竖、斜三向都只有一个皇后。

EightQueens.js

#!/usr/bin/env node

/**
 * Eight queens puzzle
 *
 * @author YanWen <i@yanwen.email>
 * @modified 2018-01-03
 */

/**
 *
 * @class Queens
 */
const Queens = class extends Object {
  constructor(numOfQueens) {
    super();

    this.numOfQueens = numOfQueens;

    // protected

    // Init a numOfQueens x numOfQueens matrix
    this._matrix = new Array(this.numOfQueens).fill(Infinity);
    this._matrix.forEach((val, key) => this._matrix[key] = new Array(this.numOfQueens).fill(Infinity));

    this._numOfCases = 0;
  }

  // protected

  /**
   * isLegal
   *
   * @param number index1
   * @param number index2
   * @return boolean
   */
  _isLegal(index1, index2) {
    for (let key1 in this._matrix) {
      if (key1 >= index1) break;

      for (let key2 in this._matrix[key1]) {
        if ( this._matrix[key1][key2] === 1 && (key2 === index2 ||
             Math.abs(index1 - key1) === Math.abs(index2 - key2)) )
          return false;
      }
    }
    return true;
  }

  /**
   * print
   *
   * @return undefined
   */
  _print() {
    process.stdout.write(`Case ${++this._numOfCases}:n`);

    this._matrix.forEach(val1 => {
      val1.forEach(val2 => process.stdout.write(`${val2 === 1 ? '♛' : '+'} `));
      process.stdout.write('n');
    });
    process.stdout.write('n')
  }

  /**
  * find recursively
  *
  * @param number index1
  * @return undefined
  */
  _find(index1) {
    index1 >= this.numOfQueens ? this._print() : (function(self) {
      for (let index2 in self._matrix[index1]) {
        self._matrix[index1][index2] = 1;
        self._isLegal(index1, index2) ? self._find(index1 + 1) : void 0;
        self._matrix[index1][index2] = 0;
      }
    }(this));
  }

  // public

  /**
  * find all
  *
  * @return undefined
  */
  findAll() {
    this._find(0);
  }

};

/**
 *
 * @class EightQueens
 */
const EightQueens = class extends Queens {
  constructor() {
    super(8);
  }

  // Test
  static main() {
    let eightQueens = new EightQueens;
    eightQueens.findAll();
  }
};

// Test
(function(self) {
  typeof window === 'undefined' ? EightQueens.main.call(self) : void 0;
}(this));

简单测试:

$ ./EightQueens.js
Case 1:
♛ + + + + + + + 
+ + + + ♛ + + + 
+ + + + + + + ♛ 
+ + + + + ♛ + + 
+ + ♛ + + + + + 
+ + + + + + ♛ + 
+ ♛ + + + + + + 
+ + + ♛ + + + + 

Case 2:
♛ + + + + + + + 
+ + + + + ♛ + + 
+ + + + + + + ♛ 
+ + ♛ + + + + + 
+ + + + + + ♛ + 
+ + + ♛ + + + + 
+ ♛ + + + + + + 
+ + + + ♛ + + +

...

Case 92:
+ + + + + + + ♛ 
+ + + ♛ + + + + 
♛ + + + + + + + 
+ + ♛ + + + + + 
+ + + + + ♛ + + 
+ ♛ + + + + + + 
+ + + + + + ♛ + 
+ + + + ♛ + + + 

参考:

  1. Wikipedida – Eight_queens_puzzle
  2. Wikipedia – Backtracking

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google photo

You are commenting using your Google account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s