multithreadnqueen.java

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

package org.freethink.nqueen;

import java.util.Stack;
import java.util.Iterator;
import org.freethink.tools.thread.WaitUntilMultiThreadExit;

public class MultiThreadNQueen implements Runnable {
	static final int len = 16;//queen的个数
	static final int threadCount = 2;
	static int mask = (1 << len) - 1;
	static int seg[] = new int[threadCount + 1];
	int start;
	int end;
	int sum = 0;
	Stack<Integer> stack = new Stack<Integer>();
//	static Object signal = new Object();
//	static int activeCount = 0;
	static WaitUntilMultiThreadExit signal = new WaitUntilMultiThreadExit(); 

	static {
		int half = len / 2;
		int interval = half / threadCount;
		for (int i = 0; i < seg.length - 1; i++) {
			seg[i] = i * interval;
		}
		seg[seg.length - 1] = half;
	}

	public MultiThreadNQueen(int threadIdx) {
		if (threadIdx >= threadCount) {
			throw new RuntimeException("thread count is " + threadCount
					+ ", thread no exceed thread count.");
		}
		start = 1 << seg[threadIdx];
		end = 1 << seg[threadIdx + 1];
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Thread[] threads = new Thread[threadCount];
		MultiThreadNQueen[] queens = new MultiThreadNQueen[threadCount];
		for (int i = 0; i < threadCount; i++) {
			MultiThreadNQueen queen = new MultiThreadNQueen(i);
			queens[i] = queen;
			threads[i] = new Thread(queen);
		}

		long starttime = System.currentTimeMillis();
		for (int i = 0; i < threadCount; i++) {
			threads[i].start();
		}
		
		signal.waiting();

		long endtime = System.currentTimeMillis();
		int sum = 0;
		for (int i = 0; i < threadCount; i++) {
			sum += queens[i].sum;
		}

		System.out.println("solution count is " + 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, tmpRow2;
		if (row == 0) {
			tmpRow = start;
			rd = 0;
			ld = 0;
			rowNO = 1;
			tmpRow2 = tmpRow - 1;
		} else {
			tmpRow = row | rd | ld;
			tmpRow = ~tmpRow & (tmpRow + 1) & mask;
			tmpRow2 = row;
		}

		while (tmpRow != 0) {
			// if (rowNO == 1) {
			// System.out.println("try " + Integer.toBinaryString(tmpRow) + " at
			// first row.");
			// }
			if (rowNO == 1 && tmpRow == end) {
				sum *= 2;
				System.out.println("half exit. solution count is " + sum + ".");
				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("-------------");
	}

	public void run() {
		signal.notifyWaiterToWait();
		testRow(0, 0, 0, 0);
		signal.notifyWaiterToRun();
	}
}