很菜的Sodoku Solver

Viktor posted @ Sep 09, 2008 12:46:32 AM in C with tags soduku solver 数独 c++ 排除法 很菜 , 3212 阅读

其实是模拟了手工填写数独的方法，用的排除法。这个代码的不足在于没有怎么规划，其实board::pencilMark()完全可以做成按行、列、正方形顺序将所有的方格的pencil mark全部填好。稍加改动，可以解１６*１６或８*８的数独。

  1. using namespace std;
  2.  
  3. class cell
  4. {
  5. private:
  6.     int number;
  7.     int pencil;
  8. public:
  9.     bool getPencil(int num);
  10.     bool setPencil(int num);
  11.     bool isHavingPencil(void);
  12.     int  getAllPencil(void);
  13.     bool erasePencil(int num);
  14.     int  getNumber(void);
  15.     bool fillNumber(int num);
  16.     bool initCell(int num);
  17.     bool clearPencil(void);
  18. protected:
  19. };
  20.  
  21. bool cell::getPencil(int num)
  22. {
  23.     return (pencil & (1<<num))?true:false;
  24. }
  25.  
  26. bool cell::setPencil(int num)
  27. {
  28.     if(!num)
  29.         return true;
  30.     if(pencil & (1<<num))
  31.         ;
  32.     else
  33.         pencil += (1<< num);
  34.     return true;
  35. }
  36.  
  37. bool cell::isHavingPencil(void)
  38. {
  39.     return pencil?true:false;
  40. }
  41.  
  42. int  cell::getAllPencil(void)
  43. {
  44.     return pencil;
  45. }
  46.  
  47. bool cell::erasePencil(int num)
  48. {
  49.     if(!num)    //Meet zero
  50.         return true;
  51.     if(pencil & (1 << num))
  52.         pencil -= 1<< num;
  53.     return true;
  54. }
  55.  
  56. int  cell::getNumber(void)
  57. {
  58.     return number;
  59. }
  60.  
  61. bool cell::fillNumber(int num)
  62. {
  63.     number = num;
  64.     clearPencil();
  65.     return true;
  66. }
  67.  
  68. bool cell::initCell(int num)
  69. {
  70.     number = num;
  71.     pencil = num?0:((1 << 10) - 2);
  72.     return true;
  73. }
  74.  
  75. bool cell::clearPencil(void)
  76. {
  77.     pencil = 0;
  78.     return true;
  79. }
  80.  
  81. class board
  82. {
  83. private:
  84.     cell boardCells[10][10];
  85.     int blankCell;
  86.     int cellSolved;
  87. public:
  88.     bool solveOneStep(void);
  89.     bool pencilMark(int x, int y);
  90.     bool decideNumber(void);
  91.     void printBoard(void);
  92.     bool readCell(void);
  93. protected:
  94.  
  95. };
  96.  
  97. void getSquare(const int x, const int y, int & left, int & top)
  98. {
  99.     static int coordinates[]={0,1,1,1,4,4,4,7,7,7};
  100.     left = coordinates[x];
  101.     top = coordinates[y];
  102.     return;
  103. }
  104.  
  105. bool board::pencilMark(int x, int y) //True for having pencil mark, false for not.
  106. {
  107.     int linearPointer, sqLinePointer, sqColumnPointer, sqLeft, sqTop;
  108.     int reading;
  109.  
  110.     if(!(boardCells[x][y].getNumber())) //Blank Cell.
  111.     {
  112.         boardCells[x][y].initCell(0);   //Initialize pencil marks.
  113.         //Line
  114.         for(linearPointer = 1; linearPointer <= 9; linearPointer ++)
  115.         {
  116.             if (linearPointer == y)
  117.                 continue;
  118.             reading = boardCells[x][linearPointer].getNumber();
  119.             if (reading)
  120.                 boardCells[x][y].erasePencil(reading);
  121.         }
  122.    
  123.         //Column
  124.         for(linearPointer = 1; linearPointer <= 9; linearPointer ++)
  125.         {
  126.             if (linearPointer == x)
  127.                 continue;
  128.             reading = boardCells[linearPointer][y].getNumber();
  129.             if (reading)
  130.                 boardCells[x][y].erasePencil(reading);
  131.         }
  132.        
  133.         //Square
  134.         getSquare(x, y, sqLeft, sqTop);
  135.         for(sqLinePointer = 0; sqLinePointer < 3; sqLinePointer ++)
  136.         {
  137.             if (x - sqLeft == sqLinePointer)
  138.                 continue;
  139.             for(sqColumnPointer = 0; sqColumnPointer < 3; sqColumnPointer ++)
  140.             {
  141.                 if(y - sqTop == sqColumnPointer)
  142.                     continue;
  143.                 reading = boardCells[sqLeft + sqLinePointer][sqTop + sqColumnPointer].getNumber();
  144.                 if(reading)
  145.                     boardCells[x][y].erasePencil(reading);
  146.             }
  147.         }
  148.     }
  149.     else
  150.         return true;
  151.     return boardCells[x][y].isHavingPencil();
  152. }
  153.  
  154. bool board::decideNumber(void) //True for progress, false for no.
  155. {
  156.     int x, y, marks;
  157.     bool retlog;
  158.  
  159.     cellSolved = 0;
  160.  
  161.     //Calculate pencil marks.
  162.     for(x = 1; x <= 9; x++)
  163.     {
  164.         for(y = 1; y <= 9; y++)
  165.         {
  166.             retlog = pencilMark(x, y);
  167.             if(!retlog)
  168.                 goto noSolution;
  169.         }
  170.     }
  171.  
  172.     //Search for single pencil mark.
  173.     for(x = 1; x <= 9; x++)
  174.     {
  175.         for(y = 1; y<= 9; y++)
  176.         {
  177.             if(boardCells[x][y].getNumber()) //Already have number
  178.                 continue;
  179.             marks = boardCells[x][y].getAllPencil();
  180.             if(!(marks & (marks - 1))) // Only have one number.
  181.             {
  182.                 switch(marks)
  183.                 {
  184.                 case 2:
  185.                     boardCells[x][y].initCell(1);break;
  186.                 case 4:
  187.                     boardCells[x][y].initCell(2);break;
  188.                 case 8:
  189.                     boardCells[x][y].initCell(3);break;
  190.                 case 16:
  191.                     boardCells[x][y].initCell(4);break;
  192.                 case 32:
  193.                     boardCells[x][y].initCell(5);break;
  194.                 case 64:
  195.                     boardCells[x][y].initCell(6);break;
  196.                 case 128:
  197.                     boardCells[x][y].initCell(7);break;
  198.                 case 256:
  199.                     boardCells[x][y].initCell(8);break;
  200.                 case 512:
  201.                     boardCells[x][y].initCell(9);break;
  202.                 default:
  203.                     cout << "ERROR! ";
  204.                 }
  205.                 blankCell--;
  206.                 cellSolved++;
  207.             }
  208.         }
  209.     }
  210.     if(cellSolved)
  211.         return true;
  212.    
  213.     int searchNum;
  214.     int markCount;
  215.     int lastPos, lastSqX, lastSqY;
  216.     int linearIndex, sqRowIndex, sqColumnIndex, sqLeft, sqTop;
  217.     //Search for only candidates.
  218.          
  219.     //By Row
  220.     for(x = 1; x <= 9; x++)
  221.     {
  222.         for(searchNum = 1; searchNum <= 9; searchNum ++)
  223.         {
  224.             markCount = 0;
  225.             lastPos = 0;
  226.             for(linearIndex = 1; linearIndex <= 9; linearIndex++)
  227.             {
  228.                 if(boardCells[x][linearIndex].getPencil(searchNum))
  229.                 {
  230.                     markCount ++;
  231.                     lastPos = linearIndex;
  232.                 }                   
  233.             }
  234.             if(markCount == 1)
  235.             {
  236.                 boardCells[x][lastPos].initCell(searchNum);
  237.                 goto foundSolution;
  238.             }
  239.         }
  240.     }
  241.  
  242.     //By Column
  243.     for(y = 1; y <= 9; y++)
  244.     {
  245.         for(searchNum = 1; searchNum <= 9; searchNum ++)
  246.         {
  247.             markCount = 0;
  248.             lastPos = 0;
  249.             for(linearIndex = 1; linearIndex <= 9; linearIndex++)
  250.             {
  251.                 if(boardCells[linearIndex][y].getPencil(searchNum))
  252.                 {
  253.                     markCount ++;
  254.                     lastPos = linearIndex;
  255.                 }                   
  256.             }
  257.             if(markCount == 1)
  258.             {
  259.                 boardCells[lastPos][y].initCell(searchNum);
  260.                 goto foundSolution;
  261.             }
  262.         }
  263.     }
  264.    
  265.     //By Square
  266.     for(sqLeft = 1; sqLeft < 9; sqLeft += 3)
  267.     {
  268.         for(sqTop = 1; sqTop < 9; sqTop += 3)
  269.         {
  270.             for(searchNum = 1; searchNum <= 9; searchNum ++)
  271.             {
  272.                 markCount = 0;
  273.                 lastSqX = 0, lastSqY = 0;
  274.                 for(sqRowIndex = 0; sqRowIndex < 3; sqRowIndex ++)
  275.                 {
  276.                     for(sqColumnIndex = 0; sqColumnIndex < 3; sqColumnIndex++)
  277.                     {
  278.                         if(boardCells[sqLeft + sqRowIndex][sqTop + sqColumnIndex].getPencil(searchNum))
  279.                         {
  280.                             markCount ++;
  281.                             lastSqX = sqRowIndex, lastSqY = sqColumnIndex;
  282.                         }
  283.                     }
  284.                 }
  285.                 if(markCount == 1)
  286.                 {
  287.                     boardCells[sqLeft + lastSqX][sqTop + lastSqY].initCell(searchNum);
  288.                     goto foundSolution;
  289.                 }
  290.             }
  291.         }
  292.     }
  293.            
  294.     if(blankCell)   //Not solved yet.
  295.         cout << "Cannot solve. " << endl;
  296.     return false;
  297.  
  298. foundSolution:
  299.     cellSolved ++;
  300.     blankCell --;
  301.     return true;
  302.    
  303. noSolution:
  304.     cout << "No Solution!!" << endl;
  305.     return false;
  306.    
  307. }
  308.  
  309. bool board::solveOneStep(void)
  310. {
  311.     int x, y;
  312.     for(x = 1; x <= 9; x++)
  313.         for(y = 1; y<= 9; y++)
  314.             pencilMark(x,y);
  315.     return decideNumber();
  316. }
  317.  
  318. bool board::readCell(void)
  319. {
  320.     int x, y, recv;
  321.     blankCell = 0;
  322.     for(x = 1; x <= 9; x++)
  323.         for(y = 1; y <= 9; y++)
  324.         {
  325.             cin >> recv;
  326.             boardCells[x][y].initCell(recv);
  327.             if(recv==0)
  328.                 blankCell++;
  329.         }
  330.     return true;
  331. }
  332.  
  333. void board::printBoard(void)
  334. {
  335.     int x, y, num;
  336.     num = 0;
  337.     for(x = 1; x <= 9; x++)
  338.     {
  339.         for(y = 1; y <= 9; y++)
  340.         {
  341.             num = boardCells[x][y].getNumber();
  342.             cout << " " << num;
  343.         }
  344.         cout << "\n";
  345.     }
  346. }
  347.  
  348. int _tmain(void)
  349. {
  350.         board game;
  351.     int counter = 0;
  352.    
  353.     cout << "VIKTOR\'S SODUKU SOLVER VER 1.00A SEPT 7, 2008\n";
  354.     cout << "Input soduku, 0 for blank\n";
  355.    
  356.     game.readCell();
  357.     cout << "Your initial soduku is: \n\n";
  358.     game.printBoard();
  359.  
  360.     while(game.solveOneStep())
  361.     {
  362.         counter ++;
  363.     /*DEBUG CODE
  364.         cout << "The " << counter << " step of soduku is: \n\n";
  365.         game.printBoard();
  366.     */
  367.     }
  368.  
  369.     cout << "Your soduku is solved after " << counter << " steps as follows: \n" ;
  370.     game.printBoard();
  371.    
  372.     return 0;
  373. }
  374.  
  375.  

  • 无匹配
Small_feed 评论 (1)
1
[回复]
Avatar_small
Nagaland 7th Class 说:
Sep 29, 2023 05:18:38 PM

Nagaland Board 7th Class Book 2024 for Science, Social Science, English, Hindi, Mathematics, EVS, Various Provide in School Wise Free Distribution in Government School, NBSE High School Various Class Complete Students Do not Waste Summers Holidays, Download Nagaland Board Class Book 2024 Regular Practice new Lessions for Students Best idea Students Method.Nagaland Board Class Textbook 2024 Download Nagaland 7th Class Books 2024 Available Official Website, Our Portal Provide Nagaland Board High School Books 2024 Download, Hindi Medium, English Medium and Urdu Medium Textbooks.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter