数学中国2008年美赛B题:sudoku source code

huashi3483

c++

/*PROGRAM FOR SOLVING THE SUDOKU USING 'C'*/

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

int i,j,k,a[10][10],o,x[100],y[100];

void display();
int getnum();
void solve(int [],int [],int);
int check(int ,int );

void main()
{
 clrscr();
 printf("\n\nEnter the elements of SUDOKU in rowwise.\n[ Enter '0' if element is absent. ]");
 for(i=1;i<=9;i++)
 for(j=1;j<=9;j++)
  scanf("%d",&a[j]);
 printf("\n\nEntered SUDOKU\n\n");
 display();
 printf("\nEnter any key for solution....\n");
 getch();
 o=getnum();
 solve(x,y,1);
 }

  int getnum()
  {
   int c=0;
   for(i=1;i<=9;i++)
   {
   for(j=1;j<=9;j++)
   {
    if(a[j]==0)
    {
     c++;
     x[c]=i;
     y[c]=j;
     }
    }
   }
   return(c);
  }

  void display()
  {
   for(i=1;i<=9;i++)
   {
    for(j=1;j<=9;j++)
    {
     if(a[j]!=0)
      printf("  %d",a[j]);
     else
      printf("  ");
     }
     printf("\n\n");
    }
   }


   void solve(int p[100],int q[100],int n)
   {
    for(k=1;k<=9;k++)
    for(i=p[n];i<=p[n];i++)
    for(j=q[n];j<=q[n];j++)
    {
     a[j]=k;
     if(n<0)
      solve(p,q,n++);
     int ch=check(1,0);
     if(ch!=0)
     {
      display();
      getch();
      exit(0);
      }
     }
    }
   }

   int check(int n,int r)
   {
    int f=0,cont=0;
    if(r==1)
    {
     for(k=1;k<=9;k++)
     {
      for(i=n;i<=n;i++)
      for(j=1;j<=9;j++)
      {
       if(k==a[j])
 f++;
       }
       if(f!=1)
 return(0);
       else
 cont++;
       f=0;
 }
 if(cont!=9)
  return(0);
 else if(n==9)
  check(1,0);
 else
  check(n++,1);
 }
 else
 {
  for(k=1;k<=9;k++)
  {
   for(i=1;i<=9;i++)
   for(j=n;j<=n;j++)
   {
    if(k==a[j])
     f++;
    }
    if(f!=1)
     return(0);
    else
     cont++;
                   f=0;
    }
    if(cont!=9)
     return(0);
    else if(n!=9)
     check(n++,1);
     }
    }

[此贴子已经被作者于2008-2-16 1:12:52编辑过]

huashi3483

Java code

http://blogs.msdn.com/dotnetinterop/archive/2006/02/15/re-use-of-existing-java-code-sudoku-engine.aspx

huashi3483

c#

http://www.codeproject.com/KB/game/sudokuincsharp.aspx

http://www.codeproject.com/KB/smart/SudokuSmartClient.aspx

[此贴子已经被作者于2008-2-16 1:05:53编辑过]

huashi3483

FormulaOne Compiler

http://www.f1compiler.com/samples/Sudoku.f1.html

huashi3483

Python scripts

http://www.eddaardvark.co.uk/sudoku/sudokusource.html

enewsky

#include <iostream>
#include <ctime>
#include <vector>
using namespace std;

/**********初始9?的矩阵*************/
/******元素为0，说明该位置还未填充***/
int MATRIX[9][9]={ {0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,0,0,0,0} };

/*******初始给出的元素个数***********/
int INITIAL_COUNT;

/********已填充元素个数，作为填充结束标志**********/
int FINISH_COUNT=0;

/********各个元素的初始候选集合*******/

vector<vector<int> > IVEC(81);

/**************函数原型******************/

/*********得到初始给出的元素个数*******/
int get_initialcount();

/*******初始化候选集合***************/
void initial_candidate();
/***********从vector中删除指定元素*******/
void delete_value(vector<int> &ivec,int value);

/********更新候选集合**************/
void refresh_candidate();

/*********返回9?候选集合元素最少的候选集合序号*******/
int min_seq();

/********随机生成一个位置序号并取得该序号所对应的元素值******/
int choose_seq(int min_seq);

/*******填充该元素并判断是否填充完毕********/
int is_finish(int min_seq, int choose_value);

int main()
{
/******得到初始给出的元素个数*****/
INITIAL_COUNT=get_initialcount();
/******初始化候选集合*******/
initial_candidate();
/********先更新候选集合(为了应付已经填充一部分数的情况)******/
refresh_candidate();
int i;
int MinSeq;
int ChooseValue;
MinSeq=min_seq();
ChooseValue=choose_seq(MinSeq);
while(is_finish(MinSeq,ChooseValue)!=1)
{
refresh_candidate();
MinSeq=min_seq();
ChooseValue=choose_seq(MinSeq);
}
/**********输出填好的数独游戏结果*********/
for( i=0;i<9;++i)
{
for(int j=0;j<9;++j)
{
cout<<MATRIX[j]<<'\t';
}
cout<<endl;
}
return 0;
}

/*******************函数定义***********************/

/*********得到初始给出的元素个数*******/
int get_initialcount()
{
int count=0;
for(int i=0;i<9;++i)
{
for(int j=0;j<9;++j)
{
if(MATRIX[j]!=0)
{
count++;
}
}
}
return count;
}

/*******初始化候选集合***************/
void initial_candidate()
{
for(int i=0;i<81;++i)
{
for(int j=1;j<10;++j)
{
IVEC.push_back(j);
}
}
}

/***********从vector中删除指定元素*******/
void delete_value(vector<int> &ivec,int value)
{
/*******如果ivec已经为空，直接退出**********/
if (ivec.size()==0)
{
return;
}
vector<int>::iterator iter=ivec.begin();
while( iter<ivec.end() && (*iter)!=value )
{
iter++;
}
if(iter<ivec.end())//在vector中找到已填充的元素，把它删除
{
ivec.erase(iter);
}
}

/********更新候选集合**************/
void refresh_candidate()
{
int i;
int rownum,colnum;
int row,col;
/******更新81个vector*******/
for(i=0;i<81;++i)
{
row=i/9;
col=i%9;
if(MATRIX[row][col]!=0)//该位置已经填充
{
if(IVEC.size()!=0)//该vector不空
{
/********删除整个候选集***********/
IVEC.erase(IVEC.begin(),IVEC.end());
}
}
else
{
/*****删除同一行中的元素****/
for(colnum=0;colnum<9;++colnum)
{
delete_value(IVEC,MATRIX[row][colnum]);
}
/*****删除同一列中的元素****/
for(rownum=0;rownum<9;++rownum)
{
delete_value(IVEC,MATRIX[rownum][col]);
}
/*****删除在一个3?方阵中的元素******/

/******在第1块中，删除3?方阵元素*****/
if(row/3==0 && col/3==0)
{
for(int r=0;r<3;++r)
{
for(int c=0;c<3;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第2块中，删除3?方阵元素*****/
if(row/3==0 && col/3==1)
{
for(int r=0;r<3;++r)
{
for(int c=3;c<6;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第3块中，删除3?方阵元素*****/
if(row/3==0 && col/3==2)
{
for(int r=0;r<3;++r)
{
for(int c=6;c<9;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第4块中，删除3?方阵元素*****/
if(row/3==1 && col/3==0)
{
for(int r=3;r<6;++r)
{
for(int c=0;c<3;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第5块中，删除3?方阵元素*****/
if(row/3==1 && col/3==1)
{
for(int r=3;r<6;++r)
{
for(int c=3;c<6;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第6块中，删除3?方阵元素*****/
if(row/3==1 && col/3==2)
{
for(int r=3;r<6;++r)
{
for(int c=6;c<9;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第7块中，删除3?方阵元素*****/
if(row/3==2 && col/3==0)
{
for(int r=6;r<9;++r)
{
for(int c=0;c<3;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第8块中，删除3?方阵元素*****/
if(row/3==2 && col/3==1)
{
for(int r=6;r<9;++r)
{
for(int c=3;c<6;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

/******在第9块中，删除3?方阵元素*****/
if(row/3==2 && col/3==2)
{
for(int r=6;r<9;++r)
{
for(int c=6;c<9;++c)
{
delete_value(IVEC,MATRIX[r][c]);
}
}
}

}
}
}

/*********返回9?候选集合元素最少的候选集合序号*******/
int min_seq()
{
int count[81];
int i;
for(i=0;i<81;++i)
{
count=IVEC.size();

}
int value=10;
int min_seq;
for(i=0;i<81;++i)
{
if(count==0)
{
continue;
}
if(count<value)
{
value=count;
min_seq=i;
}
}
return min_seq;
}

/********随机生成一个位置序号并取得该序号所对应的元素值******/
int choose_seq(int min_seq)
{
/*****根据当前时间设置种子******/
srand((unsigned)time( NULL ));
int random_seq=rand()%(IVEC[min_seq].size());
return IVEC[min_seq][random_seq];
}

/*******填充该元素并判断是否填充完毕********/
int is_finish(int min_seq, int choose_value)
{
int row, column;
row=min_seq/9;
column=min_seq%9;
MATRIX[row][column]=choose_value;
FINISH_COUNT++; /****已填充元素个数加1*****/
/*******填充完毕判断********/
if(FINISH_COUNT==81-INITIAL_COUNT)
{
return 1;
}
else
{
return 0;
}
}

yongzlee

贴这些东西有意思吗?

iori1986iori

貌似和我发的帖子一样哈

szj2008

貌似和我发的帖子一样

bsfslxh

谢谢~~~~~~~