queenjface.java

N皇后问题的实现

package arithmetic;

import org.eclipse.jface.action.MenuManager;
import org.eclipse.jface.action.StatusLineManager;
import org.eclipse.jface.action.ToolBarManager;
import org.eclipse.jface.dialogs.MessageDialog;
import org.eclipse.jface.window.ApplicationWindow;
import org.eclipse.swt.SWT;
import org.eclipse.swt.events.MouseAdapter;
import org.eclipse.swt.events.MouseEvent;
import org.eclipse.swt.graphics.Point;
import org.eclipse.swt.widgets.Button;
import org.eclipse.swt.widgets.Composite;
import org.eclipse.swt.widgets.Control;
import org.eclipse.swt.widgets.Display;
import org.eclipse.swt.widgets.Label;
import org.eclipse.swt.widgets.List;
import org.eclipse.swt.widgets.Shell;
import org.eclipse.swt.widgets.Text;

public class QueenJFace extends ApplicationWindow {

	private Text text_2;

	private List list;

	private Text text;

	/**
	 * Create the application window
	 */
	public Queen() {
		super(null);
		createActions();
		addToolBar(SWT.FLAT | SWT.WRAP);
		addMenuBar();
		addStatusLine();
	}

	/**
	 * Create contents of the application window
	 * 
	 * @param parent
	 */
	@Override
	protected Control createContents(Composite parent) {
		Composite container = new Composite(parent, SWT.NONE);

		final Button button = new Button(container, SWT.NONE);
		button.addMouseListener(new MouseAdapter() {
			public void mouseDown(final MouseEvent e) {
				String info = "";
				Text[] texts = { text, text_2 };
				info = getInfo(texts);
				if (!info.equals("")) {
					MessageDialog.openInformation(null, "", info);
					return;
				}

				int n = Integer.parseInt(text.getText().trim());
				int stopLV = Integer.parseInt(text_2.getText().trim());

				info = getInfo(n, stopLV);
				if (!info.equals("")) {
					MessageDialog.openInformation(null, "", info);
					return;
				}

				int[] x = new int[n + 1];
				boolean success = false;
				long begin = System.currentTimeMillis();
				while (success == false) {
					success = queensLV(n, x, stopLV);
					long end = System.currentTimeMillis();
					if(end-begin>5000){
						MessageDialog.openInformation(null, "", "time out");
						return;
					}
				}

				String[] y = new String[n];
				for (int i = 0; i < y.length; i++) {
					y[i] = Integer.toString(x[i + 1]);
				}
				list.setItems(y);
			}

			private String getInfo(int n, int stopLV) {
				if (n <= 3) {
					text.setFocus();
					return "皇后数不能小于或等于3";
				}
				if (stopLV < 0) {
					text_2.setFocus();
					return "stopLV不能为负";
				}
				if (n < stopLV) {
					text_2.setFocus();
					return "stopLV不能大于皇后数";
				}
				return "";
			}

			private String getInfo(Text[] texts) {
				for (Text text : texts) {
					if (text.getText().trim().equals("")) {
						text.setFocus();
						return "不能为空";
					}
					int n = 0;
					try {
						n = Integer.parseInt(text.getText().trim());
					} catch (Exception e1) {
						text.setFocus();
						return "只能填数字";
					}
				}
				return "";
			}
		});
		button.setText("计算");
		button.setBounds(349, 28, 48, 22);

		text = new Text(container, SWT.BORDER);
		text.setBounds(75, 25, 80, 25);

		final Label label = new Label(container, SWT.CENTER);
		label.setText("皇后数：");
		label.setBounds(10, 30, 72, 22);

		list = new List(container, SWT.BORDER | SWT.V_SCROLL | SWT.H_SCROLL);
		list.setBounds(10, 58, 420, 212);

		final Label label_1 = new Label(container, SWT.CENTER);
		label_1.setBounds(170, 30, 63, 22);
		label_1.setText("StopLV：");

		text_2 = new Text(container, SWT.BORDER);
		text_2.setBounds(235, 25, 80, 25);
		return container;
	}

	static boolean place(int k, int[] x) {
		for (int j = 1; j < k; j++) {
			if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || (x[j] == x[k]))
				return false;
		}
		return true;
	}

	static boolean queensLV(int n, int[] x, int stopLV) {
		int k = 1;
		int ok[] = new int[n + 1];
		int count;
		boolean success = false;
		while (k <= stopLV) {
			count = 0;
			for (int i = 1; i <= n; i++) {
				x[k] = i;
				if (place(k, x) == true) {
					count++;
					ok[count] = i;
				}
			}
			if (count == 0) {
				success = false;
				break;
			} else {
				x[k] = ok[(int) (Math.random() * (count)) + 1];
				success = true;
			}
			k++;
		}
		if (success == false && stopLV != 0)
			return false;
		success = backTrack(stopLV + 1, n, x);
		return success;
	}

	static boolean backTrack(int t, int n, int[] x) {
		if (t > n) {
			return true;
		} else {
			for (int i = 1; i <= n; i++) {
				x[t] = i;
				if (place(t, x) == true)
					if (backTrack(t + 1, n, x) == true)
						return true;
			}
		}
		return false;
	}

	/**
	 * Create the actions
	 */
	private void createActions() {
		// Create the actions
	}

	/**
	 * Create the menu manager
	 * 
	 * @return the menu manager
	 */
	@Override
	protected MenuManager createMenuManager() {
		MenuManager menuManager = new MenuManager("menu");
		return menuManager;
	}

	/**
	 * Create the toolbar manager
	 * 
	 * @return the toolbar manager
	 */
	@Override
	protected ToolBarManager createToolBarManager(int style) {
		ToolBarManager toolBarManager = new ToolBarManager(style);
		return toolBarManager;
	}

	/**
	 * Create the status line manager
	 * 
	 * @return the status line manager
	 */
	@Override
	protected StatusLineManager createStatusLineManager() {
		StatusLineManager statusLineManager = new StatusLineManager();
		statusLineManager.setMessage(null, "");
		return statusLineManager;
	}

	/**
	 * Launch the application
	 * 
	 * @param args
	 */
	public static void main(String args[]) {
		try {
			Queen window = new Queen();
			window.setBlockOnOpen(true);
			window.open();
			Display.getCurrent().dispose();
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

	/**
	 * Configure the shell
	 * 
	 * @param newShell
	 */
	@Override
	protected void configureShell(Shell newShell) {
		super.configureShell(newShell);
		newShell.setText("N皇后问题");
	}

	/**
	 * Return the initial size of the window
	 */
	@Override
	protected Point getInitialSize() {
		return new Point(500, 375);
	}

}