[8]

1. 하노이의 탑

https://namu.wiki/w/%ED%95%98%EB%85%B8%EC%9D%B4%EC%9D%98%20%ED%83%91

// 원반 no를 시작기둥x에서 목표기둥y로 이동
void move(int no, int x, int y){
        if(no>1)
                move(no-1,x,6-x-y); // 그룹을 시작기둥에서 중간기둥으로
        printf("won[%d] %d -> %d gidong\n",no,x,y); // 바닥원반을 목표기둥으로
        if(no>1)
                move(no-1,6-x-y,y); // 그룹을 중간기둥에서 목표기둥으로
}

2. 8퀸 문제

https://namu.wiki/w/%EC%97%AC%EB%8D%9F%20%ED%80%B8%20%EB%AC%B8%EC%A0%9C

(가지 뻗기) 모든 조합을 나열하는 프로그램

int pos[8]; // 각 열에서 퀸의 위치
void set(int i){
	int j;
    for(j=0; j<8; j++){
    	pos[i] = j; // i열에 j행 배치
        if(i ==7) print(); // 각 열의 퀸의 위치를 출력하는 함수
        else set(i+1);
    }
}

(분기 한정법) 규칙: 각 행에 퀸을 1개만 배치

int flag[8]; 각 행에 퀸을 배치했는지 체크용
int pos[8]; // 각 열에서 퀸의 배치
void set(int i){
	int i;
    for(j=0; j<8; j++){
    	if(!flag[j]){ // j행에 퀸을 배치하지 않았다면
        	pos[i] = j;
            if(i==7) print();
        }
        else{
        	flag[j] = 1;
            set(i+1);
            flag[j] = 0;
        }
    }
}

(8퀸 정답) 대각선도 고려

#include<stdio.h>

int flag_a[8]; // 각 행에 퀸을 배치했는지
int flag_b[15]; // 대각선 / 에 배치했는지
int flag_c[15]; // 대각선 \ 에 배치했는지
int pos[8]; // 각 열에서의 퀸의 위치

// 각 열에서의 퀸 출력함수
void print(){
        int i;
        for(i=0; i<8; i++) printf("%2d",pos[i]);
        putchar('\n');
}

// i열에 알맞은 위치에 퀸을 배치
void set(int i){
        int j; 
        for(j=0; j<8; j++){
                if(!flag_a[j] &&!flag_b[i+j] && !flag_c[i-j+7]){
                        pos[i] = j;
                        if(i==7) print();
                        else{
                                flag_a[j] = flag_b[i+j] =  flag_c[i-j+7] = 1;
                                set(i+1);
                                flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = 0;
                        }
                }
        }
}

int main(){
        int i;
        for(i=0; i<8; i++) flag_a[i] = 0;
        for(i=0; i<15; i++) flag_b[i] = flag_c[i] = 0;
        set(0);

        return 0;
}

ㅇ위의 코드에서 각 행에 퀸을 하나씩만 놓기위해 flag_a[j] 를 사용하였다.
ㅇ / 대각선에서의 배치를 확인하기위해 flag_b[i+j]를 통해 각 행과 열의 인덱스 값을 더해 대각선으로 있는경우 flag_b[i+j] 값이 같아져서 이를 통해 중복 배치 여부를 확인했다.
ㅇ ＼ 대각선의 경우는 / 대각선과는 다르게 flab_c[i-j+7] 방식으로 인덱스 값을 계산했고 이전과는 다르게 ＼ 방향 대각선으로의 인덱스값이 같아진다.