原來...放暑假了喔...

好像缺席幾次了，
繼續缺席中...
不過這次是數獨啊...
最近有想寫個數獨的小遊戲...
我倒是覺得題目比較難出...

我的是C#版本的，
應該沒辦法打分數，
稍微分享一下

        /// <summary>
        /// 檢查全部的數字是否有重複的
        /// </summary>
        /// <returns></returns>
        private ECheckResult CheckAllNumberAllow()
        {
            ECheckResult result = ECheckResult.SUCCESS;
            //九宮格的
            List<List<List<int>>> listList = new List<List<List<int>>>();
            //直排的
            List<List<int>> list1 = new List<List<int>>();
            //橫排的
            List<List<int>> list2 = new List<List<int>>();

            int num = (int)Math.Sqrt(lineNumber);
            //初始化資料
            for(int i=0;i<lineNumber;i++)
            {
                list1.Add(new List<int>());
                list2.Add(new List<int>());
            }
            for(int i=0;i<num;i++)
            {
                List<List<int>> list = new List<List<int>>();
                for(int j=0;j<num;j++)
                    list.Add(new List<int>());
                listList.Add(list);
            }

            for(int i=0;i<lineNumber;i++)
            {
                for(int j=0;j<lineNumber;j++)
                {
                    int num1 = i / num;
                    int num2 = j / num;
                    int index1 = i * lineNumber + j;
                    int index2 = j * lineNumber + i;
                    int number1 = ansList[index1];
                    int number2 = ansList[index2];

                    //檢查是否有空白的，也就是數字是0的，如果有直接回傳
                    if (ansList[index1] == 0)
                        return ECheckResult.NULL;

                    if (result == ECheckResult.DUPLICATE)
                        continue;

                    //檢查直排是否有重複的
                    if (list1[i].Contains(number1))
                        result = ECheckResult.DUPLICATE;
                    else
                        list1[i].Add(number1);

                    //檢查橫排是否有重複的
                    if (list2[j].Contains(number2))
                        result = ECheckResult.DUPLICATE;
                    else
                        list2[j].Add(number2);

                    //檢查九宮格是否有重複的
                    List<int> intList = listList[num1][num2];
                    if (intList.Contains(number1))
                        result = ECheckResult.DUPLICATE;
                    else
                        listList[num1][num2].Add(number1);
                }
            }
            return result;
        }

出差五天，與世隔絕，終於回來了

這次用 Python 來寫。

class Solution:
    def isValidSudoku(self, board):
        
        checkR = {}
        checkC = {}
        checkB = {}
        
        for i in range(9):
            for j in range(9):
                value = board[i][j]
                if (value != "."):
                    # 判斷列有無重複
                    rKey = str(i) + "=" + value
                    if (rKey in checkR):
                        return False
                    # 判斷行有無重複
                    cKey = str(j) + "=" + value
                    if (cKey in checkC):
                        return False
                    # 判斷九宮格有無重複
                    bKey = str(i//3*3 + j//3) + "=" + value
                    if (bKey in checkB):
                        return False
                    # 紀錄 Key 值
                    checkR[rKey] = checkC[cKey] = checkB[bKey] = 1
        return True

這題我卡在判斷九宮格的地方，計算公式用 Excel 拉了好久才拉出來，哈哈哈。
=FLOOR.MATH($A2/3)*3+FLOOR.MATH(B$1/3)

計算時間複雜度，我會將所有方格數當作 n，
因為方格數不會因為程式寫法不同而增加。

接著以大大的程式來看，外層的兩個迴圈算 n，
checkRepeat 內繞 arrTemp 的迴圈也算 n，
相乘後，時間複雜度是 O(n²) 沒錯。

話說原來 ² 可以打的出來，一直以為數學公式才有。

我也來貼個省一篇文章, 原諒我喜歡打得很長哈哈。

class Solution {
public:
	const int SIZE = 9;
	const int SQUARE_SIZE = 3;
	vector<vector<bool>> _checkCol;
	vector<vector<bool>> _checkRow;
	vector<vector<bool>> _checkSquare;

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

		_checkCol = vector<vector<bool>>(SIZE, vector<bool>(SIZE, true));
		_checkRow = vector<vector<bool>>(SIZE, vector<bool>(SIZE, true));
		_checkSquare = vector<vector<bool>>(SIZE, vector<bool>(SIZE, true));
        
        // 找出目前已經使用過的
        
		for (int index = 0; index < SIZE; index++)
		{
			SetCheckRow(board, _checkCol[index], index);
			SetCheckCol(board, _checkRow[index], index);
			SetCheckSquare(board, _checkSquare[index], (index / 3) * 3, (index * 3) % 9);
		}
        
        // 開始插入數字
		Run(board, 0, 0, 0);
	}

	bool Run(vector<vector<char>>& board, int finish, int row, int col)
	{
        // 全部數字都已插入就完成
		if (finish == 81)
		{
			return true;
		}
        
        // 已插入的可直接跳過
		if (board[row][col] != '.')
		{
			return Run(board, finish + 1, row + ((col + 1) / SIZE), ((col + 1) % SIZE));
		}
        
        // 計算方形的第一個位置
		const int squareIndex = (row / 3) * 3 + (col / 3);

		for (int index = 0; index < SIZE; index++)
		{
            // 檢查是否有沒有被使用過
            // 沒有即可設為使用，進入下一格
            // 若無法完成81格則回朔並且跳過
			if (_checkCol[col][index]
				&& _checkRow[row][index]
				&& _checkSquare[squareIndex][index])
			{

				_checkCol[col][index] = false;
				_checkRow[row][index] = false;
				_checkSquare[squareIndex][index] = false;
				board[row][col] = index + 49;

				if (Run(board, finish + 1, row + ((col + 1) / SIZE), ((col + 1) % SIZE)))
				{
					return true;
				}

				_checkCol[col][index] = true;
				_checkRow[row][index] = true;
				_checkSquare[squareIndex][index] = true;
				board[row][col] = '.';
			}
		}

		return false;
	}
    
    // 初始化設置已使用的Col 
	void SetCheckCol(const vector<vector<char>>& board, vector<bool>& check, const int index)
	{
		for (int col = 0; col < SIZE; col++)
		{
			if (board[index][col] != '.')
			{
				check[board[index][col] - 49] = false;
			}
		}
	}
    
    // 初始化設置已使用的Row
	void SetCheckRow(const vector<vector<char>>& board, vector<bool>& check, const int index)
	{
		for (int row = 0; row < SIZE; row++)
		{
			if (board[row][index] != '.')
			{
				check[board[row][index] - 49] = false;
			}
		}
	}

    // 初始畫設置已使用的Square
	void SetCheckSquare(const vector<vector<char>>& board, vector<bool>& check, const int rowIndex, const int colIndex)
	{
		int index = 0;

		for (int row = rowIndex; row < rowIndex + SQUARE_SIZE; row++)
		{
			for (int col = colIndex; col < colIndex + SQUARE_SIZE; col++) {
				if (board[row][col] != '.')
				{
					check[board[row][col] - 49] = false;
				}
			}
		}
	}

};

這圖似乎沒參考價值......