九宫格问题

红太狼 2022-08-11 00:40 230阅读 0赞

\#include <iostream>  
\#include <deque>//STL 双端队列容器  
\#include<fstream>  
\#include"pos.h"  
using namespace std;  
ofstream fout("sudoku.txt");  
deque <Pos> D;             
int lay(deque <Pos> & D);  
int checkout(Pos p, int n);  
  
  
int sudoku\[9\]\[9\] = \{  
// 九宫格数组  
\{0, 0, 0, 0, 5, 8, 0, 4, 1\},  
\{0, 8, 1, 0, 3, 0, 0, 7, 0\},  
\{0, 6, 0, 1, 7, 0, 8, 5, 0\},  
\{0, 9, 3, 0, 8, 5, 0, 0, 7\},  
\{0, 0, 2, 3, 6, 0, 5, 0, 0\},  
\{0, 5, 0, 7, 9, 0, 0, 0, 4\},  
\{9, 0, 7, 0, 4, 3, 0, 6, 0\},  
\{4, 0, 0, 0, 0, 6, 7, 8, 2\},  
\{8, 1, 6, 0, 0, 0, 0, 3, 9\},  
\};  
  
  
void main()  
\{   
fout<<"未填写的九宫格(0表示未填写)：\\n";  
fout<<"---------------------\\n";  
cout<<"未填写的九宫格(0表示未填写)："<<endl;  
cout << "---------------------" << endl;  
for (int i = 0; i < 9; i++)  
\{  
for (int j = 0; j <9; j++)  
\{  
if (j % 3 == 0)   
\{  
cout << " ";  
fout<<" ";  
\}  
cout << sudoku\[i\]\[j\] << " ";  
fout<<sudoku\[i\]\[j\]<<" ";  
\}  
cout << " ";  
fout<<" ";  
cout << endl;  
fout<<"\\n";  
if ( (i+1) % 3 == 0 ) \{  
cout << "---------------------" << endl;  
fout<<"---------------------\\n";  
\}  
\}  
fout<<"完成之后的九宫格：\\n";  
cout<<"完成之后的九宫格："<<endl;// Q中保存需要放置数字的位置  
  
  
for (int i = 0; i < 9; i++)  
\{  
for (int j = 0; j < 9; j++)//遍历一遍九宫格数组  
\{  
if ( sudoku\[i\]\[j\]==0) //找到没有填写数字的位置  
\{  
D.push\_back(Pos(i, j));//表示在尾部加入一个数据,这条语句的作用是将所有的0的坐标放到容器也就是队列之中，队列是从（0,0）开始的  
\}  
\}  
\}  
  
  
lay(D);//往空着的地方填写，并且输出完成之后的九宫格  
  
  
  
\}  
int lay(deque <Pos> & D)  
\{        // 这个函数利用了递归，结束的条件是没有再放置数字的位置，也就是九宫格数组没有0  
                   
if (D.empty()) //判断容器是否为空，若true则容器中无元素  
\{                    
fout<<"---------------------\\n";  
   cout << "---------------------" << endl;  
   for (int i = 0; i < 9; i++)  
   \{  
   for (int j = 0; j <9; j++)  
  \{  
 if (j % 3 == 0)   
 \{  
cout << " ";  
fout<<" ";  
 \}  
   cout << sudoku\[i\]\[j\] << " ";  
   fout<<sudoku\[i\]\[j\]<<" ";  
  \}  
    cout << " ";  
    fout<<" ";  
    cout << endl;  
    fout<<"\\n";  
 if ( (i+1) % 3 == 0 )  
  \{  
cout << "---------------------" << endl;  
fout<<"---------------------\\n";  
  \}  
    \}  
return true;  
\}  
  
  
 Pos sodu(D.front().row, D.front().col); // 当前需要放置的位置信息，容器中首元素的行和列，调用带参数的构造函数  
 D.pop\_front();//删除双端队列之中最前面的一个元素  
  
  
for (int i = 1; i <= 9; i++)// 从1到9不断的尝试数字是否合适，i代表要放置的数字  
\{                      
if ( checkout(sodu, i) )//在纵向和横向以及九宫格内没有重复的数字，执行下面的代码  
\{  
sudoku\[sodu.row\]\[sodu.col\] = i; // 放置数字i到当前位置  
  
if ( !lay(D) )                  // 放置下一位置，下一位置放置失败，则在当前位置尝试放置下一个i   
sudoku\[sodu.row\]\[sodu.col\] = 0;    // 将当前位置值重置   
\}  
\}   
D.push\_front(sodu); //当前位置不论怎么放置数字，下一位置都无法放置成功，  
       // 重新插入该位置信息，返回上一级放置位置。双端队列头部增加一个元素  
return false;  
\}  
  
  
  
  
int checkout(Pos p, int n)//检验要放置的数字是否合适，n代表不断地尝试去放入其中的数字  
\{  
int c\_row = p.row;//检验横向以及纵向有没有我们要添加的数字  
int c\_col = p.col;                  
for (int i = 0; i < 9; i++)   
\{                             
if ( sudoku\[i\]\[c\_col\] == n||  sudoku\[c\_row\]\[i\]==n )   
\{  
return false;  
\}  
\}                                
int g\_row = ( c\_row / 3 ) \* 3;// 验证3\*3格子内是否有重复的数字  
int g\_col = ( c\_col / 3 ) \* 3;  
for (int i = 0; i < 2; i++)   
\{  
if (  sudoku\[g\_row\]\[i + g\_col\]== n||sudoku\[g\_row + i\]\[g\_col\]== n ||sudoku\[g\_row+i\]\[g\_col+i\]==n)   
\{  
return false;  
\}  
\}  
  
  
return true;  
\}