U E D R , A S I H C RSS

Eight Queen Problem/강인수

  • C++로 한거(심심해서 한거)

~cpp 
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

const int N = 8;

int fac(int n)
{
	int ret = 1;
	if(n <= 1)
		return 1;
	for(int i = 2 ; i <= n ; ++i)
		ret *= i;
	return ret;
}

bool isCorrectChecker(vector<int>& ar)
{
	for(int i = 0 ; i < ar.size() ; ++i)
	{
		for(int j = 0 ; j < ar.size() ; ++j)
			if( abs(ar[i] - ar[j]) == abs(i - j) && i != j )
				return false;
	}
	return true;
}

vector< vector<int> > getCorrectChecker(vector<int>& ar)
{
	vector< vector<int> > ret;
	for(int i = 0 ; i < fac( ar.size() ) ; ++i)
	{
		next_permutation(ar.begin(), ar.end());
		if( isCorrectChecker(ar) )
			ret.push_back( ar );
	}
	return ret;
}

void showResult(vector< vector<int> >& result)
{
	for(int i = 0 ; i < result.size() ; ++i)
	{
		for(int j = 0 ; j < result[i].size() ; ++j)
			cout << result[i][j] << " ";
		cout << endl;
	}
}

vector<int> getDatas()
{
	vector<int> ret(N);
	for(int i = 0 ; i < N ; ++i)
		ret[i] = i + 1;
	return ret;
}

int main()
{
	int totalNum = 0;
	vector<int> ar = getDatas();
	vector< vector<int> > result = getCorrectChecker(ar);
	showResult(result);
	return 0;
}
  • 파이썬으로 한거(2003 데블스 캠프 대비용)

~cpp 
class NQueen:
    def __init__(self, size):
        self.size = size
        self.count = 0
        self.board = [0] * (self.size+1)
    def isValid(self, curRow):
        for i in range(curRow):
            if self.board[i] == self.board[curRow] or\
               abs(self.board[i]-self.board[curRow]) == abs(i - curRow):
                return False
        return True
    def traverse(self, curRow):
        for i in range(self.size):
            self.board[curRow] = i
            if self.isValid(curRow):
                self.traverse(curRow+1)
                if curRow == self.size-1:
                    self.printBoard()
    def printBoard(self):
        self.count+=1
        print self.count , ' : ',
        for i in range(self.size):
            print self.board[i]+1 , ' ',
        print

if __name__ == '__main__':
    queen = NQueen(8)
    queen.traverse(0)     


Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:11
Processing time 0.0125 sec