[Recursion:Backtracking, 깊이우선 탐색 예제] N-Queen C#

N * N 체스판에 최대한 많은 Queen을 놓고 싶다. 다만, 서로를 공격하지 않게 올려놓고 싶다. 총 몇 가지 경우의 수가 있을까?

<N-Queen>

🎡 BackTracking

 

백트래킹의 대표적인 문제로 N-Queen으로 공부해보았다. N-Queen이란 N*N의 체스판에서 서로를 잡아먹지 않는 선에서 최대한 많은 수의 퀸을 두는 문제이다. 한 행에는 같은 선상에는  퀸을 1개만 배치할 수 있으므로 N* N배열에서 최대 개수는 N개가 될 것이다. 이것의 위치를  한정조건 없이 탐색할 경우 엄청나게 많은 조합의 경우가 탄생한다(O(N^N)).

 

첫 행에 체스말을 배치시켰을 경우 그 다음행에서 배치말이 유효한 칸이 있는지(둘 수 있는 칸인지) 검사 한뒤 없다면 이를 배제하고 그 전 행으로 되돌아간 뒤 , 다음 노드를 검사한다. 만약 최대값이 도출 되지 않는 노드라면 다시 그전전 노드로 돌아가 이 작업을 반복한다. 이렇게 검사하며 최종값이 N이 나오게 된다면 True로 반환한뒤 이 값을 반환하는 방식이다. 

 

이를 구현하는 방식에는 Recursion(재귀) 와 Stack(스택)을 이용하는 방식이  있는데 직관적이고 간단한 방법으로 Recursion을 사용해 보았다. (C#)

 

< 4*4 N-Queen >

---

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Simulation
{
    //백트래킹(BackTracking) , 깊이 우선 탐색
    class Program
    {
        public static int N = 8; // 8*8 체스칸 
        public static int[] cols = new int[N + 1];
        
        public static bool queens(int level)
        {       	
            if (!promising(level))
            {
                return false;
            }
            //최댓값일시 end
            else if(level == N)
            {
                for(int i = 1; i <= N; i++)
                {
                    Console.WriteLine("("+i+","+cols[i] +")");
                }
                return true;
            }
            else
            {
            // 중간 노드시 재귀
                for(int i = 1; i <= N; i++)
                {
                    cols[level + 1] = i;
                    if (queens(level + 1))
                    {
                        return true;
                    }
                }
                return false;
            }
        }
        //유효성 검사
        public static bool promising(int level)
        {
            for(int i = 1; i < level; i++)
            {
            	// 같은 열인지 검사
                if(cols[i] == cols[level])
                {
                    return false;
                }
                // 대각선 검사 ((절대값 x-y열의 차)
                else if(level-i == Math.Abs(cols[level]- cols[i]))
                {
                    return false;
                }              
            }
            return true;
        }

        public static void Main(string[] args)
        {
            queens(0);
        }

    }
}

cols에 값을 저장하면서 유효성을 검사하는 방식이다.  만약 값을 1개 도출이 아니라 여러 조건을 반환해야 한다면 특정 조건에 한해 조합을 카운트하거나 리스트에 저장하면 될것이다. 

 

8*8의 실행 예시