#include #include #include #include void initiate(); void generatesolvedsudoku(); void concealcells(); int checkuniqueness(); void removecandidates(int); void undo(); void screenoutput(); int nakedsingle(); int unsolvedcells[81]; int cellptr; int solution[81]; int sudoku[81]; int cellscandidates[81]; int countcandidates[512]; int cellsboxnumber[81]; int boxcellnumbers[9][9]; int lastcandidate[81]; int logsteps; int logcell[81]; int logrow[81]; int logcolumn[81]; int logbox[81]; void main(void) { printf("Random Sudoku Generator V1.0\n\n");//title srand((unsigned)time(NULL)); //seed randomizer initiate(); //initiate arrays and base data generatesolvedsudoku(); //generate random solution concealcells(); //conceal to regular sudoku screenoutput();//set result on screen printf("Press any key...\n");//ask for key getch();//wait for key } void initiate(void) { int i; int j; int k; int l; int cell; int box; //possible candidates for each cell are stored bitwise in array //cellscandidates[].If candidate 1 is present then bit 0 is set, //if candidate 2 is present then bit 1 is set, and so on... //The array countcandidates[] will return the number of candidates //if feeded with any cell's cellscandidates[] //Here, the array countcandidates[] is initiated. for(i=0;i<512;i++) { j=i; countcandidates[i]=0; while (j>0) { if (j%2>0) countcandidates[i]++; j=(j-(j%2))/2; } } //Boxes are adressed 0 to 8 from top left to bottom right //The array cellsboxnumber[] will return the boxnumber for //any cell, it acts as some kind of boxmap. //The array boxcellnumbers[][] holds the 9 cellnumbers //for each box. Here we initiate both arrays for(i=0;i<3;i++) { for(j=0;j<3;j++) { for(k=0;k<3;k++) { for(l=0;l<3;l++) { cell=(j*27)+(i*3)+(l*9)+k; box=(j*3)+i; cellsboxnumber[cell]=box; boxcellnumbers[box][(l*3)+k]=cell; } } } } } void generatesolvedsudoku(void) { int i; int j; int k; int l; int currentcell; //prepare base data for empty grid for(i=0;i<81;i++) { unsolvedcells[i]=i;//collect all cellnumbers as unsolved cells cellscandidates[i]=511;//set all candidates as available for all cells solution[i]=0;//clear solution for all cells lastcandidate[i]=0;//clear last candidate indicator } //mix up the order of the cells kept in unsolvedcells[] for(i=0;i<500;i++)//500 times will be enough { j=(rand()%81);//generate a random number between 0 and 80 k=(rand()%81);//generate another between 0 and 80 //swap cell adresses kept in unsolvedcells[] pointed by i and j l=unsolvedcells[j]; unsolvedcells[j]=unsolvedcells[k]; unsolvedcells[k]=l; } cellptr=80;//initiate unsolved cells pointer logsteps=-1;//initiate candidate update counter //start brute force loop until grid is filled while (cellptr>-1)//if cellptr=-1 then the grid is filled { currentcell=unsolvedcells[cellptr];//get current cell from array unsolvedcells //check if the unsolved cell pointed by cellptr is allready under examination if (solution[currentcell]==0)//if 0 then the cell is not allready under examination { //seek through all unsolved cells for the one with the least available candidates //kinda bubble sort for(i=0;i0)//test with bitmask { //available candidate found solution[currentcell]=i+1;//set as tempararely solution break;//stop searching } j=j*2;//update bitmask } //check if there is only one candidate, and if so set lastcandidate indicator if (countcandidates[cellscandidates[currentcell]]==1) lastcandidate[currentcell]=1; removecandidates(currentcell);//update candidates in unsolved cells sharing row, column or box of currentcell j=cellptr;//copy current value of cellptr to j cellptr--;//decrease cellptr (prepare for next unsolved cell) //if there are still cells unsolved check if there are empty cells among them if (cellptr>-1) { for(i=0;i0)//test with bitmask { //next available candidate found solution[currentcell]=i+1;//set as temperarely solution break;//stop searching } j=j*2;//update bitmask } lastcandidate[currentcell]=1;//by default, set last candidate indicator //if current used candidate is not 9 then maybe it's not the last candidate used if (solution[currentcell]<9)//check if there are more available candidates { for(i=solution[currentcell];i<9;i++)//scan other candidates { j=j*2;//update bitmask if ((cellscandidates[currentcell]&j)>0)//test with bitmask { //more candidates available lastcandidate[currentcell]=0;//clear last candidate indicator break;//stop searching } } } removecandidates(currentcell);//update candidates in unsolved cells sharing row, column or box of currentcell j=cellptr;//copy current value of cellptr to j cellptr--;//decrease cellptr (prepare for next unsolved cell) //if there are still cells unsolved check if there are empty cells among them if (cellptr>-1) { for(i=0;i1) { for(i=1;i0)//test if candidate is present { if (unsolvedcells[i]/9==row)//check if it shares row with current cell { l=1;//prepare position bitmask for(k=0;k<9;k++)//search position in row { if ((row*9)+k==unsolvedcells[i])//if position found... { logrow[logsteps]=logrow[logsteps]|l;//set position bit in row log cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list break;//stop position search } l=l*2;//update position bitmask } } else if (unsolvedcells[i]%9==column)//check if it shares column with current cell { l=1;//prepare position bitmask for(k=0;k<9;k++)//search position in column { if ((k*9)+column==unsolvedcells[i])//if position found... { logcolumn[logsteps]=logcolumn[logsteps]|l;//set position bit in column log cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list break;//stop position search } l=l*2;//update position bitmask } } else if (cellsboxnumber[unsolvedcells[i]]==box)//check if it shares box with current cell { l=1;//prepare position bitmask for(k=0;k<9;k++)//search position in box { if (boxcellnumbers[box][k]==unsolvedcells[i])//if position found... { logbox[logsteps]=logbox[logsteps]|l;//set position bit in box log cellscandidates[unsolvedcells[i]]=cellscandidates[unsolvedcells[i]]&(511^j);//remove candidate from list break;//stop position search } l=l*2;//update position bitmask } } } } } void undo(void) { int i; int j; int k; int l; int row; int column; int box; //This routine uses the information stored by removecandidates[] to replace //the last removed candidates from the unsolved cells whenever the brute force //handler needs to backtrack k=solution[logcell[logsteps]];//get the candidate value solution[logcell[logsteps]]=0;//clear the solution row=logcell[logsteps]/9;//calculate row column=logcell[logsteps]%9;//calculate column box=cellsboxnumber[logcell[logsteps]];//get boxnumber j=1;//prepare candidate bitmask if (k>1) { for(i=1;i0) cellscandidates[(row*9)+i]=cellscandidates[(row*9)+i]|j; //if position is in column log then replace candidate if ((logcolumn[logsteps]&l)>0) cellscandidates[(i*9)+column]=cellscandidates[(i*9)+column]|j; //if position is in box log then replace candidate if ((logbox[logsteps]&l)>0) cellscandidates[boxcellnumbers[box][i]]=cellscandidates[boxcellnumbers[box][i]]|j; l=l*2;//update position bitmask } logsteps--;//decrease logcounter (for next backtrack, if needed) } void concealcells(void) { int i; int j; int k; int l; int solutionbackup[81]; int countconcealedcells; int currentcell; int mixedorder[41]; //This routine will remove values from the random ordered cell list, and checks //for uniqueness. To gain an 180° rotational sudoku cells are removed in pairs. //therefore only the first half of the cells are adressed directly. The 180° rotational //opposite cell is calculated: opposite cell = 80 - cell for(i=0;i<81;i++) { //make a backup of the solution, since the array solution is //used by the routine that checks the uniqueness solutionbackup[i]=solution[i]; //copy the solution to handle the cells to conceal sudoku[i]=solution[i]; //prepare an array to mix up the order of the first half of the cells if (i<41) mixedorder[i]=i;//setup first half of cells } for(i=0;i<250;i++)//mix up the order of the cellnumbers kept in array mixedorder[] { j=(rand()%41); k=(rand()%41); l=mixedorder[j]; mixedorder[j]=mixedorder[k]; mixedorder[k]=l; } countconcealedcells=0;//clear concealed cell counter for(i=0;i<41;i++)//scan half of the cells { //stop concealing if 58 cells are concealed succesful if (countconcealedcells==58) break; //get next cell currentcell=mixedorder[i]; //conceal that cell (remove the value) sudoku[currentcell]=0; //conceal the 180° rotational cell sudoku[80-currentcell]=0; //check uniqueness if (checkuniqueness()==1)//if return value is 1, then there was one unique solution { //increase twice the concealed cell counter countconcealedcells++; countconcealedcells++; } else//if return value is not 1, then there was more than one solution { //restore the last concealed cells sudoku[currentcell]=solutionbackup[currentcell]; sudoku[80-currentcell]=solutionbackup[80-currentcell]; } } //all possible cells to conceal with a maximum of 58 are concealed, //and the sudoku to solve is in array sudoku[] //now restore the solution for(i=0;i<81;i++) solution[i]=solutionbackup[i]; } int checkuniqueness(void) { int i; int j; int k; int solvedcells; int row; int column; int box; int currentcell; int countsolutions; int boundary; //This routine will brute force solve the puzzle contained in sudoku[] //Since sudoku[] is based upon a solved grid, at least one solution will be found //When found the first and hopefully the only solution, the last solved cell //will be rejected so the search will continue. If another solution is found //the routine will be halted and countsolutions will be 2, indicating that there //are at least 2 solutions, and the brute force loop will be stopped. //If there is only one solution, this brute force will //eventually backtrack beyond the first solved cell, can't have that! //Therefore, a boundary is set to prevent this, and ends the brute force loop. //At last, the value from countsolutions is returned (1=1 solution, 2=at least 2 solutions) //initiation for(i=0;i<81;i++) { //transfer the sudoku puzzle to solution[] solution[i]=sudoku[i]; //set all candidates available for all cells cellscandidates[i]=511; //clear last candidate indicator for all cells lastcandidate[i]=0; } solvedcells=0;//setup solved cells counter //update cellscandidates[] for(i=0;i<81;i++)//scan sudoku[] { if (solution[i]>0)//for each solved cell... { solvedcells++;//update solved cells counter //update cells candidates //remove candidates for each solved cell cellscandidates[i]=0; row=i/9;//calculate row from solved cell column=i%9;//calculate column from solved cell box=cellsboxnumber[i];//get boxnumber from solved cell j=1;//prepare candidate bitmask if (solution[i]>1) { for (k=1;k0) { solution[currentcell]=i+1; break; } j=j*2; } if (countcandidates[cellscandidates[currentcell]]==1) lastcandidate[currentcell]=1; removecandidates(currentcell); j=cellptr; cellptr--; if (cellptr>-1) { for(i=0;i0) { solution[currentcell]=i+1; break; } j=j*2; } lastcandidate[currentcell]=1; if (solution[currentcell]<9) { for(i=solution[currentcell];i<9;i++) { j=j*2; if ((cellscandidates[currentcell]&j)>0) { lastcandidate[currentcell]=0; break; } } } removecandidates(currentcell); j=cellptr; cellptr--; if (cellptr>-1) { for(i=0;i0)//test bit for available candidate { //if found... solution[i]=k+1;//assign to solution break;//stop scanning candidate list } j=j*2;//update bitmask } cellscandidates[i]=0;//clear candidate list from naked single cell for (k=0;k<9;k++)//for each position in same row, column or box { //update cellscandidates for each cell in same row cellscandidates[(row*9)+k]=cellscandidates[(row*9)+k]&(511^j); //update cellscandidates for each cell in same column cellscandidates[(k*9)+column]=cellscandidates[(k*9)+column]&(511^j); //update cellscandidates for each cell in same box cellscandidates[boxcellnumbers[box][k]]=cellscandidates[boxcellnumbers[box][k]]&(511^j); } break; } } return(foundnaked); } void screenoutput(void) { int i; int j; int k; int l; printf("Sudoku Solution\n"); printf("----------- -----------\n"); for(i=0;i<3;i++) { for(j=0;j<3;j++) { for(k=0;k<3;k++) { for(l=0;l<3;l++) { printf("%u",sudoku[(i*27)+(j*9)+(k*3)+l]); } printf(" "); } printf(" "); for(k=0;k<3;k++) { for(l=0;l<3;l++) { printf("%u",solution[(i*27)+(j*9)+(k*3)+l]); } printf(" "); } printf("\n"); } printf("\n"); } printf("\n\n"); }