1 題目

編寫一個程序，通過填充空格來解決數(shù)獨問題。

數(shù)獨的解法需 遵循如下規(guī)則：

數(shù)字?1-9?在每一行只能出現(xiàn)一次。
數(shù)字?1-9?在每一列只能出現(xiàn)一次。
數(shù)字?1-9?在每一個以粗實線分隔的?3x3?宮內(nèi)只能出現(xiàn)一次。（請參考示例圖）
數(shù)獨部分空格內(nèi)已填入了數(shù)字，空白格用?'.'?表示。

2 解法

核心思想是, 首先把所有未確定值的位置收集起來, 讓每個位置都選取其可選的值, 這就要有數(shù)據(jù)結(jié)構(gòu)記錄下其所出的行, 列, 以及塊已經(jīng)被選的值, 這樣遍歷其可選的值, 并且如果之前選的值不合適, 引入回退機制.

代碼:

?

int row[9]; int col[9]; int block[3][3]; bool valid; vector<pair<int, int>> blanks; vector<vector<char>> *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(vector<vector<char>>& 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); }

總結(jié)

以上是生活随笔為你收集整理的leetcode37 --- solveSudoku(解数独)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。