剑指offer：八皇后有关问题

剑指offer：八皇后问题

相信大家都知道经典的八皇后问题，我们本次不用回溯法求解八皇后问题，我们采用这样的方法，自己定义一个数组，初始数组

为{0,1,2,3,4,5,6,7}，则数组下标代表行，数组中元素代表列，这样就不会出现两个或者两个以上的数组元素在同一行或者同一列的情况，我们只需要考虑对角巷的情况就可以了，，只要保证两个或者多个元素不在同一对角线上就行了，显然这个对角线分为主对角线和副对角线。

下面是运行的程序：

package com.interview;

/*
 * 经典的八皇后问题
 */
public class EightQueen {
	private int sum = 0;

	public int[] Char2Int(char[] c) {
		int[] a = new int[c.length];
		for (int i = 0; i < c.length; ++i)
			a[i] = c[i] - '0'; // 这里我们定义了一个数组，数组的下标代表行，数组中元素代表列
		return a; // 这样我们就可以在定义的时候规避八皇后问题的不在同一行和不再同一列的问题
	}

	public void listAll(String body, String prefix) {
		if (body.length() < 1) {
			char[] tmp = prefix.toCharArray();
			int[] tmp_arr = Char2Int(tmp);
			boolean tag = false;
			outer: for (int i = 0; i < tmp_arr.length - 1; ++i) {
				for (int j = i + 1; j < tmp_arr.length; ++j) {
					if (i - j == tmp_arr[i] - tmp_arr[j]
							|| (i + tmp_arr[i]) == (j + tmp_arr[j])) {
						tag = true; // 只要碰到一个在对角线上的情况，则条状整个循环
						break outer;
					}
				}
			}
			if (!tag) {
				//if (sum % 4 == 0)
					//System.out.println();
				for (int i = 0; i < tmp_arr.length; ++i)
					System.out.print(tmp_arr[i] + "  ");
				sum++;
				System.out.println();
			}
		} else {
			for (int i = 0; i < body.length(); ++i) {
				listAll(body.substring(1), prefix + body.substring(0, 1));
				body = body.substring(1) + body.substring(0, 1);
			}
		}
	}

	public static void main(String[] args) {
		EightQueen eq = new EightQueen();
		String body = "01234567";
		eq.listAll(body, "");
		System.out.println("\n\n八皇后问题的解法公有:\t" + eq.sum);
	}
}

PS：如果面试题是按照一定要求摆放若干个数字，我们可以先求出这些数字的所有排列，然后再一一判断每个排列是不是满足所给定的要求。

剑指offer：八皇后有关问题

相关推荐