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

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;i<cellptr;i++)
            {
            if (countcandidates[cellscandidates[unsolvedcells[i]]]<countcandidates[cellscandidates[unsolvedcells[cellptr]]])
                {
                j=unsolvedcells[i];
                unsolvedcells[i]=unsolvedcells[cellptr];
                unsolvedcells[cellptr]=j;
                }
            }
        //copy cellnumber with least available candidates to currentcell
        currentcell=unsolvedcells[cellptr];
        //seek for the first available candidate
        j=1;//prepare bitmask
        for(i=0;i<9;i++)//scan candidates
            {
            if ((cellscandidates[currentcell]&j)>0)//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;i<j;i++)//scan all unsolved cells
                {
                //check for empty cell
                if (cellscandidates[unsolvedcells[i]]==0)//if 0 then empty cell
                    {
                    //empty cell caused by last altered cell
                    cellptr++;//increase cellptr, so it will point to the last altered cell again
                    break;//stop searching for empty cells
                    }
                }
            }
        }
    else//currentcell is allready under examination, apparantly not the right solution
        {
        //check if the current value was the last available candidate
        if (lastcandidate[currentcell]==1)//check last candidate indicator
            {
            //no more candidates available for the current cell
            undo();//undo the last candidate update
            lastcandidate[currentcell]=0;//clear the last candidate indicator
            cellptr++;//increase cellptr (prepare for previous cell)
            }
        else//try next available candidate for the current cell
            {
            j=1;//prepare bitmask
            k=solution[currentcell];//get last used candidate
            undo();//undo the last candidate update
            for(i=0;i<k;i++) j=j*2;//update bitmask
            //seek for next available candidate
            for(i=k;i<9;i++)//scan next candidates
                {
                if ((cellscandidates[currentcell]&j)>0)//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;i<j;i++)//scan all unsolved cells
                    {
                    //check for empty cell
                    if (cellscandidates[unsolvedcells[i]]==0)//if 0 then empty cell
                        {
                        //empty cell caused by last altered cell
                        cellptr++;//increase cellptr, so it will point to the last altered cell again
                        break;//stop searching for empty cells
                        }
                    }
                }
            }
        }
    }
} 


void removecandidates(int currentcell)
{
int i;
int j;
int k;
int l;
int row;
int column;
int box;
//Each unsolved cell that shares the same row, column or box with the current cell
//will loose the value last placed in the current cell as candidate
//The current cell is saved, along with the positions of the cells losing the candidate,
//related to their row, column or box.
//If the brute force handler needs to backtrack, the undo() routine uses this information
//to restore those candidates
logsteps++;//increase stepcounter

logcell[logsteps]=currentcell;//save current cell, this is the last altered cell
logrow[logsteps]=0;//clear row log
logcolumn[logsteps]=0;//clear column log
logbox[logsteps]=0;//clear box log

row=currentcell/9;//calculate the row where the current cell belongs to
column=currentcell%9;//calculate the column where the current cell belongs to
box=cellsboxnumber[currentcell];//get the boxnumber for the current cell

j=1;//prepare candidate bitmask
if (solution[currentcell]>1)
    {
    for(i=1;i<solution[currentcell];i++) j=j*2;//update candidate bitmask
    }
for(i=0;i<cellptr;i++)//scan all unsolved cells
    {
    if ((cellscandidates[unsolvedcells[i]]&j)>0)//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;i<k;i++) j=j*2;//update candidate bitmask
    }
l=1;//prepare position bitmask
for(i=0;i<9;i++)//scan all positions
    {
    //if position is in row log then replace candidate
    if ((logrow[logsteps]&l)>0) 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;k<solution[i];k++) j=j*2;//update candidate bitmask
            }
        for (k=0;k<9;k++)//for all positions in row, column or box...
            {
            //remove candidate from cells in row
            cellscandidates[(row*9)+k]=cellscandidates[(row*9)+k]&(511^j);
            //remove candidate from cells in column
            cellscandidates[(k*9)+column]=cellscandidates[(k*9)+column]&(511^j);
            //remove candidate from cells in box
            cellscandidates[boxcellnumbers[box][k]]=cellscandidates[boxcellnumbers[box][k]]&(511^j);
            }
        }
    }


//solve naked singles first
while (nakedsingle()==1) solvedcells++;//update solved cells counter
	
if (solvedcells==81)//check if puzzle is solved
    {
    countsolutions=1;//set return value
    return (countsolutions);//return
    }

//collect unsolved cells
cellptr=-1;//reset unsolved cell pointer
for(i=0;i<81;i++)//scan sudoku[]
    {
    if (solution[i]==0)//for each unsolved cell...
        {
        //collect all unsolved cells
        //increase cellptr for each unsolved cell
        cellptr++;
        //transfer cellnumber for each unsolved cell to array unsolvedcells[]
        unsolvedcells[cellptr]=i;
        }
    }

boundary=cellptr+1;//set boundary
logsteps=-1;//reset log stepcounter
countsolutions=0;//clear solution counter

while (cellptr<boundary)//do brute force loop but don't let it backtrack beyond the first unsolved cell
    {
    if (cellptr==-1)//check cellptr, if -1 then a solution is found
        {
        //solution found, increase solution counter
        countsolutions++;
        //if this is the second solution then break the brute force loop
        if (countsolutions==2) break;
        //at this point only one solution is found, now reject
        //the last solved cell by increasing cellptr, so the search
        //can continue for other solutions, if any
        cellptr++;
        }
    //FROM HERE THE CODE IS THE SAME AS IN THE BRUTE FORCE LOOP FROM generatesolvedsudoku()
    currentcell=unsolvedcells[cellptr];
    if (solution[unsolvedcells[cellptr]]==0)
        {
        for(i=0;i<cellptr;i++)
            {
            if (countcandidates[cellscandidates[unsolvedcells[i]]]<countcandidates[cellscandidates[unsolvedcells[cellptr]]])
                {
                j=unsolvedcells[i];
                unsolvedcells[i]=unsolvedcells[cellptr];
                unsolvedcells[cellptr]=j;
                }
            }
        currentcell=unsolvedcells[cellptr];
        j=1;
        for(i=0;i<9;i++)
            {
            if ((cellscandidates[currentcell]&j)>0)
                {
                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;i<j;i++)
                {
                if (cellscandidates[unsolvedcells[i]]==0)
                    {
                    cellptr++;
                    break;
                    }
                }
            }
        }
    else
        {
        if (lastcandidate[currentcell]==1)
            {
            undo();
            lastcandidate[currentcell]=0;
            cellptr++;
            }
        else
            {
            j=1;
            k=solution[currentcell];
            undo();
            for(i=0;i<k;i++) j=j*2;
            for(i=k;i<9;i++)
                {
                if ((cellscandidates[currentcell]&j)>0)
                    {
                    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;i<j;i++)
                    {
                    if (cellscandidates[unsolvedcells[i]]==0)
                        {
                        cellptr++;
                        break;
                        }
                    }
                }
            }
        }
    }
//brute force loop ended, return countsolutions
return (countsolutions);
}


int nakedsingle(void)
{
int i;
int j;
int k;
int row;
int column;
int box;
int foundnaked;

foundnaked=0;//clear return value
for (i=0;i<81;i++)//scan all cells
    {
    //search for unsolved cell with only one possible candidate (naked single)
    if(countcandidates[cellscandidates[i]]==1)
        {
        foundnaked=1;//set return value
        row=i/9;//calculate row
        column=i%9;//calculate column
        box=cellsboxnumber[i];//get boxnumber
        j=1;//prepare bitmask
        for (k=0;k<9;k++)//scan candidate list
            {
            if ((cellscandidates[i]&j)>0)//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");
}