判断数独是否成功(c++)

一、问题描述

游戏中你需要在一个$9\ast 9$的方格内放置 1-9 的数字，让每一行、每一列和9个3*3的小方格都只出现一次 1-9 的数字，满足上述规则的数独，即为成功的数独！

二、解题思路

最开始的想法是用行、列和块的和来检查，但是显然是错误的，比如都填满5；所以我们需要依据规则来检查，即要检查1-9是否齐全并且没有重复。 所以，解题的想法就是：设置标志数组 tag，将要检查的行列块的当前位置的数字，作为tag的索引，相应位置填1，最后检查是否tag所以位置都为1，如果不是，说明，1-9中有数字没用，这就不是成功的数独；如果是，那就继续检查，当检查完所有的行、列和块后，即为成功的数独。

三、代码及注释

#include <iostream> using namespace std; class Sudoku{ public: void initSudoku(); bool checkAnswer(); private: int mySudoku[9][9]; }; void Sudoku::initSudoku() { for(int i=0;i<9;i++) for(int j=0;j<9;j++) cin>>mySudoku[i][j]; } bool review(int* p) //判断是否有没有的数字 { int i=1; while(i<10) { if(!*(++p)) { return false; } ++i; } return true; } void zero_tag(int* p) //每次判断后对tag数组清零 { int i=1; while(i<10) { *(++p)=0; ++i; } } bool Sudoku::checkAnswer() { int tag[10]={0}; //0号单元不用 int curValue=0; for(int i=0;i<9;i++) //对每一行进行检查 { for(int j=0;j<9;j++) { curValue=mySudoku[i][j]; tag[curValue]=1; //如果有重复也会是1，但是缺少的数字相应的位置上就会是0 } if(!review(tag)) return false; //有重复元素 zero_tag(tag);//每次判断后对tag数组清零 } for(int i=0;i<9;i++) //对每一列进行检查 { for(int j=0;j<9;j++) { curValue=mySudoku[j][i]; tag[curValue]=1; } if(!review(tag)) return false; //有重复元素 zero_tag(tag);//每次判断后对tag数组清零 } for(int k=0;k<9;k=k+3) //对每一3x3方块进行检查 { for(int t=0;t<9;t=t+3) //对1-3行，1-9列进行检查 { for(int i=k;i<k+3;i++) //计算每一个方块的和 for(int j=t;j<t+3;j++) { curValue=mySudoku[j][i]; tag[curValue]=1; } if(!review(tag)) return false; //有重复元素 zero_tag(tag);//每次判断后对tag数组清零 } } return true; //经过了所有的行，列块的检查 } int main() { int t; cin>>t; Sudoku S[t]; for(int i=0;i<t;i++) { S[i].initSudoku(); if(S[i].checkAnswer()) cout<<"Yeah!"<<endl; else cout<<"Oh,No!"<<endl; } return 0; }