nqueen.java

基于位运算的求解NQueen问题的一个实例。 提供了基于单线程和多线程两种方式计算的代码

package org.freethink.nqueen;

import java.util.Stack;
import java.util.Iterator;

public class NQueen {
	static final int len = 16;//queen的个数
	static final int mask = (1 << len) - 1;
	static final int half = (1 << len / 2);
	int sum = 0;
	Stack<Integer> stack = new Stack<Integer>();

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		NQueen queen = new NQueen();
		long starttime = System.currentTimeMillis();
		queen.testRow(0, 0, 0, 0);
		long endtime = System.currentTimeMillis();
		System.out.println("solution count is " + queen.sum + ".");
		System.out.println("it consums " + (endtime - starttime)
				+ "ms to find all solution.");
	}

	/**
	 * @param row
	 * @param rd
	 * @param ld
	 * @param rowNO
	 */
	public void testRow(int row, int rd, int ld, int rowNO) {
		int tmpRow;
		if (row == 0) {
			tmpRow = 1;
			rd = 0;
			ld = 0;
			rowNO = 1;
		} else {
			tmpRow = row | rd | ld;
			tmpRow = ~tmpRow & (tmpRow + 1) & mask;
		}

		int tmpRow2 = row;
		while (tmpRow != 0) {
			// if (rowNO == 1) {
			// System.out.println("try " + Integer.toBinaryString(tmpRow) + " at
			// first row.");
			// }
			if (rowNO == 1 && tmpRow == half) {
				sum *= 2;
				System.out.println("half exit.");
				break;
			}
//			stack.push(tmpRow);
			if (rowNO == len) {
				sum++;
				// output();
			}

			if (rowNO < len) {
				int tmpRd = rd | tmpRow;
				int tmpLd = ld | tmpRow;
				tmpRd >>= 1;
				tmpLd <<= 1;
				testRow(row | tmpRow, tmpRd, tmpLd, rowNO + 1);
			}
//			stack.pop();
			tmpRow2 |= tmpRow;
			tmpRow |= tmpRow2 | rd | ld;
			tmpRow = ~tmpRow & (tmpRow + 1) & mask;
		}
	}

	public void output() {
		System.out.println("queue size is " + stack.size());
		Iterator<Integer> itr = stack.iterator();
		while (itr.hasNext()) {
			System.out.println(Integer.toBinaryString(itr.next()));
		}
		if (stack.size() != len) {
			throw new RuntimeException("error solution.");
		}
		System.out.println("-------------");
	}
}