一个棋盘,一个格子放一个棋子,要求横竖不能有多个棋子，有多少种放法？
一个棋盘,一个格子放一个棋子,要求横竖不能有多个棋子，有多少种放法？
求一个递归算法
------解决方案--------------------
n皇后的阉割版。。。

注释的部分为：结果输出和n皇后斜线部分的判断

以下代码就是答案~

package com.zyc.homework;



/**

 * n皇后问题

 * 

 * 1皇后有1种解 2皇后有0种解 3皇后有0种解 4皇后有2种解 5皇后有10种解 6皇后有4种解 7皇后有40种解 8皇后有92种解 9皇后有352种解

 * 10皇后有724种解 11皇后有2680种解 12皇后有14200种解 13皇后有73712种解 14皇后有365596种解

 * 

 * @author zyc

 * 

 */

public class Homework02 {

	static final char QUEEN = 'Q';

	static final char STAR = '*';



	static int _count = 0;



	public static void main(String[] args) {

		nQueen(8);

	}



	static void nQueen(int n) {

		if (n < 1) {

			System.out.println("参数错误");

			return;

		}

		// 初始化数组，全部为'*'

		char[][] arr = new char[n][n];

		for (int i = 0; i < arr.length; ++i) {

			for (int j = 0; j < arr.length; ++j) {

				arr[i][j] = STAR;

			}

		}

		// 递归解n皇后

		nQueen(arr, 0, n);

		System.out.printf("%d皇后有%d种解\n", n, _count);

	}



	static void nQueen(char[][] arr, int row, int max) {

		// 数量达到n个输出

		if (row == max) {

//			output(arr);

			++_count;

			return;

		}

		// 按列遍历

		for (int col = 0; col < arr.length; ++col) {

			// 如果发现这个格子可以放，就继续递归遍历

			if (canPut(arr, row, col)) {

				arr[row][col] = QUEEN;

				nQueen(arr, row + 1, max);

				// 不要忘记设回来，否则下次遍历出错

				arr[row][col] = STAR;

			}

		}

	}



	static boolean canPut(char[][] arr, int row, int col) {

		// 判断竖线

		for (int i = 0; i < row; ++i) {

			if (arr[i][col] == QUEEN) {

				return false;

			}

		}

//		// 判断左上对角线

//		for (int i = row, j = col; i > 0 && j > 0; --i, --j) {

//			if (arr[i - 1][j - 1] == QUEEN) {

//				return false;

//			}

//		}

//		// 判断右上对角线

//		for (int i = row, j = col; i > 0 && j < arr.length - 1; --i, ++j) {

//			if (arr[i - 1][j + 1] == QUEEN) {

//				return false;

//			}

//		}

		return true;

	}



	// 输出数组

	static void output(char[][] arr) {

		System.out.println("----------------");

		for (int i = 0; i < arr.length; ++i) {

			for (int j = 0; j < arr.length; ++j) {

				System.out.print(arr[i][j] + " ");

			}

			System.out.println();

		}

	}

}