发信人: CSharp (The RETURN of the King), 信区: Algorithm
标 题: 八皇后递归解法--c#
发信站: 兵马俑BBS (Mon Oct 2 11:22:48 2006), 本站(202.117.1.8)
using System;
using System.Collections.Generic;
using System.Text;
public class Queen8
{
//用于记录行、列和两个斜线上是否有queen
bool[] row, column, firstDiagonal, secondDiagonal;
List all;
public string[] getPlacement()
{
row = new bool[8]; column = new bool[8];
firstDiagonal = new bool[15]; secondDiagonal = new bool[15];
all = new List();
DP(0, "");
return all.ToArray();
}
void doit(int curRow, String curSol)
{
if (curRow == 8)
{
all.Add(curSol);
return;
}
for (int i = 0; i < 8; i++)
{
if (!column[i] && !firstDiagonal[curRow - i + 7] && !secondDiagonal[curRow + i])
{
row[curRow] =column[i] = firstDiagonal[curRow - i + 7] = true;
secondDiagonal[curRow + i] = true;
doit(curRow + 1, curSol + (char)('1' + curRow) + (char)('A' + i));
row[curRow] =column[i] = firstDiagonal[curRow - i + 7] = secondDiagonal[curRow + i] = false;
}
}
}
}