Sudoku : Visual C++

   Sudoku is a logic-based, number-placement puzzle. The objective is to fill a 9x9 grid with digits so that each column, each row, and each of the nine 3x3 subgrids that compose the grid ( also called "boxes", or "regions") contains all of the digits from 1 to 9. 

At the beginning of the game, the 9x9 grid will have some of the squares filled in. Your job is to use logic to fill in the missing digits and complete the grid. This game is designed and programmed in Visual Studio Express 2013 IDE in C++ (CLR) language.

The following screenshots of the program describe its functionality:-

Backtracking algorithm to solve Sudoku

Backtracking is a systematic method to iterate through all the possible configurations of a search space. 

The backtracking algorithm fills up a blank cell of Sudoku with a valid number (i.e. non-duplication across rows, columns, and boxes), moves on to the next cell, and then does the same thing. If all the possible numbers from 1 to 9 are invalid for any cell that the algorithm is currently “at”, the algorithm moves back to the previous cell and changes that cell’s value to another valid number. Afterwards, it moves back to the next cell and the whole process repeats.

Algorithm to solve Sudoku

  Find row, col of an unassigned cell
  If there is none, return true
  For digits from 1 to 9
    a) If there is no conflict for digit at row,col
    assign digit to row,col and recursively try fill in rest of grid
    b) If recursion successful, return true
    c) Else, remove digit and try another
  If all digits have been tried and nothing worked, return false

// UNASSIGNED is used for empty cells in sudoku grid
#define UNASSIGNED 0

// N is used for size of Sudoku grid. Size will be NxN
#define N 9

// Levels
#define EASY 1
#define MEDIUM 2
#define HARD 3

•  bool FindUnassignedLocation(int sudoku[N][N], int &row, int &col) 

/* Searches the grid to find an entry that is still unassigned. If found, the reference parameters row, col will be set the location that is unassigned, and true is returned. If no unassigned entries remain, false is returned. */

bool FindUnassignedLocation(int sudoku[N][N], int &row, int &col)
{
    for (row = 0; row < N; row++)
    for (col = 0; col < N; col++)
    if (sudoku[row][col] == UNASSIGNED)
        return true;
    return false;
}

• bool UsedInRow(int sudoku[N][N], int row, int num)

/* Returns a boolean which indicates whether any assigned entry in the specified row matches the given number. */

bool UsedInRow(int sudoku[N][N], int row, int num)
{
    for (int col = 0; col < N; col++)
    if (sudoku[row][col] == num)
        return true;
    return false;
}

• bool UsedInCol(int sudoku[N][N], int col, int num)

/* Returns a boolean which indicates whether any assigned entry in the specified column matches the given number. */

bool UsedInCol(int sudoku[N][N], int col, int num)

{

    for (int row = 0; row < N; row++)

    if (sudoku[row][col] == num)

        return true;

    return false;

}

• bool UsedInBox(int sudoku[N][N], int boxStartRow, int boxStartCol, int num)

/* Returns a boolean which indicates whether any assigned entry within the specified 3x3 box matches the given number. */

bool UsedInBox(int sudoku[N][N], int boxStartRow, int boxStartCol, int num)
{
    for (int row = 0; row < 3; row++)
    for (int col = 0; col < 3; col++)
    if (sudoku[row + boxStartRow][col + boxStartCol] == num)
        return true;
    return false;
}

• bool isSafe(int sudoku[N][N], int row, int col, int num)

/* Returns a boolean which indicates whether it will be legal to assign num to the given row,col location. */

bool isSafe(int sudoku[N][N], int row, int col, int num)
{
    /* Check if 'num' is not already placed in current row, current column and current 3x3 box */
    return !UsedInRow(sudoku, row, num) &&
        !UsedInCol(sudoku, col, num) &&
        !UsedInBox(sudoku, row - row % 3, col - col % 3, num);
}

• bool SolveSudoku(int sudoku[N][N])

/* Takes a partially filled-in grid and attempts to assign values to all unassigned locations in such a way to meet the requirements for Sudoku solution (non-duplication across rows, columns, and boxes) */

bool SolveSudoku(int sudoku[N][N])
{
    int row, col;

    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(sudoku, row, col))
        return true; // success!

    // consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        // if looks promising
        if (isSafe(sudoku, row, col, num))
        {
            // make tentative assignment
            sudoku[row][col] = num;

            // return, if success
            if (SolveSudoku(sudoku))
                return true;

            // failure, unmake & try again
            sudoku[row][col] = UNASSIGNED;
        }
    }
    return false;
}


Algorithm to generate Sudoku

Step 1: Randomly take any number 1-9 and place it in any cell.
Step 2: Solve the Sudoku.
Step 3: Remove k no. of elements randomly to complete game.

• bool initSudoku(int sudoku[N][N])

/*Fills all cells of Sudoku with 0(denotes empty cells) */

bool initSudoku(int sudoku[N][N])
{
    for (int row = 0; row < N; row++)
    for (int col = 0; col < N; col++)
        sudoku[row][col] == UNASSIGNED;
}

• bool isGenerated(int sudoku[N][N])

/* Checks that the Sudoku is partially filled or not. */

bool isGenerated(int sudoku[N][N])
{
    for (int row = 0; row < N; row++)
    for (int col = 0; col < N; col++)
    {
        if (sudoku[row][col] == UNASSIGNED)
            return true;
    }
    return false;
}

• void generateSudoku(int sudoku[N][N], int level)

/* Generates partially filled Sudoku */

void generateSudoku(int sudoku[N][N], int level)

{

    System::Random^ rnd = gcnew System::Random();

    initSudoku(sudoku);

    sudoku[0][0] = rnd->Next(1, 9);

    sudoku[4][4] = rnd->Next(1, 9);

    sudoku[8][8] = rnd->Next(1, 9);

    SolveSudoku(sudoku);

    for (int row = 0; row < N; row++)

    for (int col = 0; col < N; col++)

    {

        if (levelType == EASY)

        {

            if (rnd->Next(0,4) == 0)

                sudoku[row][col] = UNASSIGNED;

        }

        else if (levelType == MEDIUM)

        {

            if (rnd->Next(0, 3) == 0)

                sudoku[row][col] = UNASSIGNED;

        }

        else

        {

            if (rnd->Next(0, 2) == 0)

                sudoku[row][col] = UNASSIGNED;

        }

    }

    if (!isGenerated(sudoku))

        generateSudoku(sudoku,levelType);  

}




The following video displays this program in action :

                                                                                                




Downloads

Click here to view and download the source code of Sudoku (180 KB).

Click here to download the executable file of Sudoku (87 KB).