U E D R , A S I H C RSS

Eight Queen Problem/최봉환

DeleteMe) 페이지 제목에 대한 통일성 관계상 페이지 이름 수정을 했습니다. --1002

8퀸즈 소스1

2h:30m, 71line
~cpp 
#include <iostream.h>
struct QUEEN{
	int x;
	int y;
};
int map[8][8];
bool MARK(QUEEN Pt);
int main(){
	QUEEN history[8];
	int nQueens=0;
	history[0].x=0;
	history[0].y=0;
	bool bOk;
	while(!bOk || nQueens<8){
		for(int i=0;i<8;i++) for(int j=0;j<8;j++) map[i][j]=0;
		for(i=0;i<nQueens;i++) MARK(history[i]);
		do{
			bOk=MARK(history[nQueens]);
			if(bOk){
				if(nQueens!=7) history[nQueens+1]=history[nQueens];
				nQueens++;
			}
			else{
				if(++history[nQueens].x==8){
					history[nQueens].x=0;
					if(++history[nQueens].y==8){
						do{
							nQueens--;
						}while(history[nQueens].x==7 && history[nQueens].y==7);
						if((++history[nQueens].x)==8){
							history[nQueens].x=0;
							history[nQueens].y++;
						}
						break;
					}
				}
			}
		}while(!bOk);
	}
	for(int y=0;y<8;y++){
		for(int x=0;x<8;x++){
			if(map[x][y]==0) cout<<' ';
			else if(map[x][y]==1) cout<<'X';
			else if(map[x][y]==2) cout<<'O';
		}
		cout<<endl;
	}
	return 0;
}
bool MARK(QUEEN Pt){
	int tmp[8][8];
	for(int x=0;x<8;x++) for(int y=0;y<8;y++) tmp[x][y]=map[x][y];
	if(tmp[Pt.x][Pt.y]>0) return false;
	for(int i=0;i<8;i++){
		if(tmp[Pt.x][i]==2) return false;
		else tmp[Pt.x][i]=1;
		if(tmp[i][Pt.y]==2) return false;
		else tmp[i][Pt.y]=1;
		if(i-Pt.x+Pt.y<8 && i-Pt.x+Pt.y>=0){
			if(tmp[i][i-Pt.x+Pt.y]==2) return false;
			else tmp[i][i-Pt.x+Pt.y]=1;
		}
		if(Pt.x+Pt.y-i<8 && Pt.x+Pt.y-i>=0){
			if(tmp[i][Pt.x-i+Pt.y]==2) return false;
			else tmp[i][Pt.x-i+Pt.y]=1;
		}
	}
	tmp[Pt.x][Pt.y]=2;
	for(x=0;x<8;x++) for(int y=0;y<8;y++) map[x][y]=tmp[x][y];
	return true;
}
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2009-05-27 07:09:19
Processing time 0.1894 sec