DFS를 이용한 스도쿠 문제 풀이 알고리즘

#include <iostream>
using namespace std;
int sdocu[9][9]={0};         // 정답을 저장할 배열
int success = 0;               // 성공변수
int dfs(int c, int r)
{
         if(c==9)                  // 끝에 도달시
         {
                success = 1;
                return 0;
         }
         if(sdocu[c][r]!=0)    // 숫자가 있다면
         {
                if(r==8)
                {
                          c++;
                          r=0;
                }
                else
                {
                          r++;
                }
                dfs(c, r);
                if(success==1)
                {
                          return 0;
                } 
                if(r==0)           // 되돌아가기
                {
                          c--;
                          r=8;
                }              
                else
                {
                          r--;
                }
                return 0;
        }
        else
        {
                int temparr[9]={1,2,3,4,5,6,7,8,9};  // 빈칸에 들어갈 수 있는 숫자배열
                for(int i = 0; i < 9 ; i++)
                {
                        for(int j = 0 ; j < 9 ; j++)
                        {
                               if(sdocu[c][i]==temparr[j] || sdocu[i][r]==temparr[j]) // 가로줄 세로줄에 있는 숫자 제외
                               {
                                         temparr[j]=0;
                               }
                        }
               }
               int l = (c/3)*3;               // 포함된 정사각형 영역 숫자 제외
               int m = (r/3)*3;         
               for(int i = l ; i < l+3 ;i++)
               {
                             for(int j = m ; j < m+3 ; j++)
                            {
                                        for(int k = 0 ; k < 9 ; k++)
                                       {
                                                  if(sdocu[i][j]==temparr[k])
                                                  {
                                                             temparr[k]=0;
                                                  }
                                        }
                            }
              }
              for(int i = 0 ; i < 9 ; i++)             // 빈칸에 숫자대입
              {
                           if(temparr[i]!=0)
                           {
                                       sdocu[c][r]=temparr[i];
                                       if(r==8)
                                       {
                                                  c++;
                                                  r=0;
                                       } 
                                      else
                                      {
                                                  r++;
                                      }
                                      dfs(c, r);
                                      if(success==1)
                                      {
                                                 return 0;
                                      }    
                                     
                                      if(r==0)                           //되돌아가기
                                      {
                                                 c--;
                                                 r=8;
                                      }
                                      else
                                      {
                                                 r--;
                                      }
                            }
                }
                sdocu[c][r]=0;
                return 0;
        }
}
int main()
{
       char temp[10]={0};
       cout<<"intput data : "<<endl;
       for(int i = 0; i < 9; i++)
       {
               cin>>temp;
               for(int j = 0 ; j < 9 ; j++)   // 숫자 입력
               {
                         sdocu[i][j]=temp[j]-'0';
               }
      }
      cout<<endl<<"output data : "<<endl;
 
      dfs(0, 0);
 
      for(int i = 0; i < 9 ; i++)
      {
               for(int j = 0 ; j < 9 ; j++)
               {
                       cout<<sdocu[i][j];
               }
               cout<<endl;
      }
      system("pause");
      return 0;
}

 

dakuo_sdocu.exe

dakuo_sdocu_main.cpp