fork(1) download
copy 
  1.  
  2. #include <set>
  3. #include <string>
  4.  
  5. #include <fstream>
  6. #include <iostream>
  7. #include <cassert>
  8.  
  9. // ======================================================================================
  10.  
  11. enum SolutionResult {
  12.  
  13.     // The position has been solved OK.
  14.     SR_SOLVED,
  15.  
  16.     // The current position in invalid.
  17.     // For that reason, it is useless to even attempt to solve it.
  18.     SR_INVALID,
  19.  
  20.     // The current position is valid in its current state, but there 
  21.     // exists no complete solution that would uphold the sudoku rules.
  22.     SR_UNSOLVABLE
  23.  
  24. };
  25.  
  26. // ======================================================================================
  27.  
  28. class Sudoku {
  29.  
  30. protected:
  31.  
  32.     // 0 = Empty cell
  33.     short values[9][9];
  34.  
  35.     // Returns whether all the rows are currently valid, 
  36.     // i.e. whether no rows contain any duplicate values.
  37.     bool checkValidRows() {
  38.  
  39.         for (short row = 0; row < 9; row++) {
  40.  
  41.             std::set<short> valuesInRow;
  42.             for (short col = 0; col < 9; col++) {
  43.  
  44.                 short val = this->values[row][col];
  45.                 if (!val) continue;
  46.  
  47.                 if (valuesInRow.find(val) != valuesInRow.end()) {
  48.                     return false;
  49.                 }
  50.  
  51.                 valuesInRow.insert(val);
  52.  
  53.             }
  54.  
  55.         }
  56.  
  57.         return true;
  58.  
  59.     }
  60.  
  61.     // Returns whether all the columns are currently valid, 
  62.     // i.e. whether no columns contain any duplicate values.
  63.     bool checkValidCols() {
  64.  
  65.         for (short col = 0; col < 9; col++) {
  66.  
  67.             std::set<short> valuesInCol;
  68.             for (short row = 0; row < 9; row++) {
  69.  
  70.                 short val = this->values[row][col];
  71.                 if (!val) continue;
  72.  
  73.                 if (valuesInCol.find(val) != valuesInCol.end()) {
  74.                     return false;
  75.                 }
  76.  
  77.                 valuesInCol.insert(val);
  78.  
  79.             }
  80.  
  81.         }
  82.  
  83.         return true;
  84.  
  85.     }
  86.  
  87.     // Returns whether all the partial squares are currently valid, 
  88.     // i.e. whether no 3x3 square contains a duplicate value.
  89.     bool checkValidSquares() {
  90.  
  91.         for (short squareX = 0; squareX < 3; squareX++) {
  92.         for (short squareY = 0; squareY < 3; squareY++) {
  93.  
  94.             std::set<short> valuesInSquare;
  95.             for (short m = 0; m < 3; m++) {
  96.                 for (short n = 0; n < 3; n++) {
  97.  
  98.                     short val = this->values[squareX*3+m][squareY*3+n];
  99.                     if (val == 0) continue;
  100.                     if (valuesInSquare.find(val) != valuesInSquare.end()) {
  101.                         return false;
  102.                     }
  103.                     valuesInSquare.insert(val);
  104.  
  105.                 }
  106.             }
  107.  
  108.         }
  109.         }
  110.  
  111.         return true;
  112.  
  113.     }
  114.  
  115.     // Returns whether the current position is valid, i.e., whether its rows, columns, 
  116.     // and squares are all valid and do not contain a duplicate value.
  117.     bool checkValid() {
  118.  
  119.         return this->checkValidRows() && this->checkValidCols() && this->checkValidSquares();
  120.  
  121.     }
  122.  
  123. public:
  124.  
  125.     Sudoku() {
  126.  
  127.         // Start with a blank position.
  128.         for (short row = 0; row < 9; row++) {
  129.         for (short col = 0; col < 9; col++) {
  130.  
  131.             this->values[row][col] = 0;
  132.  
  133.         }
  134.         }
  135.  
  136.     }
  137.  
  138.     Sudoku (const short values[9][9]) {
  139.  
  140.         for (short row = 0; row < 9; row++) {
  141.         for (short col = 0; col < 9; col++) {
  142.  
  143.             // Values that are not between [0 .. 9] 
  144.             // are discarded and replaced with zeroes.
  145.             short val = values[row][col];
  146.             if (val >= 0 && val <= 9) {
  147.                 this->values[row][col] = val;
  148.             } 
  149.             else {
  150.                 this->values[row][col] = 0;
  151.             }
  152.  
  153.         }
  154.         }
  155.  
  156.     }
  157.  
  158.     // This is the solver method.
  159.     // The way to solution is a standard backtrack exercise.
  160.     // 
  161.     // For the next empty space, we put the lowest possible value in, and recursively call the solver
  162.     // to see whether it can complete all the other spaces in a valid manner – in which case, we are done.
  163.     // In case that no possible value in the chosen space leads to a valid and complete solution, we clear 
  164.     // the space entirely and declare the position as unsolvable. In recursion terms, this means that 
  165.     // we need to attempt to put another value to the previous space, and so on.
  166.  
  167.     SolutionResult solve() {
  168.  
  169.         // Check that the situation is valid.
  170.         if (!this->checkValid()) return SR_INVALID;
  171.  
  172.         // For the next empty space:
  173.         for (short row = 0; row < 9; row++) {
  174.         for (short col = 0; col < 9; col++) {
  175.  
  176.             if (this->values[row][col] > 0) continue;
  177.  
  178.             // Put an arbitrary value into the space:
  179.             for (short val = 1; val <= 9; val++) {
  180.  
  181.                 this->values[row][col] = val;
  182.  
  183.                 // Recursively call the solver and see whether it can complete all 
  184.                 // the other spaces in the same manner. In case that it can, we're done.
  185.                 if (this->solve() == SR_SOLVED) {
  186.                     return SR_SOLVED;
  187.                 }
  188.  
  189.             }
  190.  
  191.             // We tried all the possible values, and none has lead to a complete and 
  192.             // valid solution. Clear the space, and return that the position is unsolvable.
  193.             this->values[row][col] = 0;
  194.             return SR_UNSOLVABLE;
  195.  
  196.         }
  197.         }
  198.  
  199.         // There are no more empty spaces. 
  200.         // We're done.
  201.         return SR_SOLVED;
  202.  
  203.     }
  204.  
  205.     // Formatted output.
  206.     friend std::ostream& operator<< (std::ostream &os, const Sudoku& s) {
  207.  
  208.         for (short row = 0; row < 9; row++) {
  209.  
  210.             os << std::endl;
  211.             for (short col = 0; col < 9; col++) {
  212.  
  213.                 os << ' ';
  214.                 if (s.values[row][col] > 0) {
  215.                     os << s.values[row][col];
  216.                 } else {
  217.                     os << '.';
  218.                 }
  219.  
  220.                 if (col == 2 || col == 5) {
  221.                     os << " |";
  222.                 }
  223.  
  224.             }
  225.  
  226.             if (row == 2 || row == 5) {
  227.                 os << std::endl << " ------+-------+------";
  228.             }
  229.  
  230.         }
  231.  
  232.         os << std::endl;
  233.         return os;
  234.  
  235.     }
  236.  
  237.     //
  238.     static void runUnitTests();
  239.  
  240. };
  241.  
  242. // ======================================================================================
  243.  
  244. int main (int argc, char* argv[])
  245. {
  246.     short pos[9][9] = {
  247.         {0, 0, 4, 0, 0, 0, 0, 0, 0},
  248.         {6, 0, 2, 1, 0, 0, 0, 0, 0},
  249.         {1, 0, 8, 3, 4, 2, 5, 6, 7},
  250.         {0, 0, 9, 7, 0, 0, 4, 2, 3},
  251.         {4, 0, 6, 8, 0, 0, 0, 0, 1},
  252.         {7, 1, 3, 9, 2, 0, 8, 0, 0},
  253.         {0, 0, 0, 5, 3, 0, 2, 8, 4},
  254.         {0, 0, 0, 4, 1, 0, 6, 0, 0},
  255.         {3, 0, 0, 0, 0, 6, 1, 0, 0}
  256.     };
  257.  
  258.     // Let's test the entire unit.
  259.     Sudoku::runUnitTests();
  260.  
  261.     // Let's solve the particular position above:
  262.  
  263.     Sudoku s (pos);
  264.     std::cout << s << std::endl;
  265.     std::cout << "Solver starts, please wait..." << std::endl;
  266.  
  267.     switch (s.solve()) {
  268.  
  269.     case SR_SOLVED:
  270.         std::cout << "Solution: " << std:: endl;
  271.         std::cout << s << std::endl;
  272.         break;
  273.  
  274.     case SR_INVALID:
  275.         std::cout << "The position is not valid." << std:: endl;
  276.         break;
  277.  
  278.     case SR_UNSOLVABLE:
  279.         std::cout << "The position cannot be solved." << std:: endl;
  280.         break;
  281.  
  282.     }
  283.  
  284.     std::cout << "Press any key to exit...";
  285.     getchar();
  286.     return 0;
  287. }
  288.  
  289. // ======================================================================================
  290.  
  291. void Sudoku::runUnitTests() {
  292.  
  293.     short dataZeroes[9][9] = {
  294.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  295.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  296.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  297.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  298.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  299.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  300.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  301.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  302.         {0, 0, 0, 0, 0, 0, 0, 0, 0}
  303.     };
  304.  
  305.     short dataValidPos1[9][9] = {
  306.         {5, 3, 4, 6, 7, 8, 9, 1, 2},
  307.         {6, 7, 2, 1, 9, 5, 3, 4, 8},
  308.         {1, 9, 8, 3, 4, 2, 5, 6, 7},
  309.         {8, 5, 9, 7, 6, 1, 4, 2, 3},
  310.         {4, 2, 6, 8, 5, 3, 7, 9, 1},
  311.         {7, 1, 3, 9, 2, 4, 8, 5, 6},
  312.         {9, 6, 1, 5, 3, 7, 2, 8, 4},
  313.         {2, 8, 7, 4, 1, 9, 6, 3, 5},
  314.         {3, 4, 5, 2, 8, 6, 1, 7, 9}
  315.     };
  316.  
  317.     short dataValidPos2[9][9] = {
  318.         {0, 0, 0, 0, 0, 0, 0, 0, 0},
  319.         {6, 0, 2, 1, 0, 0, 0, 0, 0},
  320.         {1, 0, 8, 3, 4, 2, 5, 6, 7},
  321.         {0, 0, 9, 7, 0, 0, 4, 2, 3},
  322.         {4, 0, 6, 8, 0, 0, 0, 0, 1},
  323.         {7, 1, 3, 9, 2, 0, 8, 0, 0},
  324.         {0, 0, 0, 5, 3, 0, 2, 8, 4},
  325.         {0, 0, 0, 4, 1, 0, 6, 0, 0},
  326.         {3, 0, 0, 0, 0, 6, 1, 0, 0}
  327.     };
  328.  
  329.     short dataInvalidRows[9][9] = {
  330.         {5, 3, 4, 6, 7, 8, 9, 1, 5},
  331.         {6, 7, 2, 1, 9, 5, 3, 4, 8},
  332.         {1, 9, 8, 3, 4, 2, 0, 6, 7},
  333.         {8, 5, 9, 7, 6, 1, 4, 2, 3},
  334.         {4, 2, 6, 8, 5, 3, 7, 9, 1},
  335.         {7, 1, 3, 9, 2, 4, 8, 5, 6},
  336.         {9, 6, 1, 5, 3, 7, 2, 8, 4},
  337.         {2, 8, 7, 4, 1, 9, 6, 3, 0},
  338.         {3, 4, 5, 2, 8, 6, 1, 7, 9}
  339.     };
  340.  
  341.     short dataInvalidCols[9][9] = {
  342.         {5, 3, 4, 6, 7, 8, 9, 1, 2},
  343.         {6, 7, 2, 1, 9, 0, 3, 4, 8},
  344.         {1, 9, 8, 3, 4, 2, 5, 6, 7},
  345.         {8, 5, 9, 7, 6, 1, 4, 2, 3},
  346.         {4, 2, 6, 8, 5, 3, 7, 9, 1},
  347.         {7, 1, 3, 9, 2, 4, 8, 5, 6},
  348.         {9, 6, 1, 5, 3, 7, 2, 8, 4},
  349.         {2, 8, 7, 4, 1, 9, 6, 3, 5},
  350.         {5, 4, 0, 2, 8, 6, 1, 7, 9}
  351.     };
  352.  
  353.     short dataInvalidSquares[9][9] = {
  354.         {5, 3, 4, 6, 7, 8, 9, 1, 2},
  355.         {6, 5, 2, 1, 9, 0, 3, 4, 8},
  356.         {1, 9, 8, 3, 4, 2, 5, 6, 7},
  357.         {8, 0, 9, 7, 6, 1, 4, 2, 3},
  358.         {4, 2, 6, 8, 5, 3, 7, 9, 1},
  359.         {7, 1, 3, 9, 2, 4, 8, 5, 6},
  360.         {9, 6, 1, 5, 3, 7, 2, 8, 4},
  361.         {2, 8, 7, 4, 1, 9, 6, 3, 5},
  362.         {3, 4, 5, 2, 8, 6, 1, 7, 9}
  363.     };
  364.  
  365.     Sudoku zeroes (dataZeroes);
  366.     Sudoku validPos1 (dataValidPos1);
  367.     Sudoku validPos2 (dataValidPos2);
  368.     Sudoku invalidRows (dataInvalidRows);
  369.     Sudoku invalidCols (dataInvalidCols);
  370.     Sudoku invalidSquares (dataInvalidSquares);
  371.  
  372.     std::cout << "Unit tests start..." << std::endl;
  373.  
  374.     assert(zeroes.checkValidRows());
  375.     assert(zeroes.checkValidCols());
  376.     assert(zeroes.checkValidSquares());
  377.     assert(zeroes.checkValid());
  378.     assert(zeroes.solve() == SR_SOLVED);
  379.  
  380.     assert(validPos1.checkValidRows());
  381.     assert(validPos1.checkValidCols());
  382.     assert(validPos1.checkValidSquares());
  383.     assert(validPos1.checkValid());
  384.     assert(validPos1.solve() == SR_SOLVED);
  385.  
  386.     assert(validPos2.checkValidRows());
  387.     assert(validPos2.checkValidCols());
  388.     assert(validPos2.checkValidSquares());
  389.     assert(validPos2.checkValid());
  390.     assert(validPos2.solve() == SR_SOLVED);
  391.     assert(validPos2.values[0][0] == 5);
  392.     assert(validPos2.values[0][1] == 3);
  393.     assert(validPos2.values[0][2] == 4);
  394.     assert(validPos2.values[0][3] == 6);
  395.     assert(validPos2.values[0][4] == 7);
  396.     assert(validPos2.values[0][5] == 8);
  397.     assert(validPos2.values[0][6] == 9);
  398.     assert(validPos2.values[0][7] == 1);
  399.     assert(validPos2.values[0][8] == 2);
  400.  
  401.     assert(!invalidRows.checkValidRows());
  402.     assert( invalidRows.checkValidCols());
  403.     assert( invalidRows.checkValidSquares());
  404.     assert(!invalidRows.checkValid());
  405.     assert( invalidRows.solve() == SR_INVALID);
  406.  
  407.     assert( invalidCols.checkValidRows());
  408.     assert(!invalidCols.checkValidCols());
  409.     assert( invalidCols.checkValidSquares());
  410.     assert(!invalidCols.checkValid());
  411.     assert( invalidCols.solve() == SR_INVALID);
  412.  
  413.     assert( invalidSquares.checkValidRows());
  414.     assert( invalidSquares.checkValidCols());
  415.     assert(!invalidSquares.checkValidSquares());
  416.     assert(!invalidSquares.checkValid());
  417.     assert( invalidSquares.solve() == SR_INVALID);
  418.  
  419.     std::cout << "All unit tests OK." << std::endl;
  420.  
  421. }
  422.  
Success #stdin #stdout 0.02s 3012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Unit tests start...
All unit tests OK.

 . . 4 | . . . | . . .
 6 . 2 | 1 . . | . . .
 1 . 8 | 3 4 2 | 5 6 7
 ------+-------+------
 . . 9 | 7 . . | 4 2 3
 4 . 6 | 8 . . | . . 1
 7 1 3 | 9 2 . | 8 . .
 ------+-------+------
 . . . | 5 3 . | 2 8 4
 . . . | 4 1 . | 6 . .
 3 . . | . . 6 | 1 . .

Solver starts, please wait...
Solution: 

 5 3 4 | 6 7 8 | 9 1 2
 6 7 2 | 1 9 5 | 3 4 8
 1 9 8 | 3 4 2 | 5 6 7
 ------+-------+------
 8 5 9 | 7 6 1 | 4 2 3
 4 2 6 | 8 5 3 | 7 9 1
 7 1 3 | 9 2 4 | 8 5 6
 ------+-------+------
 9 6 1 | 5 3 7 | 2 8 4
 2 8 7 | 4 1 9 | 6 3 5
 3 4 5 | 2 8 6 | 1 7 9

Press any key to exit...
https://ideone.com/iaNvZ4
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

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!