数学中国2008年美赛B题:sudoku source code
<div class="ad_notxt"><div id="1323226810_1"><pre class="code"><font color="#ff0000" size="6"><strong>c++</strong></font></pre><pre class="code">/*PROGRAM FOR SOLVING THE <strong class="highlight">SUDOKU</strong> USING 'C'*/<br/><br/>#include<stdio.h><br/>#include<conio.h><br/>#include<iostream.h><br/>#include<stdlib.h><br/><br/>int i,j,k,a,o,x,y;<br/><br/>void display();<br/>int getnum();<br/>void solve(int [],int [],int);<br/>int check(int ,int );<br/><br/>void main()<br/>{<br/> clrscr();<br/> printf("\n\nEnter the elements of <strong class="highlight">SUDOKU</strong> in rowwise.\n[ Enter '0' if element is absent. ]");<br/> for(i=1;i<=9;i++)<br/> for(j=1;j<=9;j++)<br/> scanf("%d",&a);<br/> printf("\n\nEntered SUDOKU\n\n");<br/> display();<br/> printf("\nEnter any key for solution....\n");<br/> getch();<br/> o=getnum();<br/> solve(x,y,1);<br/> }<br/><br/> int getnum()<br/> {<br/> int c=0;<br/> for(i=1;i<=9;i++)<br/> {<br/> for(j=1;j<=9;j++)<br/> {<br/> if(a==0)<br/> {<br/> c++;<br/> x=i;<br/> y=j;<br/> }<br/> }<br/> }<br/> return(c);<br/> }<br/><br/> void display()<br/> {<br/> for(i=1;i<=9;i++)<br/> {<br/> for(j=1;j<=9;j++)<br/> {<br/> if(a!=0)<br/> printf(" %d",a);<br/> else<br/> printf(" ");<br/> }<br/> printf("\n\n");<br/> }<br/> }<br/><br/><br/> void solve(int p,int q,int n)<br/> {<br/> for(k=1;k<=9;k++)<br/> for(i=p;i<=p;i++)<br/> for(j=q;j<=q;j++)<br/> {<br/> a=k;<br/> if(n<0)<br/> solve(p,q,n++);<br/> int ch=check(1,0);<br/> if(ch!=0)<br/> {<br/> display();<br/> getch();<br/> exit(0);<br/> }<br/> }<br/> }<br/> }<br/><br/> int check(int n,int r)<br/> {<br/> int f=0,cont=0;<br/> if(r==1)<br/> {<br/> for(k=1;k<=9;k++)<br/> {<br/> for(i=n;i<=n;i++)<br/> for(j=1;j<=9;j++)<br/> {<br/> if(k==a)<br/> f++;<br/> }<br/> if(f!=1)<br/> return(0);<br/> else<br/> cont++;<br/> f=0;<br/> }<br/> if(cont!=9)<br/> return(0);<br/> else if(n==9)<br/> check(1,0);<br/> else<br/> check(n++,1);<br/> }<br/> else<br/> {<br/> for(k=1;k<=9;k++)<br/> {<br/> for(i=1;i<=9;i++)<br/> for(j=n;j<=n;j++)<br/> {<br/> if(k==a)<br/> f++;<br/> }<br/> if(f!=1)<br/> return(0);<br/> else<br/> cont++;<br/> f=0;<br/> }<br/> if(cont!=9)<br/> return(0);<br/> else if(n!=9)<br/> check(n++,1);<br/> }<br/> }</pre></div><div id="1323226810_2" style="DISPLAY: none;"></div></div>[此贴子已经被作者于2008-2-16 1:12:52编辑过] <p><font color="#ff0000"><strong> Java code</strong></font></p><p>http://blogs.msdn.com/dotnetinterop/archive/2006/02/15/re-use-of-existing-java-code-sudoku-engine.aspx</p> <p><strong><font color="#ff0000" size="6">c#</font></strong></p><p><a href="http://www.codeproject.com/KB/game/sudokuincsharp.aspx">http://www.codeproject.com/KB/game/sudokuincsharp.aspx</a></p><p><a href="http://www.codeproject.com/KB/smart/SudokuSmartClient.aspx">http://www.codeproject.com/KB/smart/SudokuSmartClient.aspx</a></p>
[此贴子已经被作者于2008-2-16 1:05:53编辑过] <p>Formula<span style="FONT-SIZE: 36pt; COLOR: red;">O</span>ne Compiler </p><p>http://www.f1compiler.com/samples/Sudoku.f1.html</p> <p>Python scripts</p><p>http://www.eddaardvark.co.uk/sudoku/sudokusource.html</p>
1
<p>#include <iostream> <br/>#include <ctime> <br/>#include <vector> <br/>using namespace std; </p><p>/**********初始9?的矩阵*************/ <br/>/******元素为0，说明该位置还未填充***/ <br/>int MATRIX={ {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0}, <br/> {0,0,0,0,0,0,0,0,0} }; </p><p>/*******初始给出的元素个数***********/ <br/>int INITIAL_COUNT; </p><p>/********已填充元素个数，作为填充结束标志**********/ <br/>int FINISH_COUNT=0; </p><p>/********各个元素的初始候选集合*******/ </p><p>vector<vector<int> > IVEC(81); </p><p><br/>/**************函数原型******************/ </p><p>/*********得到初始给出的元素个数*******/ <br/>int get_initialcount(); </p><p>/*******初始化候选集合***************/ <br/>void initial_candidate(); <br/>/***********从vector中删除指定元素*******/ <br/>void delete_value(vector<int> &ivec,int value); </p><p>/********更新候选集合**************/ <br/>void refresh_candidate(); </p><p>/*********返回9?候选集合元素最少的候选集合序号*******/ <br/>int min_seq(); </p><p><br/>/********随机生成一个位置序号并取得该序号所对应的元素值******/ <br/>int choose_seq(int min_seq); </p><p>/*******填充该元素并判断是否填充完毕********/ <br/>int is_finish(int min_seq, int choose_value); </p><p><br/>int main() <br/>{ <br/> /******得到初始给出的元素个数*****/ <br/> INITIAL_COUNT=get_initialcount(); <br/> /******初始化候选集合*******/ <br/> initial_candidate(); <br/> /********先更新候选集合(为了应付已经填充一部分数的情况)******/ <br/> refresh_candidate(); <br/> int i; <br/> int MinSeq; <br/> int ChooseValue; <br/> MinSeq=min_seq(); <br/> ChooseValue=choose_seq(MinSeq); <br/> while(is_finish(MinSeq,ChooseValue)!=1) <br/> { <br/> refresh_candidate(); <br/> MinSeq=min_seq(); <br/> ChooseValue=choose_seq(MinSeq); <br/> } <br/> /**********输出填好的数独游戏结果*********/ <br/> for( i=0;i<9;++i) <br/> { <br/> for(int j=0;j<9;++j) <br/> { <br/> cout<<MATRIX<<'\t'; <br/> } <br/> cout<<endl; <br/> } <br/> return 0; <br/>} </p><p>/*******************函数定义***********************/ </p><p>/*********得到初始给出的元素个数*******/ <br/>int get_initialcount() <br/>{ <br/>int count=0; <br/>for(int i=0;i<9;++i) <br/>{ <br/>for(int j=0;j<9;++j) <br/>{ <br/>if(MATRIX!=0) <br/>{ <br/>count++; <br/>} <br/>} <br/>} <br/>return count; <br/>} </p><p><br/>/*******初始化候选集合***************/ <br/>void initial_candidate() <br/>{ <br/> for(int i=0;i<81;++i) <br/> { <br/> for(int j=1;j<10;++j) <br/> { <br/> IVEC.push_back(j); <br/> } <br/> } <br/> } </p><p>/***********从vector中删除指定元素*******/ <br/>void delete_value(vector<int> &ivec,int value) <br/>{ <br/>/*******如果ivec已经为空，直接退出**********/ <br/>if (ivec.size()==0) <br/>{ <br/>return; <br/>} <br/> vector<int>::iterator iter=ivec.begin(); <br/> while( iter<ivec.end() && (*iter)!=value ) <br/> { <br/> iter++; <br/> } <br/> if(iter<ivec.end())//在vector中找到已填充的元素，把它删除 <br/> { <br/> ivec.erase(iter); <br/> } <br/> } </p><p><br/>/********更新候选集合**************/ <br/>void refresh_candidate() <br/>{ <br/> int i; <br/> int rownum,colnum; <br/> int row,col; <br/> /******更新81个vector*******/ <br/> for(i=0;i<81;++i) <br/> { <br/> row=i/9; <br/> col=i%9; <br/> if(MATRIX!=0)//该位置已经填充 <br/> { <br/> if(IVEC.size()!=0)//该vector不空 <br/> { <br/> /********删除整个候选集***********/ <br/> IVEC.erase(IVEC.begin(),IVEC.end()); <br/> } <br/> } <br/> else <br/> { <br/> /*****删除同一行中的元素****/ <br/> for(colnum=0;colnum<9;++colnum) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> /*****删除同一列中的元素****/ <br/> for(rownum=0;rownum<9;++rownum) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> /*****删除在一个3?方阵中的元素******/ </p><p> /******在第1块中，删除3?方阵元素*****/ <br/> if(row/3==0 && col/3==0) <br/> { <br/> for(int r=0;r<3;++r) <br/> { <br/> for(int c=0;c<3;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第2块中，删除3?方阵元素*****/ <br/> if(row/3==0 && col/3==1) <br/> { <br/> for(int r=0;r<3;++r) <br/> { <br/> for(int c=3;c<6;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第3块中，删除3?方阵元素*****/ <br/> if(row/3==0 && col/3==2) <br/> { <br/> for(int r=0;r<3;++r) <br/> { <br/> for(int c=6;c<9;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第4块中，删除3?方阵元素*****/ <br/> if(row/3==1 && col/3==0) <br/> { <br/> for(int r=3;r<6;++r) <br/> { <br/> for(int c=0;c<3;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第5块中，删除3?方阵元素*****/ <br/> if(row/3==1 && col/3==1) <br/> { <br/> for(int r=3;r<6;++r) <br/> { <br/> for(int c=3;c<6;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第6块中，删除3?方阵元素*****/ <br/> if(row/3==1 && col/3==2) <br/> { <br/> for(int r=3;r<6;++r) <br/> { <br/> for(int c=6;c<9;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第7块中，删除3?方阵元素*****/ <br/> if(row/3==2 && col/3==0) <br/> { <br/> for(int r=6;r<9;++r) <br/> { <br/> for(int c=0;c<3;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第8块中，删除3?方阵元素*****/ <br/> if(row/3==2 && col/3==1) <br/> { <br/> for(int r=6;r<9;++r) <br/> { <br/> for(int c=3;c<6;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> /******在第9块中，删除3?方阵元素*****/ <br/> if(row/3==2 && col/3==2) <br/> { <br/> for(int r=6;r<9;++r) <br/> { <br/> for(int c=6;c<9;++c) <br/> { <br/> delete_value(IVEC,MATRIX); <br/> } <br/> } <br/> } </p><p> } <br/> } <br/>} </p><p>/*********返回9?候选集合元素最少的候选集合序号*******/ <br/>int min_seq() <br/>{ <br/> int count; <br/> int i; <br/> for(i=0;i<81;++i) <br/> { <br/> count=IVEC.size(); </p><p> } <br/> int value=10; <br/> int min_seq; <br/> for(i=0;i<81;++i) <br/> { <br/> if(count==0) <br/> { <br/> continue; <br/> } <br/> if(count<value) <br/> { <br/> value=count; <br/> min_seq=i; <br/> } <br/> } <br/> return min_seq; <br/>} </p><p>/********随机生成一个位置序号并取得该序号所对应的元素值******/ <br/>int choose_seq(int min_seq) <br/>{ <br/> /*****根据当前时间设置种子******/ <br/> srand((unsigned)time( NULL )); <br/> int random_seq=rand()%(IVEC.size()); <br/> return IVEC; <br/>} </p><p>/*******填充该元素并判断是否填充完毕********/ <br/>int is_finish(int min_seq, int choose_value) <br/>{ <br/> int row, column; <br/> row=min_seq/9; <br/> column=min_seq%9; <br/> MATRIX=choose_value; <br/> FINISH_COUNT++; /****已填充元素个数加1*****/ <br/> /*******填充完毕判断********/ <br/> if(FINISH_COUNT==81-INITIAL_COUNT) <br/> { <br/> return 1; <br/> } <br/> else <br/> { <br/> return 0; <br/> } <br/>} </p> <p>贴这些东西有意思吗?</p><p></p> <font color="#000000">貌似和我发的帖子一样哈</font> 貌似和我发的帖子一样 谢谢~~~~~~~
页:
[1]
2