摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法 : DFS

對每個未填的格子做1~9的猜測,並在搜尋途中把不可能剪枝

需要檢查9宮格 以及橫 直

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
int n,map[10][10]={0};
int top,queue[100][2]={0};
int check(int x,int y,int num)
{
  int a,b;
 
  for(a=0;a<n*n;a++)
     if(map[x][a]==num&&a!=y) return 0;
  for(a=0;a<n*n;a++)
     if(map[a][y]==num&&a!=x) return 0;
  int xx=x/n,yy=y/n;
  xx*=n;
  yy*=n;
 
  for(a=0;a<n;a++)
     for(b=0;b<n;b++)
        if(map[xx+a][yy+b]==num&&(xx+a!=x&&yy+b!=y)) return 0;
  return 1;
}
int find=0;
void DFS(int now)
{
   int a,b;
   if(find==1) return;
  if(now==top)
       {
         find=1;
         for(a=0;a<n*n;a++)
            {
               for(b=0;b<n*n;b++)
                  printf("%d ",map[a][b]);
                  printf("\n");
            }
            return;
       }
 
  for(a=1;a<=n*n;a++)
     if(check(queue[now][0],queue[now][1],a)==1)
       {
         map[queue[now][0]][queue[now][1]]=a;
         DFS(now+1);
         map[queue[now][0]][queue[now][1]]=0;
       }
}
main()
{
 while(scanf("%d",&n)==1)
     {
       int a,b,c;
       top=0;
       int no=0;
       for(a=0;a<n*n;a++)
          for(b=0;b<n*n;b++)
             {
              scanf("%d",&map[a][b]);
              if(map[a][b]==0)
                 {
                 queue[top][0]=a;
                 queue[top][1]=b;
                 top++;
                 }
             }
        for(a=0;a<n*n;a++)
           for(b=0;b<n*n;b++)
              if(map[a][b]!=0)
                    if(check(a,b,map[a][b])==0) no=1;
        find=0;
        if(no==0)
          DFS(0);
        if(find==0) printf("NO SOLUTION\n");
     }
 return 0;
}