网易互娱23届实习笔试_3x3锯齿数独网易互娱23届实习笔试

一、输入：
输入一个3x3数独，字符'.'代表空
输入三个宫的域，每个宫包括三个位置，[0,0]表示0行0列
二、输出要求：
1.每个宫里最终123各出现一次，
【网易互娱23届实习笔试_3x3锯齿数独】2.数独中的行列里不出现重复字符；

输出满足条件的解
思想：先根据输入找到所有行列不重复的数独，再判断三个宫是否满足不重复；

1 #include 2 #include 3 using namespace std; 4 int a[3][3]; //存储三个宫区域 5 int cnt; //记录满足的个数 6 bool isValid(int row, int col, char val, vector>& board) { 7for (int i = 0; i < 3; i++) { // 判断行里是否重复 8if (board[row][i] == val) { 9return false; 10} 11} 12for (int j = 0; j < 3; j++) { // 判断列里是否重复 13if (board[j][col] == val) { 14return false; 15} 16} 17return true; 18 } 19 bool func(vector> board){ 20for (int i = 0; i<3; i++){//第i个宫 21intvec[3]; 22memset(vec,0,sizeof(vec)); 23for (int j = 0; j < 3; j++){ 24if (vec[board[a[i][j]/3][a[i][j]%3]-'1']==1){ 25return false; 26cout <<"失败"<< a[i][j] << endl; 27} 28vec[board[a[i][j] / 3][a[i][j] % 3]-'1'] = 1; 29} 30} 31return true; 32 } 33 34 bool backtracking(vector>& board) { 35int x, y; 36for (int i = 0; i < board.size(); i++) {// 遍历行 37for (int j = 0; j < board[0].size(); j++) { // 遍历列 38x = i; 39y = j; 40if (board[i][j] != '.') continue; 41for (char k = '1'; k <= '3'; k++) {// (i, j) 这个位置放k是否合适 42if (isValid(i, j, k, board)) { 43board[i][j] = k; // 放置k 44if (backtracking(board)) { 45return true; // 如果找到合2 适一组立刻返回 46} 47board[i][j] = '.'; // 回溯，撤销k 48} 49} 50return false; // 9个数都试完了，都不行，那么就返回false 51} 52} 53if(x==2&&y==2){ //判断是否满足宫 54if(func(board)){ 55cout << "cnt++:" << endl; 56cnt++; 57for(int i=0; i<3; i++){ 58for(int j=0; j<3; j++){ 59cout<>board={{0,0,0},{0,0,0},{0,0,0}}; 78for(int i=0; i<3; i++){ 79for(int j=0; j<3; j++){ 80char ch; 81cin>>ch; 82board[i][j]=ch; 83//cout<> x >> y; 90a[i][j] = 3 * x + y; 91//cout << 3 * x + y; 92} 93} 94cout << endl; 95cout << "x" << endl; 96backtracking(board); 97int coun = cnt; 98cout << "answer " << cnt << endl; 99return 0; 100 }

测例1：
输入