用C语言如何随机生成一个数独
发布时间:2025-05-14 09:30:40 发布人:远客网络
一、用C语言如何随机生成一个数独
数独生成算法？这个还真不好搞，不过我当初写数独游戏的时候随便捣鼓出来过一个，你自己去改改吧，至于这个算法能不能生成所有的数独，我还真没论证过。
原理：对一个给出的数独棋盘的所有行或列交换给出的两个数X、Y，数组仍满足数独规则。如给出1、2，则对所有列交换1、2的位置，数组仍满足数独规则。
由于对棋盘的演进是随机的，所以相当于随机生成数独棋盘啦。每次演进的次数最好大一点，10次以上吧，以保证每个数都被换过位置。
具体代码就不用我写了吧，嘎嘎……
二、用c语言写一个简易数独的思路。要代码
1、if((xy[x][y]==xy[i][y]&&i!=x)||(xy[x][y]==xy[x][i]&&i!=y))
2、for(i=0,m=x/3*3,n=y/3*3;i<9;i++)
3、if(xy[x][y]==xy[m+i/3][n+i%3]&&m+i/3!=x&&n+i%3!=y)
4、for(xy[x][y]=1;xy[x][y]<=9;xy[x][y]++)
5、}
输入为9行9列整数，已知的整数填写对应的数字，尚待计算的未知数字填写0。
6、输入为9行9列整数，已知的整数填写对应的数字，尚待计算的未知数字填写0。
7、该代码的思路很简单，就是从第一行第一列开始依次填入数字，检查是否是在同一行、同一列、同一宫有没有填入重复数字，如果没有就继续填入下一个数字，如果有就返回。
8、虽然效率稍低，但原理简单、表述直白、易于理解，更有效率的代码是使用十字链表完成，如有兴趣可继续深入
三、求数独源码
int tempNum[81];//上一次填数位置
int tempSp= 0;//上一次填数位置指标
int startB[81];//九宫格位置的起点
int addB[9];//九宫格位置的加值
int main(int argc, char*argv[]){
if(argc>1) for(j=0; j<81; j++) sudoku[j]= argv[1][j]-'0';
//参数设定(设定这些参数之后，无论检查行、列、九宫格都方便多了)
startH[i]= i/9* 9;//列位置的起点
startV[i]= i% 9;//行位置的起点
startB[i]=((i/9)/3)*27+((i%9)/3)*3;//九宫格位置的起点
addB[i]=(i/3)*9+(i%3);//九宫格位置的加值
int sp=getNextBlank(-1);//取得第一个空白的位置开始填入数字
sudoku[sp]++;//将本位置数字加 1
if(sudoku[sp]>9){//如果本位置的数字已大於 9时则回到上一个位置继续测试
if(check(sp)==0){//如果同行、列、九宫格都没有相同的数字，则到下一个空白处继续
push(sp);//当然，如果发现有相同的数字时，就需把原位置的数字加 1(所以本处什麼都不做)
} while(sp<81&& sudoku[sp]>0);
//检查同行、列、九宫格有没有相同的数字，若有传回 1
if(!fg) fg= check1(sp, startH[sp], addH);//检查同列有没有相同的数字
if(!fg) fg= check1(sp, startV[sp], addV);//检查同行有没有相同的数字
if(!fg) fg= check1(sp, startB[sp], addB);//检查同九宫格有没有相同的数字
int check1(int sp, int start, int*addnum){
//检查指定的行、列、九宫格有没有相同的数字，若有传回 1
if(sp!=sp1&& sudoku[sp]==sudoku[sp1]) fg++;
else return(tempNum[--tempSp]);
参考资料：算法如下,先构造一个9*9的结构体数组,表示棋盘数据0表示空白未知,结构体中每个元素
包含一个1-9的数组作为备选数字.
构建好一个棋盘之后依次对每个空白位置进行备选数字中进行删除.当前已经填写的数字就全部删除
如果只剩下一个备选数字就将该备选数字填写到棋盘数据中.该算法在AI这个函数中实现.
当无法用AI算法推出结果的时候就进行回朔法,见找到有两个备选数字的元素,选取其中一个,
继续往下填写,直到全部填写上去(结束),或者无法继续填写(某个空白位置没有备选元素).
如果无法继续填写下去就表示最初选择的那个数据是错误的,直接填写另外一个数据到棋盘上.
如此下去就能够填写出棋盘中的所有元素.
unsigned int Data[SIZE]={//未解棋盘数据
const int temp[9]={ 1, 2, 3, 4, 5, 6, 7, 8, 9};
Item():data(0),other(temp,temp+9){}
inline Item& operator=(const Item& src)
inline Item& operator=(int x){
std::copy(temp,temp+sizeof(temp)/sizeof(temp[0]), other.begin());
inline operator int(){return data;}
const int Group1,Group2,Group3;
GroupInfo(int g1,int g2,int g3):Group1(g1),Group2(g2),Group3(g3){}
inline bool operator==(GroupInfo& src){
return((Group1|Group2|Group3)&(src.Group1|src.Group2|src.Group3))?true:false;
GroupInfo( 1<<1, 1<<10, 1<<19),GroupInfo( 1<<1, 1<<11, 1<<19),GroupInfo( 1<<1, 1<<12, 1<<19),GroupInfo( 1<<1, 1<<13, 1<<20),GroupInfo( 1<<1, 1<<14, 1<<20),GroupInfo( 1<<1, 1<<15, 1<<20),GroupInfo( 1<<1, 1<<16, 1<<21),GroupInfo( 1<<1, 1<<17, 1<<21),GroupInfo( 1<<1, 1<<18, 1<<21),
GroupInfo( 1<<2, 1<<10, 1<<19),GroupInfo( 1<<2, 1<<11, 1<<19),GroupInfo( 1<<2, 1<<12, 1<<19),GroupInfo( 1<<2, 1<<13, 1<<20),GroupInfo( 1<<2, 1<<14, 1<<20),GroupInfo( 1<<2, 1<<15, 1<<20),GroupInfo( 1<<2, 1<<16, 1<<21),GroupInfo( 1<<2, 1<<17, 1<<21),GroupInfo( 1<<2, 1<<18, 1<<21),
GroupInfo( 1<<3, 1<<10, 1<<19),GroupInfo( 1<<3, 1<<11, 1<<19),GroupInfo( 1<<3, 1<<12, 1<<19),GroupInfo( 1<<3, 1<<13, 1<<20),GroupInfo( 1<<3, 1<<14, 1<<20),GroupInfo( 1<<3, 1<<15, 1<<20),GroupInfo( 1<<3, 1<<16, 1<<21),GroupInfo( 1<<3, 1<<17, 1<<21),GroupInfo( 1<<3, 1<<18, 1<<21),
GroupInfo( 1<<4, 1<<10, 1<<22),GroupInfo( 1<<4, 1<<11, 1<<22),GroupInfo( 1<<4, 1<<12, 1<<22),GroupInfo( 1<<4, 1<<13, 1<<23),GroupInfo( 1<<4, 1<<14, 1<<23),GroupInfo( 1<<4, 1<<15, 1<<23),GroupInfo( 1<<4, 1<<16, 1<<24),GroupInfo( 1<<4, 1<<17, 1<<24),GroupInfo( 1<<4, 1<<18, 1<<24),
GroupInfo( 1<<5, 1<<10, 1<<22),GroupInfo( 1<<5, 1<<11, 1<<22),GroupInfo( 1<<5, 1<<12, 1<<22),GroupInfo( 1<<5, 1<<13, 1<<23),GroupInfo( 1<<5, 1<<14, 1<<23),GroupInfo( 1<<5, 1<<15, 1<<23),GroupInfo( 1<<5, 1<<16, 1<<24),GroupInfo( 1<<5, 1<<17, 1<<24),GroupInfo( 1<<5, 1<<18, 1<<24),
GroupInfo( 1<<6, 1<<10, 1<<22),GroupInfo( 1<<6, 1<<11, 1<<22),GroupInfo( 1<<6, 1<<12, 1<<22),GroupInfo( 1<<6, 1<<13, 1<<23),GroupInfo( 1<<6, 1<<14, 1<<23),GroupInfo( 1<<6, 1<<15, 1<<23),GroupInfo( 1<<6, 1<<16, 1<<24),GroupInfo( 1<<6, 1<<17, 1<<24),GroupInfo( 1<<6, 1<<18, 1<<24),
GroupInfo( 1<<7, 1<<10, 1<<25),GroupInfo( 1<<7, 1<<11, 1<<25),GroupInfo( 1<<7, 1<<12, 1<<25),GroupInfo( 1<<7, 1<<13, 1<<26),GroupInfo( 1<<7, 1<<14, 1<<26),GroupInfo( 1<<7, 1<<15, 1<<26),GroupInfo( 1<<7, 1<<16, 1<<27),GroupInfo( 1<<7, 1<<17, 1<<27),GroupInfo( 1<<7, 1<<18, 1<<27),
GroupInfo( 1<<8, 1<<10, 1<<25),GroupInfo( 1<<8, 1<<11, 1<<25),GroupInfo( 1<<8, 1<<12, 1<<25),GroupInfo( 1<<8, 1<<13, 1<<26),GroupInfo( 1<<8, 1<<14, 1<<26),GroupInfo( 1<<8, 1<<15, 1<<26),GroupInfo( 1<<8, 1<<16, 1<<27),GroupInfo( 1<<8, 1<<17, 1<<27),GroupInfo( 1<<8, 1<<18, 1<<27),
GroupInfo( 1<<9, 1<<10, 1<<25),GroupInfo( 1<<9, 1<<11, 1<<25),GroupInfo( 1<<9, 1<<12, 1<<25),GroupInfo( 1<<9, 1<<13, 1<<26),GroupInfo( 1<<9, 1<<14, 1<<26),GroupInfo( 1<<9, 1<<15, 1<<26),GroupInfo( 1<<9, 1<<16, 1<<27),GroupInfo( 1<<9, 1<<17, 1<<27),GroupInfo( 1<<9, 1<<18, 1<<27)
bool AI(std::vector<Item>& game)
for(size_t x= 0; x< game.size();++x){
if( 0!= game[x].data){//依次检查每个位置
vTemp.push_back( game[i].data);
vTemp.erase( std::remove(vTemp.begin(),vTemp.end(), 0), vTemp.end());
for(std::vector<int>::iterator Iter= vTemp.begin(); Iter!=vTemp.end();++ Iter)
std::replace(game[x].other.begin(), game[x].other.end(),(*Iter), 0);
game[x].other.erase( std::remove(game[x].other.begin(),game[x].other.end(), 0),game[x].other.end());
if(( 1== game[x].other.size())&&( 0!= game[x].other[0])){
game[x].data= game[x].other[0];
{return( item.other.size()==2)?true:false;}
if(( item.data==0)&&(item.other.size()==0))
bool AdvanceAI(std::vector<Item>& game)
std::vector<Item> Back= game;
std::vector<Item>::iterator iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
for(size_t i= 0; i<(*iItem).other.size();++i){
if( std::for_each( Back.begin(), Back.end(), testBackOpt()).bBack){//是否结束回滚
iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
if( std::count( Back.begin(), Back.end(), 0)){//判断是否结束
if( AdvanceAI( Back)){//没有结束，继续下一步递归
iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
int main(int argc, char* argv[])
std::vector<Item> game(SIZE);
std::copy(Data,Data+SIZE, game.begin());
if( std::count( game.begin(), game.end(), 0)){
return 0;算法如下,先构造一个9*9的结构体数组,表示棋盘数据0表示空白未知,结构体中每个元素
包含一个1-9的数组作为备选数字.
构建好一个棋盘之后依次对每个空白位置进行备选数字中进行删除.当前已经填写的数字就全部删除
如果只剩下一个备选数字就将该备选数字填写到棋盘数据中.该算法在AI这个函数中实现.
当无法用AI算法推出结果的时候就进行回朔法,见找到有两个备选数字的元素,选取其中一个,
继续往下填写,直到全部填写上去(结束),或者无法继续填写(某个空白位置没有备选元素).
如果无法继续填写下去就表示最初选择的那个数据是错误的,直接填写另外一个数据到棋盘上.
如此下去就能够填写出棋盘中的所有元素.
unsigned int Data[SIZE]={//未解棋盘数据
const int temp[9]={ 1, 2, 3, 4, 5, 6, 7, 8, 9};
Item():data(0),other(temp,temp+9){}
inline Item& operator=(const Item& src)
inline Item& operator=(int x){
std::copy(temp,temp+sizeof(temp)/sizeof(temp[0]), other.begin());
inline operator int(){return data;}
const int Group1,Group2,Group3;
GroupInfo(int g1,int g2,int g3):Group1(g1),Group2(g2),Group3(g3){}
inline bool operator==(GroupInfo& src){
return((Group1|Group2|Group3)&(src.Group1|src.Group2|src.Group3))?true:false;
GroupInfo( 1<<1, 1<<10, 1<<19),GroupInfo( 1<<1, 1<<11, 1<<19),GroupInfo( 1<<1, 1<<12, 1<<19),GroupInfo( 1<<1, 1<<13, 1<<20),GroupInfo( 1<<1, 1<<14, 1<<20),GroupInfo( 1<<1, 1<<15, 1<<20),GroupInfo( 1<<1, 1<<16, 1<<21),GroupInfo( 1<<1, 1<<17, 1<<21),GroupInfo( 1<<1, 1<<18, 1<<21),
GroupInfo( 1<<2, 1<<10, 1<<19),GroupInfo( 1<<2, 1<<11, 1<<19),GroupInfo( 1<<2, 1<<12, 1<<19),GroupInfo( 1<<2, 1<<13, 1<<20),GroupInfo( 1<<2, 1<<14, 1<<20),GroupInfo( 1<<2, 1<<15, 1<<20),GroupInfo( 1<<2, 1<<16, 1<<21),GroupInfo( 1<<2, 1<<17, 1<<21),GroupInfo( 1<<2, 1<<18, 1<<21),
GroupInfo( 1<<3, 1<<10, 1<<19),GroupInfo( 1<<3, 1<<11, 1<<19),GroupInfo( 1<<3, 1<<12, 1<<19),GroupInfo( 1<<3, 1<<13, 1<<20),GroupInfo( 1<<3, 1<<14, 1<<20),GroupInfo( 1<<3, 1<<15, 1<<20),GroupInfo( 1<<3, 1<<16, 1<<21),GroupInfo( 1<<3, 1<<17, 1<<21),GroupInfo( 1<<3, 1<<18, 1<<21),
GroupInfo( 1<<4, 1<<10, 1<<22),GroupInfo( 1<<4, 1<<11, 1<<22),GroupInfo( 1<<4, 1<<12, 1<<22),GroupInfo( 1<<4, 1<<13, 1<<23),GroupInfo( 1<<4, 1<<14, 1<<23),GroupInfo( 1<<4, 1<<15, 1<<23),GroupInfo( 1<<4, 1<<16, 1<<24),GroupInfo( 1<<4, 1<<17, 1<<24),GroupInfo( 1<<4, 1<<18, 1<<24),
GroupInfo( 1<<5, 1<<10, 1<<22),GroupInfo( 1<<5, 1<<11, 1<<22),GroupInfo( 1<<5, 1<<12, 1<<22),GroupInfo( 1<<5, 1<<13, 1<<23),GroupInfo( 1<<5, 1<<14, 1<<23),GroupInfo( 1<<5, 1<<15, 1<<23),GroupInfo( 1<<5, 1<<16, 1<<24),GroupInfo( 1<<5, 1<<17, 1<<24),GroupInfo( 1<<5, 1<<18, 1<<24),
GroupInfo( 1<<6, 1<<10, 1<<22),GroupInfo( 1<<6, 1<<11, 1<<22),GroupInfo( 1<<6, 1<<12, 1<<22),GroupInfo( 1<<6, 1<<13, 1<<23),GroupInfo( 1<<6, 1<<14, 1<<23),GroupInfo( 1<<6, 1<<15, 1<<23),GroupInfo( 1<<6, 1<<16, 1<<24),GroupInfo( 1<<6, 1<<17, 1<<24),GroupInfo( 1<<6, 1<<18, 1<<24),
GroupInfo( 1<<7, 1<<10, 1<<25),GroupInfo( 1<<7, 1<<11, 1<<25),GroupInfo( 1<<7, 1<<12, 1<<25),GroupInfo( 1<<7, 1<<13, 1<<26),GroupInfo( 1<<7, 1<<14, 1<<26),GroupInfo( 1<<7, 1<<15, 1<<26),GroupInfo( 1<<7, 1<<16, 1<<27),GroupInfo( 1<<7, 1<<17, 1<<27),GroupInfo( 1<<7, 1<<18, 1<<27),
GroupInfo( 1<<8, 1<<10, 1<<25),GroupInfo( 1<<8, 1<<11, 1<<25),GroupInfo( 1<<8, 1<<12, 1<<25),GroupInfo( 1<<8, 1<<13, 1<<26),GroupInfo( 1<<8, 1<<14, 1<<26),GroupInfo( 1<<8, 1<<15, 1<<26),GroupInfo( 1<<8, 1<<16, 1<<27),GroupInfo( 1<<8, 1<<17, 1<<27),GroupInfo( 1<<8, 1<<18, 1<<27),
GroupInfo( 1<<9, 1<<10, 1<<25),GroupInfo( 1<<9, 1<<11, 1<<25),GroupInfo( 1<<9, 1<<12, 1<<25),GroupInfo( 1<<9, 1<<13, 1<<26),GroupInfo( 1<<9, 1<<14, 1<<26),GroupInfo( 1<<9, 1<<15, 1<<26),GroupInfo( 1<<9, 1<<16, 1<<27),GroupInfo( 1<<9, 1<<17, 1<<27),GroupInfo( 1<<9, 1<<18, 1<<27)
bool AI(std::vector<Item>& game)
for(size_t x= 0; x< game.size();++x){
if( 0!= game[x].data){//依次检查每个位置
vTemp.push_back( game[i].data);
vTemp.erase( std::remove(vTemp.begin(),vTemp.end(), 0), vTemp.end());
for(std::vector<int>::iterator Iter= vTemp.begin(); Iter!=vTemp.end();++ Iter)
std::replace(game[x].other.begin(), game[x].other.end(),(*Iter), 0);
game[x].other.erase( std::remove(game[x].other.begin(),game[x].other.end(), 0),game[x].other.end());
if(( 1== game[x].other.size())&&( 0!= game[x].other[0])){
game[x].data= game[x].other[0];
{return( item.other.size()==2)?true:false;}
if(( item.data==0)&&(item.other.size()==0))
bool AdvanceAI(std::vector<Item>& game)
std::vector<Item> Back= game;
std::vector<Item>::iterator iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
for(size_t i= 0; i<(*iItem).other.size();++i){
if( std::for_each( Back.begin(), Back.end(), testBackOpt()).bBack){//是否结束回滚
iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
if( std::count( Back.begin(), Back.end(), 0)){//判断是否结束
if( AdvanceAI( Back)){//没有结束，继续下一步递归
iItem= std::find_if( Back.begin(), Back.end(), OtherIs2Opt());
int main(int argc, char* argv[])
std::vector<Item> game(SIZE);
std::copy(Data,Data+SIZE, game.begin());
if( std::count( game.begin(), game.end(), 0)){
