fork download
copy 
  1. /*    A C++ program designed to solve sudoku puzzles. The program finds blank spaces
  2.  *    on the 9x9 grid and tests for the first value from 1 to 9 that can be placed
  3.  *    in the square. There must be the number 1 through 9 in every row, column,
  4.  *    and 3x3 box. If the program later finds a problem trying to place values in
  5.  *    blank boxes, it goes back and unassigns values to the recently assigned 
  6.  *    boxes. This program was written for the CS 173 Spring 2014 honors project 
  7.  *    by Erin Emrath.  */
  8. #include <stdio.h>
  9.  
  10. // UNASSIGNED is used for blank spaces in the sudoku grid
  11. #define UNASSIGNED 0
  12.  
  13. bool FindEmptySpace(int grid[9][9], int &row, int &col);
  14.  
  15. bool isLegal(int grid[9][9], int row, int col, int num);
  16.  
  17. bool SolveSudoku(int grid[9][9])
  18. {
  19.     int row, col;
  20.  
  21.     // If there are no empty spaces, the puzzle is solved.
  22.     if (!FindEmptySpace(grid, row, col))
  23.        return true; 
  24.  
  25.     // try integers 1 through 9
  26.     for (int num = 1; num <= 9; num++)
  27.     {
  28.         // checks that the number isn't in the corresponding row, column, or box.
  29.         if (isLegal(grid, row, col, num))
  30.         {
  31.             // make preliminary guess
  32.             grid[row][col] = num;
  33.  
  34.             // The grid is solved
  35.             if (SolveSudoku(grid))
  36.                 return true;
  37.  
  38.             // failure, unassign previous value and try a different number
  39.             grid[row][col] = UNASSIGNED;
  40.         }
  41.     }
  42.     return false; // the program goes back to try a higher value than before
  43. }
  44.  
  45. /* Searches the grid to find a space that is still empty. If
  46.    one is found, the variables row and col will be set to the 
  47.    empty space and then true is returned. If there are no empty
  48.    spaces left, false is returned. */
  49. bool FindEmptySpace(int grid[9][9], int &row, int &col)
  50. {
  51.     for (row = 0; row < 9; row++)
  52.         for (col = 0; col < 9; col++)
  53.             if (grid[row][col] == UNASSIGNED)
  54.                 return true;
  55.     return false;
  56. }
  57.  
  58. /* Returns a boolean indicating whether any assigned value
  59.    in the specified row matches the given number. Similar 
  60.    for the following column and box methods. */
  61. bool InSameRow(int grid[9][9], int row, int num)
  62. {
  63.     for (int col = 0; col < 9; col++)
  64.         if (grid[row][col] == num)
  65.             return true;
  66.     return false;
  67. }
  68.  
  69. bool InSameCol(int grid[9][9], int col, int num)
  70. {
  71.     for (int row = 0; row < 9; row++)
  72.         if (grid[row][col] == num)
  73.             return true;
  74.     return false;
  75. }
  76.  
  77. bool InSameBox(int grid[9][9], int boxStartRow, int boxStartCol, int num)
  78. {
  79.     for (int row = 0; row < 3; row++)
  80.         for (int col = 0; col < 3; col++)
  81.             if (grid[row+boxStartRow][col+boxStartCol] == num)
  82.                 return true;
  83.     return false;
  84. }
  85.  
  86. /* Returns a boolean indicating whether it will be legal to fill 
  87.    the given row, col, and box location with num. */
  88. bool isLegal(int grid[9][9], int row, int col, int num)
  89. {
  90.     return !InSameRow(grid, row, num) &&
  91.            !InSameCol(grid, col, num) &&
  92.            !InSameBox(grid, row - row%3 , col - col%3, num);
  93. }
  94.  
  95. /* print solved grid  */
  96. void printGrid(int grid[9][9])
  97. {
  98.     for (int row = 0; row < 9; row++)
  99.     {
  100.        for (int col = 0; col < 9; col++)
  101.              printf("%2d", grid[row][col]);
  102.         printf("\n");
  103.     }
  104. }
  105.  
  106. /* main program, implementation */
  107. int main()
  108. {
  109.     // 0 means empty spaces
  110.     int grid[9][9] = {{1,0,9,0,0,0,0,0,0},
  111. 		      {0,0,5,0,0,0,1,2,0},
  112. 		      {6,0,0,0,0,4,0,0,0},
  113. 		      {0,1,0,0,0,9,0,0,0},
  114. 		      {0,0,0,0,3,7,0,0,0},
  115. 		      {7,0,0,0,0,1,2,0,0},
  116. 		      {0,0,0,0,0,0,3,0,8},
  117. 		      {0,0,0,3,0,0,9,0,0},
  118. 		      {0,0,8,0,0,0,0,6,0}};
  119.  
  120.     if (SolveSudoku(grid) == true)
  121.           printGrid(grid);
  122.     else
  123.          printf("Puzzle has no solution");
  124.  
  125.     return 0;
  126. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 1 2 9 5 6 3 4 8 7
 3 4 5 7 9 8 1 2 6
 6 8 7 1 2 4 5 3 9
 2 1 3 6 4 9 8 7 5
 8 5 4 2 3 7 6 9 1
 7 9 6 8 5 1 2 4 3
 4 6 1 9 7 2 3 5 8
 5 7 2 3 8 6 9 1 4
 9 3 8 4 1 5 7 6 2
https://ideone.com/SdrbLM
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!