Microsoft Foundation Classes: creating a Sudoku game. Part 1.

Submitted by pavel7_7_7 on Sunday, February 9, 2014 - 08:37.
In this article you will read about the rules of the Sudoku game and the algorithm, used to solve the Sudoku puzzle. In the next two articles I'll describe the complete step by step guide about how to implement a Sudoku puzzle game using MFC. The goal of the Sudoku game is to fill the 9x9 grid with numbers from 1 to 9 in the next way:
  • Each row contains all numbers from 1 to 9
  • Each column contains all numbers from 1 to 9
  • Each block of 3x3 cells contains all numbers from 1 to 9
Here is an example of the solved Sudoku: Sudoku The first step is to create the class that will represent the Sudoku puzzle. The definition of this class in my project is:
  1. #include "stdlib.h"
  2. #pragma once
  3. class board
  4. {
  5. public:
  6.         int difficulty;//difficulty of the game
  7.         board(void);
  8.         ~board(void);
  9.         int **numbers;//array to store the current representation of the board
  10.         int **solution;//used to save the solution of the puzzle
  11.         int *tempSol;//temporary element
  12.         void generate();//generate the random puzzle
  13.         bool checkNumberValidity(int,int,int);
  14.         void help();//show help
  15.         void showSolution();//show solution
  16.         bool win();//check for winn
  17. private:       
  18.         void transpose();//operations
  19.         void swap_rows();//performed
  20.         void swap_columns();//to generate
  21.         void swap_rows_sector();//a new
  22.         void swap_columns_sector();//puzzle
  23.         void createProblem();
  24.         bool solve();
  25.         void placeNumber(int);
  26.         bool checkValidity(int,int,int);
  27. };
The constructor of the board is very simple. It just allocates memory for the arrays and calls generate() function to generate the problem:
  1. board::board(void)
  2. {
  3.         difficulty = 30;
  4.         numbers = new int*[9];
  5.         solution = new int*[9];
  6.         tempSol = new int [81];
  7.         for(int i = 0; i!=9;++i)
  8.         {
  9.                 numbers[i] = new int[9];
  10.                 solution[i] = new int[9];
  11.         }
  12.         generate();
  13. }
Before the description of the generate() function I would like to describe the algorithm used by me. To generate a random puzzle I start from the "base grid" - a correct grid of Sudoku puzzle: base The next list of operations can be performed on the base grid and the rule of the Sudoku will be kept:
  • transpose grid transpose
  • swap 2 rows
  • swap 2 columns
    • rowsandcol
  • swap 2 sectors of rows
  • swap 2 sectors columns
    • sectors
These transformations have next realization:
  1. void board::swap_rows()
  2. {
  3.  
  4.         srand(time(NULL));
  5.         int sector = rand() % 3;
  6.  
  7.         int row_number1 = rand() % 3;
  8.         int row_number2;
  9.         do
  10.                 row_number2 = rand() % 3;
  11.         while(row_number1 == row_number2);
  12.  
  13.         for(int i = 0; i != 9; ++i)
  14.         {
  15.                 int temp = numbers[sector*3 + row_number2][i];
  16.                 numbers[sector*3 + row_number2][i] = numbers[sector*3 + row_number1][i];
  17.                 numbers[sector*3 + row_number1][i] = temp;
  18.         }              
  19. }
  20. void board::swap_columns()
  21. {
  22.         transpose();
  23.         swap_rows();
  24.         transpose();
  25. }
  26. void board::transpose()
  27. {
  28.         int **temp;
  29.         temp = new int*[9];
  30.         for(int i = 0; i != 9; ++i)
  31.                 temp[i] = new int[9];
  32.         for(int i = 0; i != 9; ++i)
  33.                 for(int j = 0; j != 9; ++j)
  34.                         temp[i][j] = numbers[j][i];
  35.         for(int i = 0; i != 9; ++i)
  36.                 for(int j = 0; j!=9; ++j)
  37.                         numbers[i][j] = temp[i][j];
  38. }
  39. void board::swap_rows_sector()
  40. {
  41.         srand(time(NULL));
  42.         int sector1 = rand()%3;
  43.         int sector2;
  44.         do
  45.                 sector2 = rand() % 3;
  46.         while(sector1 == sector2);
  47.         for(int i = 0; i != 3; ++i)
  48.         {      
  49.                 for(int j = 0; j != 9; ++j)
  50.                 {
  51.                         int temp = numbers[sector2*3 + i][j];
  52.                         numbers[sector2*3 + i][j] = numbers[sector1*3 + i][j];
  53.                         numbers[sector1*3 + i][j] = temp;
  54.                 }
  55.         }
  56. }
  57. void board::swap_columns_sector()
  58. {
  59.         transpose();
  60.         swap_rows_sector();
  61.         transpose();
  62. }
As you can see the swapping of the columns and columns sectors are done using already defined functions:  transpose() and  swap_rows(), swap_rows_sector(); The generation of the puzzle is done by random number of these transformations:
  1. void board::generate()
  2. {
  3.         for(int i1 = 0,k = 0; i1 != 9; ++i1,k += 3){
  4.                 for(int i2 = 0; i2 != 9; ++i2,k++){
  5.                         numbers[i1][i2] = k%9 + 1;
  6.                 }
  7.                 if(i1==2)
  8.                         k++;
  9.                 if(i1 == 5)
  10.                         k++;
  11.         }
  12.        
  13.         srand(time(NULL));
  14.         for(int i = 0; i != 100; ++i)
  15.         {
  16.                 switch(rand()% 5)
  17.                 {
  18.                         case 0: transpose();
  19.                                         break;
  20.                         case 1: swap_rows();
  21.                                         break;
  22.                         case 2: swap_columns();
  23.                                         break;
  24.                         case 3: swap_rows_sector();
  25.                                         break;
  26.                         case 4: swap_columns_sector();
  27.                                         break;
  28.                 }
  29.         }
  30.        
  31.         for(int i = 0; i != 9; ++i)
  32.                 for(int j = 0; j != 9; ++j)
  33.                         solution[i][j] = numbers[i][j];
  34.  
  35.         for(int i = 0; i != 9; ++i){
  36.                 for(int j = 0; j != 9; ++j)
  37.                         tempSol[i*9+j] = numbers[i][j];
  38.         }
  39.         createProblem();
  40. }
In this function we create a random already solved puzzle and save it's representation. After this we need to create a problem for the user: we need to erase some numbers from cells. It's done by createProblem() function:
  1. void board::createProblem()
  2. {
  3.         for(int k = 0; k != difficulty;)
  4.         {
  5.                 int i;
  6.                 int j;
  7.                 do
  8.                 {
  9.                         i = rand() % 9;
  10.                         j = rand() % 9;
  11.                 }
  12.                 while(numbers[i][j] == 0);
  13.                 int save = numbers[i][j];
  14.                 numbers[i][j] = 0;
  15.                 tempSol[i*9+j] = 0;
  16.                 if(!solve())
  17.                 {
  18.                         numbers[i][j] = save;
  19.                         tempSol[i*9+j] = save;
  20.                 }
  21.                 else
  22.                         ++k;
  23.         }
  24. }
In this method numbers from the grid are randomly eliminated. After the cell is eliminated, the program checks if the problem can be resolved in a single way. If it can be resolved - number is deleted from cell. The check of the valid elimination is performed by the next functions:
  1. bool board::solve()
  2. {
  3.         try {
  4.             placeNumber(0);
  5.             return false;
  6.         } catch (char* ex) {
  7.             return true;
  8.         }
  9. }
  10. void board::placeNumber(int position)
  11. {
  12.         if(position==81)
  13.                 throw (char*) "Finished!";
  14.         if(tempSol[position])
  15.         {
  16.                 placeNumber(position+1);
  17.                         return;
  18.         }
  19.         for(int n = 1; n!=10; ++n)
  20.         {
  21.                 if(checkValidity(n,position%9, position / 9))
  22.                 {
  23.                         tempSol[position] = n;
  24.                         placeNumber(position+1);
  25.                         tempSol[position] = 0;
  26.                 }
  27.         }
  28. }
  29. bool board::checkValidity(int value, int x, int y)
  30. {
  31.         for(int i = 0; i != 9; ++i)
  32.         {
  33.                 if(tempSol[y*9 + i] == value || tempSol[i*9 + x] == value)
  34.                         return false;
  35.         }
  36.         int startX = (x / 3) * 3;
  37.     int startY = (y / 3) * 3;
  38.                 for (int i = startY; i < startY + 3; i++) {
  39.             for (int j = startX; j < startX + 3; j++) {
  40.                 if (tempSol[i * 9 + j] == value)
  41.                     return false;
  42.             }
  43.         }
  44.         return true;
  45. }
  46. bool board::checkNumberValidity(int value, int x, int y)
  47. {
  48.         for(int i = 0; i != 9; ++i)
  49.         {
  50.                 if(numbers[x][i] == value || numbers[i][y] == value)
  51.                         return false;
  52.         }
  53.         int startX = (x / 3) * 3;
  54.     int startY = (y / 3) * 3;
  55.                 for (int i = startY; i < startY + 3; i++) {
  56.             for (int j = startX; j < startX + 3; j++) {
  57.                 if (numbers[j][i] == value)
  58.                     return false;
  59.             }
  60.         }
  61.         return true;
  62. }
These functions use the depth search algorithm with backtracking to find if any solution for the current state can be found. As the result of generate() function we have next things:
  • A grid that represents the solution of the Sudoku puzzle
  • A grid a copy of the solution but without some numbers in cells
So, we have the full implementation of the Sudoku logic. In the next article I'll tell you how to create the interface of the Sudoku game.
Tags
C++
Sudoku
MFC

Add new comment

About text formats
  • 242 views