八皇后，栈溢出


package 递归;public class EightQueenProblem {
private int queenCount;
private int[] ROW;
private int[] COL;
private int[] backslashDiff;
private int[] slashSum;
// private int[][] board;
private int solutionCount;
private int[][] positions;
private int[] oneSolution;

public EightQueenProblem(int queenCount){
this.queenCount = queenCount;
ROW = new int[queenCount];
COL = new int[queenCount];
backslashDiff = new int[2*queenCount-1];
slashSum = new int[2*queenCount-1];
// board = new int[queenCount][queenCount];
int maxPossibleSolutionCount=1;
for(int i=1;i<=queenCount;i++)
maxPossibleSolutionCount*=i;
positions = new int[maxPossibleSolutionCount][queenCount];
oneSolution = new int[queenCount];
//会自动初始化为零，不用我操心
}

private boolean put(int row){
boolean hasPut=false;
   for(int col=0;col<queenCount;col++){
if(valid(row,col))
{
(row,col);
oneSolution[row]=col;
  if(row==queenCount-1)
{
System.arraycopy(oneSolution, 0, positions[solutionCount++], 0, queenCount);
hasPut = true;
}
  put(row+1);
deMark(row,col);//不管放置成功与否，回来后都清除痕迹,从而保证得出所有结果
}
}
return hasPut;
}

private boolean valid(int row,int col){
if(row<0 || col<0 || row>queenCount-1 || col>queenCount-1)
return false;
if(backslashDiff[row-col+queenCount-1]!=0)
return false;
if(slashSum[row+col]!=0)
return false;
if(ROW[row]!=0)
return false;
if(COL[col]!=0)
return false;
return true;
}
private void (int row,int col){
backslashDiff[row-col+queenCount-1]=1;
slashSum[row+col]=1;
ROW[row]=1;
COL[col]=1;
// board[row][col]=1;
}
private void deMark(int row,int col){
backslashDiff[row-col+queenCount-1]=0;
slashSum[row+col]=0;
ROW[row]=0;
COL[col]=0;
// board[row][col]=0;
}
public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(solutionCount);
return sb.toString();
}
public static void main(String[] args) {
EightQueenProblem eq = new EightQueenProblem(8);//这里改到10就会栈溢出，求解决方案
System.out.println(eq);
eq.put(0);
System.out.println(eq);

}}10皇后栈溢出的问题，我在VC++6.0中用同样的思路，改到12皇后都没问题的，是不是编译器设置的问题？// QBoard.cpp: implementation of the CQBoard class.
//
//////////////////////////////////////////////////////////////////////#include "stdafx.h"
#include "QBoard.h"//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////CQBoard::CQBoard()
{}CQBoard::~CQBoard()
{}void CQBoard::Initial()
{
for(int i=0;i<15;i++)
{
ColPos[i]=true;
}
for(i=1;i<25;i++)
{
diag45[i]=true;
diag135[i]=true;
}
SolutionNum=1;
index=1;
memset(Solution,0,sizeof(Solution));
}void CQBoard::Solve()
{
Place(1);
}void CQBoard::Place(int row)
{
if(row-1==QueenNum) //找到了一种方案
{
for(int i=1;i<=QueenNum;i++)
{
Solution[SolutionNum][i]=temp[i];
}
SolutionNum++;
return;
}
for(int col=1;col<=QueenNum;col++)
{
if(CanPlace(row,col))
{
Mark(row,col); //标记并递归
temp[row]=col;
Place(row+1);
DeMark(row,col);//标记并回溯
}
}
}//判断是否可以放置皇后,从列，45度对角线和135度对角线
bool CQBoard::CanPlace(int row, int col)
{
if(diag45[row+col]&&diag135[row-col+QueenNum]&&ColPos[col])
return true;
return false;
}
//标记皇后的控制范围
void CQBoard::Mark(int row, int col)
{
diag45[row+col]=false;
diag135[row-col+QueenNum]=false;
ColPos[col]=false;
}
//取消皇后控制范围的标记，以便回溯
void CQBoard::DeMark(int row, int col)
{
diag45[row+col]=true;
diag135[row-col+QueenNum]=true;
ColPos[col]=true;
}
//画出棋盘面板
void CQBoard::DrawBoard(int thSol)
{
int i;
for(i=0;i<13;i++) //画网格
{
MoveToEx(hdc, left, top+i* Gridwidth,NULL);
LineTo(hdc, right, top+i* Gridwidth);
}
for(i=0;i<13;i++) //画网格
{
MoveToEx(hdc, left+i* Gridwidth, top,NULL);
LineTo(hdc, left+i* Gridwidth, bottom);
}

RECT rt;

  for(i=1;i<=QueenNum;i++)
  {
  rt.left=left+(Solution[thSol][i]-1)*Gridwidth;
  rt.top=top+(i-1)*Gridwidth;
  rt.bottom=rt.top+Gridwidth;
  rt.right=rt.left+Gridwidth;//找到填充位置
  HBRUSH OldBrush=(HBRUSH)SelectObject(hdc,GetStockObject(BLACK_BRUSH));
  if(Solution[thSol][i]!=0)
{
//char note[5];
//wsprintf(note,"%d",Solution[thSol][i]);//填充皇后所在位置并标记所在列
Ellipse(hdc,rt.left,rt.top,rt.right,rt.bottom);
//TextOut(hdc,rt.left+size/2-2,rt.top+size/2-3,note,strlen(note));
}
  SelectObject(hdc,OldBrush);
}
}
//初始化基本大小
void CQBoard::SetSize()
{
size=HIWORD(GetDialogBaseUnits());//初始化基本大小
left =    ClientRect.left+ size;
right =   ClientRect.right- size*5;
top =     ClientRect.top+ size;
bottom =  ClientRect.bottom- size;
Gridwidth=( bottom- top)/12;
right= left+ Gridwidth*12;
bottom= top+ Gridwidth*12;}