심심해서 짜본 N Queen

레이튼 박사와 이상한 마을의 8개의 Queen문제를 풀기 위해 심심해서 N-Queen을 짜 봤다.
옛날에 짜 봤던것 같기도 하던데..
백트래킹이 중요하기도 했던 것 같던데..

여튼 어젯밤 하고 오늘밤 조금 해서 결과물이 나왔다.-ㅁ-a;

N=8
□□Ｑ□□□□□
□□□□□Ｑ□□
□□□Ｑ□□□□
□Ｑ□□□□□□
□□□□□□□Ｑ
□□□□Ｑ□□□
□□□□□□Ｑ□
Ｑ□□□□□□□

N=20
□□□□□□□□□Ｑ□□□□□□□□□□
□□□□□□□□□□□□□Ｑ□□□□□□
□□□□□□□□Ｑ□□□□□□□□□□□
□□□□□□□□□□Ｑ□□□□□□□□□
□□□□□□□□□□□□Ｑ□□□□□□□
□□□□□□Ｑ□□□□□□□□□□□□□
□□□□□□□□□□□□□□□□□Ｑ□□
□□□□□Ｑ□□□□□□□□□□□□□□
□□□□□□□Ｑ□□□□□□□□□□□□
□□□□□□□□□□□□□□□□□□□Ｑ
□□□□□□□□□□□□□□□Ｑ□□□□
□□□□□□□□□□□Ｑ□□□□□□□□
□□□□□□□□□□□□□□Ｑ□□□□□
□□□□□□□□□□□□□□□□Ｑ□□□
□□□□□□□□□□□□□□□□□□Ｑ□
□□Ｑ□□□□□□□□□□□□□□□□□
□□□□Ｑ□□□□□□□□□□□□□□□
□Ｑ□□□□□□□□□□□□□□□□□□
□□□Ｑ□□□□□□□□□□□□□□□□
Ｑ□□□□□□□□□□□□□□□□□□□

여튼 즐거운 마음으로 오늘밤은 살 수 있겠다..
아래는 소우스.

 

#include <Stdio.h>
#include <stdlib.h>
#include <malloc.h>

void init_map (bool * map, int queen_n);
bool find_queen (bool * map, int stage, int queen_n);
void show_map (bool * map, int queen_n);
bool check_map (bool * map, int stage, int queen_n);

int main(int argc, char *argv[])
{
    int queen_n;
    bool *map;

    printf ("Input Queen number: ");
    scanf ("%d",&queen_n);

    map = (bool *) malloc (sizeof(bool)*queen_n*queen_n);

    if (find_queen(map,0,queen_n))
       show_map(map,queen_n);
    else
    {
        printf ("No answer found\n");
        system("pause");
    }
   
   
    return EXIT_SUCCESS;
}

bool check_map (bool * map, int stage, int queen_n)
{
     int i,j,k,q;
     bool return_value;
     return_value=true;
    
     for (i=0;i<queen_n;i++)
     {
         for (j=0;j<queen_n;j++)
         {
             //해당 위치에 퀸이 있으면
             if (map[i*queen_n+j] == true)
             { 
                //show_map(map,queen_n);
                if (
                (i>0 && map[(i-1)*queen_n+j] == true) ||
                (i>0 && j<queen_n && map[(i-1)*queen_n+j+1] == true) ||
                (j<queen_n && map[i*queen_n+j+1] == true) ||
                (i<queen_n && j<queen_n && map[(i+1)*queen_n+j+1] == true) ||
                (i<queen_n && map[(i+1)*queen_n+j] == true) ||
                (i<queen_n && j>0 && map[(i+1)*queen_n+j-1] == true) ||
                (j>0 && map[i*queen_n+j-1] == true) ||
                (i>0 && j>0 && map[(i-1)*queen_n+j-1] == true) )
                {
                        return false;
                }
                else
                {
                     //printf ("%d,%d\n",i,j);
                     //가로
                     for (k=0;k<queen_n;k++)
                     {
                         if ((map[k*queen_n+j] == true) && (k!=i))
                         {
                            return false;
                         }
                     }
                     //세로
                     for (q=0;q<queen_n;q++)
                     {
                         if ((map[i*queen_n+q] == true) && (q!=j))
                         {
                            return false;
                         }
                     }
                     //대각선 1, 상향.
                     k=i;q=j;
                     while (true)
                     {
                           //system("pause");
                           k++;q++;
                           //printf ("k:%d, j:%d\n",k,j);
                           if (k>=queen_n || q>=queen_n) break;
                           if (map[k*queen_n+q]==true)
                           {
                              return false;
                           }
                     }
                     //대각선 1, 하향
                     k=i;q=j;
                     while (true)
                     {
                           k--;q--;
                           if (k<0 || q<0) break;
                           if (map[k*queen_n+q]==true)
                           {
                              return false;
                           }
                     }
                     //대각선 2 좌상향
                     k=i;q=j;
                     while (true)
                     {
                           k--;q++;
                           if (k<0 || q>=queen_n) break;
                           if (map[k*queen_n+q]==true)
                           {
                              return false;
                           }
                     }
                     //대각선 2 우하향
                     k=i;q=j;
                     while (true)
                     {
                           k++;q--;
                           if (k>=queen_n||q<0) break;
                           if (map[k*queen_n+q]==true)
                           {
                              return false;
                           }
                     }
                    
                     if (return_value==false)
                        break;
                }
             }
         }
     }
     return return_value;  
}

bool find_queen (bool * map,int stage,int queen_n)
{
     int j;
     //printf ("stage:%d, Queen_ n:%d\n",stage,queen_n);
     //system("PAUSE");
     //Employ somewhere.
     for (j=0;j<queen_n;j++)
     {
         //printf ("%d th iteration\n",j+1);
         map[queen_n*stage+j]=true;
         //show_map(map,queen_n);
         if (check_map(map,stage,queen_n)==true)
         {
            //printf ("x:%d, y:%d\n",stage,j);
            //show_map(map,queen_n);
            if (stage+1 == queen_n)
               return true;
            else
                if (find_queen (map, stage+1, queen_n) == true)
                    return true;
                else
                    map[queen_n*stage+j]=false;
         }
         else
             map[queen_n*stage+j]=false;
     }
     return false;
}

void show_map (bool * map, int queen_n)
{
     int i,j;
    
     for (i=queen_n-1;i>=0;i--)
     {
         for (j=0;j<queen_n;j++)
             if (map[j*queen_n+i]==true)
                printf ("Ｑ");
             else
                printf ("□");
         printf ("\n");
     }
     system("PAUSE");
     //system("pause");
}

void init_map (bool * map, int queen_n)
{
     int i,j;
     for (i=0;i<queen_n;i++)
         for (j=0;j<queen_n;j++)
             map[i*queen_n+j]=false;
}