전배열 & 8 황후 문제

 1 #include <iostream>

 2 

 3 using namespace std;

 4 static int num = 0;

 5 bool check(int * arry, int length)

 6 {

 7     int i, j;

 8     for(i = 0; i < length; ++i)

 9     {
11         for(j = i+1; j < length; ++j)

12         {

13             if(arry[i] - arry[j] == j - i || arry[i] - arry[j] == i - j)

14                 return false;

15         }

16     }

17     return true;

18 }

19 void permutation(int * arry, int start, int length)

20 {

21     if(start == length && check(arry, length))

22     {

23         for(int j = 0; j < length; ++j)

24             cout << arry[j] << " ";

25         cout << endl;

26         num++;

27         return;

28     }

29     for(int i = start; i < length; ++i)

30     {

31         int temp = arry[start];

32         arry[start] = arry[i];

33         arry[i] = temp;

34         permutation(arry, start+1, length);

35         temp = arry[start];

36         arry[start] = arry[i];

37         arry[i] = temp;    

38     }

39 }

40 int main()

41 {

42     int n;

43     while(cin >> n)

44     {

45         int * arry = new int[n];

46         for(int i = 0; i < n; ++i)

47             arry[i] = i + 1;

48         num = 0;

49         permutation(arry, 0, n);

50         cout << "The number of total solutions is " << num << endl;

51         delete arry;

52     }

53     return 0;

54 }

 1 #include <iostream>

 2 

 3 using namespace std;

 4 

 5 void permutation(int * arry, int start, int length)

 6 {

 7     if(start == length)

 8     {

 9         for(int j = 0; j < length; ++j)

10             cout << arry[j] << " ";

11         cout << endl;

12         return;

13     }

14     for(int i = start; i < length; ++i)

15     {

16         int temp = arry[start];

17         arry[start] = arry[i];

18         arry[i] = temp;

19         permutation(arry, start+1, length);

20         temp = arry[start];

21         arry[start] = arry[i];

22         arry[i] = temp;    

23     }

24 }

25 int main()

26 {

27     int n;

28     while(cin >> n)

29     {

30         int * arry = new int[n];

31         for(int i = 0; i < n; ++i)

32             arry[i] = i + 1;

33         permutation(arry, 0, n);

34         delete arry;

35     }

36     return 0;

37 }