歡迎fork and star：Nowcoder-Repository-github

37. Sudoku Solver

題目

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution. 
           

解析

• 解題思路：深度周遊的過程，從開始一直掃描，直到遇到空字元，便可開始填數字，該位置的數字從1~9依次周遊，不行的時候就回退

// 37. Sudoku Solver
class Solution_37 {
public:
	bool isValid(vector<vector<char>>& board,int i,int j) //隻需要判斷目前行，列，方格是否合法，節省時間
	{
		for (int row = 0; row < 9;row++)
		{
			if (row!=i&&board[i][j]==board[row][j])
			{
				return false;
			}
		}
		for (int col = 0; col < 9;col++)
		{
			if (col!=j&&board[i][j]==board[i][col])
			{
				return false;
			}
		}
		for (int row = i / 3 * 3; row < i / 3 * 3 + 3;row++)
		{
			for (int col = j / 3 * 3; col < j / 3 * 3 + 3;col++)
			{
				if ((row!=i||col!=j)&&board[i][j]==board[row][col]) //小方格也需要行列判斷
				{
					return false;
				}
			}
		}
		return true;
	}

	bool dfs(vector<vector<char> > &board,int i,int j)
	{
		if (i==9)
		{
			return true;
		}
		if (j==9)
		{
			return dfs(board, i + 1, 0);
		}

		if (board[i][j]=='.')
		{
			for (char k = '1'; k <='9';k++)
			{
				board[i][j] = k;
				if (isValid(board,i,j))
				{
					if (dfs(board, i, j + 1))
					{
						return true;
					}
				}
				board[i][j] = '.'; //達到回溯的目的
			}
		}
		else
		{
			return dfs(board, i, j + 1);
		}
		return false;
	}

	void solveSudoku(vector<vector<char>>& board) {

		if (board.size()<9||board[0].size()<9)
		{
			return;
		}
		dfs(board, 0, 0);
		return;
	}
};
           

題目來源

• [LeetCode] Sudoku Solver 求解數獨

C/C++基本文法學習

STL

C++ primer