C\#재 귀 알고리즘 으로 8 황후 문 제 를 해결 합 니 다.

1.도입부
중국 에는'남쪽 벽 에 부 딪 히 지 않 으 면 뒤 돌아 보지 않 는 다'는 옛말 이 있 습 니 다.한 사람의 고집 을 생동감 있 게 설명 하고 나 쁜 뜻 이 있 습 니 다.그러나 소프트웨어 프로 그래 밍 에서 이런 사 고 는 문 제 를 해결 하 는 가장 간단 한 알고리즘 입 니 다.이 는 무지막지 한 사고 와 비슷 한 사 고 를 통 해 한 걸음 한 걸음 앞으로 나 아가 목표 결과 에 더욱 가 깝 습 니 다.장애물 에 부 딪 힐 때 까지.우 리 는 비로소 돌아 갈 생각 을 했다.그리고 앞으로 계속 시도 해 보 세 요.이런 파도 식 전진 방법 을 통 해 최종 적 으로 목적지 에 도달 하 다.물론 전체 과정 은 왕복 이 많이 필요 하 다.이런 전진 방식 은 효율 이 비교적 낮다.
2.적용 범위
간단명료 한 수학 모델 이 존재 하지 않 아 문제 의 본질 을 밝 히 거나 수학 모델 이 존재 하지만 실현 하기 어 려 운 문제 에 적용 된다.
3.응용 장면
8*8 체스 판 에 서 는 각 줄 에 황 후 를 하나씩 두 고 세로 방향 으로 할 수 있 도록 해 야 하 며 경사 방향 은 충돌 하지 않 습 니 다.체스 의 바둑판 은 다음 그림 과 같다.

4.분석
기본 적 인 사고방식 은 위의 분석 이 일치 하면 우 리 는 점차적으로 탐색 하 는 방식 으로 먼저 한 방향 에서 앞으로 나 아가 고,들 어 갈 수 있 으 면 들 어가 고,들 어 갈 수 없 으 면 물 러 나 고,다른 경 로 를 시도 한다.우선 체스 의 규칙 을 분석 해 보 자.이런 규칙 들 은 우리 의 전진 을 제한 할 수 있다.즉,우리 가 전진 하 는 도중에 장애물 이다.한 황후 q(x,y)는 다음 과 같은 조건 을 만족 시 킬 수 있 는 황후 q(row,col)에 게 먹 힐 수 있다.
1)x=row(세로 로 두 황후 가 있 으 면 안 된다)
2)y=col(가로)
3）col + row = y+x;（사선
4）col - row = y-x;（배 틀
상술 한 문제 중의 하 나 를 만 났 을 때,우 리 는 이미 장애 에 부 딪 혔 기 때문에 계속 앞으로 나 아 갈 수 없다 는 것 을 설명 한다.우 리 는 다른 경 로 를 시도 하기 위해 서 되 돌아 와 야 한다.
우 리 는 바둑판 을 8*8 의 배열 로 본다.이렇게 하면 무지막지 한 사고방식 으로 이 문 제 를 해결 할 수 있다.그러면 우 리 는 8*8=64 개의 칸 에서 8 개의 조합 을 꺼 낼 수 있다.C(64,80)=4426165368.분명히 이 숫자 는 매우 크다.무지막지 한 것 을 바탕 으로 우 리 는 역 추적 을 늘 릴 수 있다.0 열 부터 우 리 는 한 열 씩 진행 할 수 있다.0 줄 에서 7 줄 까지 기 존 황후 의 공격 을 받 지 않 는 위 치 를 찾 습 니 다.5 열 은 황후 의 안전 한 위 치 를 찾 지 못 한 다 는 것 을 알 게 될 것 입 니 다.앞의 4 열 은 다음 과 같 습 니 다.

5 열 에 있 을 때 모든 줄 을 배치 하면 이미 존재 하 는 황후 의 공격 을 보 여 줍 니 다.이때 우 리 는 우리 가 남쪽 벽 에 부 딪 혔 다 고 생각 합 니 다.고 개 를 돌 릴 때 입 니 다.우 리 는 1 열 을 뒤로 물 러 나 원래 4 열 에 놓 여 있 던 황후(3,4)를 가 져 갑 니 다.(3,4)이 자리 부터 우 리 는 4 열 에서 다음 안전 위 치 를 찾 습 니 다(7,4).5 열 까지 계속 하면 5 열 은 안전 한 위치 가 없 는 것 을 발견 하고 4 열 로 거 슬러 올 라 갑 니 다.이때 4 열 도 막 다른 골목 입 니 다.우 리 는 3 열 로 거 슬러 올 라 갑 니 다.이렇게 몇 걸음 전진 하고 한 걸음 뒤로 물 러 나 서 8 열 에서 안전 한 위치(성공)를 찾 거나 1 열 은 막 다른 골목 이 었 습 니 다.그러나 8 열 은 안전 한 위 치 를 찾 지 못 했 습 니 다.
요약 하면 8 황후 문 제 를 역 추적 하 는 방법 으로 해결 하 는 절 차 는 다음 과 같다.
1)1 열 부터 황후 의 안전 한 위 치 를 찾 아 다음 열 로 뛰 어 내린다.
2)n 열 에 막 다른 골목 이 생기 면 1 열 이 되면 바둑 이 실패 하고 그렇지 않 으 면 이전 열 로 물 러 나 거 슬러 올라간다.
3)8 열 에서 안전 한 위 치 를 찾 으 면 바둑 이 성공 한다.
8 개의 황 후 는 모두 안전 한 위 치 를 찾 아 바둑판 의 성공 을 대표 한다.길이 가 8 인 정수 배열 queenList 로 성공 적 으로 배 치 된 8 개의 황 후 를 대표 한다.배열 색인 은 바둑판 의 col 벡터 를 대표 하고 배열 의 값 은 바둑판 의 row 방향 이다.
양,그래서(row,col)의 황 후 는(queenList[col],col)라 고 표시 할 수 있 습 니 다.위의 그림 에서 몇 명의 황 후 는 다음 과 같이 표시 할 수 있 습 니 다.
queenList[0] = 0;  queenList[1] = 3;   queenList[2] = 1;  queenList[3] = 4;   queenList = 2;
우 리 는 어떻게 프로그램 을 설계 하 는 지 보 자.
우선(row,col)이 안전 한 위치 인지 아 닌 지 를 판단 하 는 알고리즘:

bool IsSafe(int col,int row,int[] queenList)
{
 //       
 for (int tempCol = 0; tempCol < col; tempCol++)
 {
  int tempRow = queenList[tempCol];
  if (tempRow == row)
  {
   //   
   return false;
  }
  if (tempCol == col)
  {
   //   
   return false;
  }
  if (tempRow - tempCol == row - col || tempRow + tempCol == row + col)
  {
   return false;
  }
 }
 return true;
}

col 열 후의 황후 배치 방법 을 찾 는 함수 설정:

/// <summary>
///   col      row 
/// </summary>
/// <param name="queenList"></param>
/// <param name="col"></param>
/// <returns></returns>
public bool PlaceQueue(int[] queenList, int col)
{
 int row = 0;
 bool foundSafePos = false;
 if (col == 8) //    
 {
  //     8    
  foundSafePos = true;
 }
 else
 {
  while (row < 8 && !foundSafePos)
  {
   if (IsSafe(col, row, queenList))
   {
    //      
    queenList[col] = row;
    //         
    foundSafePos = PlaceQueue(queenList, col + 1);
    if (!foundSafePos)
    {
     row++;
    }
   }
   else
   {
    row++;
   }
  }
 }
 return foundSafePos;
}

호출 방법:

static void Main(string[] args)
{
 EightQueen eq = new EightQueen();
 int[] queenList = new int[8];
 for (int j = 0; j < 8; j++)
 {
  Console.WriteLine("-----------------"+j+"---------------------");
  queenList[0] = j;
  bool res = eq.PlaceQueue(queenList, 1);

  if (res)
  {
   Console.Write(" ");  
   for (int i = 0; i < 8; i++)
   {
    Console.Write(" " + i.ToString() + " ");  
   }
   Console.WriteLine("");
   for (int i = 0; i < 8; i++)
   {
    Console.Write(" "+i.ToString()+" ");      
    for (int a = 0; a < 8; a++)
    {       
     if (i == queenList[a])
     {
      Console.Write(" q ");
     }
     else
     {
      Console.Write(" * ");
     }
    }
    Console.WriteLine("");
      
   }
   
   Console.WriteLine("---------------------------------------");
  }
  else
  {
   Console.WriteLine("      ，    ！");
  }
 }
 Console.Read();
}

재 귀 알고리즘 Place Queue,이러한 기능 을 완성 합 니 다.col 열 후의 황후 의 안전 한 배치 위 치 를 찾 습 니 다.만약 에 이 함수 가 false 로 돌아 가면 현재 막 다른 골목 에 들 어 갔 음 을 나타 내 고 0-7 열 까지 거 슬러 올 라 가 야 합 니 다.
안전 한 위치 에 도착 하거나 이 열 을 다 찾 아 도 안전 한 위 치 를 찾 지 못 할 때 종료 합 니 다.
8 황후 문 제 를 재 귀 알고리즘 으로 해결 하 는 예제 프로그램:
http://xiazai.jb51.net/201606/yuanma/EightQueens(jb51.net).rar