湖北孝感展示型网站建设价格,外贸网站怎么推广,白山网站设计,做网站类型的营业执照证明如何填写1 题目
编写一个程序#xff0c;通过填充空格来解决数独问题。
数独的解法需 遵循如下规则#xff1a;
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。#xff08;请参考示例图#xff09; …1 题目
编写一个程序通过填充空格来解决数独问题。
数独的解法需 遵循如下规则
数字 1-9 在每一行只能出现一次。 数字 1-9 在每一列只能出现一次。 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。请参考示例图 数独部分空格内已填入了数字空白格用 . 表示。
2 解法
核心思想是, 首先把所有未确定值的位置收集起来, 让每个位置都选取其可选的值, 这就要有数据结构记录下其所出的行, 列, 以及块已经被选的值, 这样遍历其可选的值, 并且如果之前选的值不合适, 引入回退机制.
代码: int row[9];
int col[9];
int block[3][3];
bool valid;
vectorpairint, int blanks;
vectorvectorchar *pBoard;void flip(int row_index, int col_index, int number, bool changeBoard) {row[row_index] ^ (1 number);col[col_index] ^ (1 number);block[row_index / 3][col_index / 3] ^ (1 number);if (changeBoard) {if ((*pBoard)[row_index][col_index] .) {(*pBoard)[row_index][col_index] 1 number;} else {(*pBoard)[row_index][col_index] .;}}
}void dfs(int blanks_index) {if (blanks_index blanks.size()) {valid true;return;}int row_index blanks[blanks_index].first;int col_index blanks[blanks_index].second;int number 0;while (true) {if (number 9)return;int bin_num (1 number);if (row[row_index] bin_num || col[col_index] bin_num || block[row_index / 3][col_index / 3] bin_num) {number ;continue;}flip(row_index, col_index, number, true);dfs(blanks_index 1);if (!valid) {flip(row_index, col_index, number, true);number ;}}
}void solveSudoku(vectorvectorchar board) {memset(row, 0, sizeof(row));memset(col, 0, sizeof(col));memset(block, 0, sizeof(block));valid false;pBoard board;for (int i 0; i 9; i ) {for (int j 0; j 9; j ) {if (board[i][j] .) {blanks.push_back(make_pair(i, j));} else {int number board[i][j] - 1;flip(i, j, number, false);}}}dfs(0);
}
