C語言 數獨解題程式

//=================================================================
// 20090501 知識 +
// http://tw.knowledge.yahoo.com/question/question?qid=1009050109126
// 發問者 : (小小) http://tw.knowledge.yahoo.com/my/my?show=AE03326172
//=================================================================

#include <stdio.h>
#include <stdlib.h>

void Show(int b[][9]);
int Promising(int b[][9], int n);
int Tracking(int b[][9], int n);

int Sol[9*9];
int Cnt=0;
int Ans=0;

int main()
{
  int board[9][9] = {
   { 0, 0, 0, 0, 5, 0, 0, 0, 0 },
   { 0, 7, 0, 0, 0, 3, 0, 2, 0 },
   { 4, 5, 0, 0, 0, 1, 0, 0, 8 },
   { 0, 0, 2, 7, 0, 0, 0, 0, 5 },
   { 0, 4, 0, 0, 0, 0, 0, 3, 0 },
   { 8, 0, 0, 0, 0, 6, 1, 0, 0 },
   { 6, 0, 0, 9, 0, 0, 0, 4, 1 },
   { 0, 9, 0, 6, 0, 0, 0, 8, 0 },
   { 0, 0, 0, 0, 2, 0, 0, 0, 0 }
  };
  int x, y;
  for (x=0;x<9;x++)
    for (y=0;y<9;y++)
      if (board[x][y]==0)    // 尋找空格
        Sol[Cnt++] = (x<<8)+(y<<4); 
  printf( "\n數獨題目為 --\n" );
  Show(board);
  Promising(board, 0);
  if (Ans==1) printf( "\n這是唯一解的標準數獨題目!!\n" );
  else if (Ans==0) printf( "\n此題無解!!\n" );
  else printf( "\n此題有 %d組多重解!!\n", Ans );
  return 0;
}
// 顯示 --
void Show(int b[][9])
{
  char num[] = " 123456789";
  printf("╔═╤═╤═╦═╤═╤═╦═╤═╤═╗\n");
  for(int x=0; x<9; x++)
  {
    for(int y=0; y<9; y++)
       printf("%s %c", (y%3==0)? "║" :"│",  num[b[x][y]]);
    printf("║");
    if (x==8)
       printf("\n╚═╧═╧═╩═╧═╧═╩═╧═╧═╝\n");
    else if (x%3==2)
       printf("\n╠═╪═╪═╬═╪═╪═╬═╪═╪═╣\n");
    else
       printf("\n╟─┼─┼─╫─┼─┼─╫─┼─┼─╢\n");
  }
}
//
int Tracking(int b[][9], int n)
{
  int xx, yy, m, num, r;
  int x = Sol[n]>>8;
  int y = (Sol[n]>>4)&0x0F;
  for(num=1, r=0; num<=9; num++)
  {
    b[x][y] = num;
    Sol[n] = (Sol[n]&0xFF0) + num;
    for(m=0; m<9; m++)
    {
      xx = x/3*3+m%3;
      yy = y/3*3+m/3;
      if ((m!=y && b[x][m]==b[x][y]) || (m!=x && b[m][y]==b[x][y])
          || (x!=xx && y!=yy && b[xx][yy]==b[x][y]))
        break;
    }
    if (m==9 && Promising(b, n+1)) r=1;
  }
  // backtracking -- 回溯
  b[x][y]=0;
  Sol[n]&=0xFF0;
  return r;
}
//
int Promising(int b[][9], int n)
{
  if (n<Cnt) return Tracking(b, n);
  //-- solution is found
  if (++Ans<2) // 限制只顯示第一組解答
  {
     printf("\n得到第 %d組解答:\n", Ans);
     Show(b);
     printf("\nSolution :");
     for(n=0; n<Cnt; n++)
        printf( "%c[%d,%d]:%d ",(n%8==0)?'\n': ' ', (Sol[n]>>8)+1,
                ((Sol[n]>>4)&0x0F)+1, Sol[n]&0x0F );
     printf("\n");
  }
  return 1;
}