iT邦幫忙

5

[演算法][JavaScript]演算法挑戰系列(10)-Valid Sudoku

  • 分享至 

  • xImage
  •  

嗨啊,這是放暑假開始的第一篇文章,雖然在這裡的大大幾乎都沒暑假了XD,不過還是讓我們感染一下這種快樂好了,哈哈哈,說到學生時期,我很愛玩的一個遊戲就叫數獨,常常一天就廢寢忘食的解上好幾題,連大學打工在便利商店都會拿報紙起來找題目,哈哈哈,所以今天就來解個關於數讀題目吧!不過沒有大家想像的那麼困難,我們只是要判斷目前傳進來的陣列算不算是一個正確的數讀題目,那就直接來看個題目吧!

題目名稱:Valid Sudoku
難易度:中
題目內容:輸入一個9乘9的二維陣列,並判斷是不是有效數獨題目,規則如下:
一、每一行由1-9隨機組成,並不得重複(如下圖藍色框框)。
二、每一列由1-9隨機組成,並不得重複(如下圖紅色框框)。
三、把一個二維陣列分成九個九宮格,每一宮格的數字也是由1-9隨機組成,並不得重複(如下圖綠色框框):
https://ithelp.ithome.com.tw/upload/images/20180707/20106935MGqsg06g9o.jpg
例如:
1.傳入以下陣列:

[
  ["5","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

因為每一行、每一列及每一宮格都沒有重複的數字,所以回傳True。

2.傳入以下陣列:

[
  ["8","3",".",".","7",".",".",".","."],
  ["6",".",".","1","9","5",".",".","."],
  [".","9","8",".",".",".",".","6","."],
  ["8",".",".",".","6",".",".",".","3"],
  ["4",".",".","8",".","3",".",".","1"],
  ["7",".",".",".","2",".",".",".","6"],
  [".","6",".",".",".",".","2","8","."],
  [".",".",".","4","1","9",".",".","5"],
  [".",".",".",".","8",".",".","7","9"]
]

因為在左上角的那一個九宮格中,數字8重複出現了,所以回傳False。

說一下這次的解題過程好了,其實是在打預防針,哈哈哈,好啦!其實沒什麼,只是這次用暴力破解法來處理掉,也就是說如果沒有提前判斷到重複,或結果是True的話,最多必須判斷...27次,然後迴圈會跑(9*9)+3次,時間複雜度應該是O(n²),因為我跑了9行裡面又跑了9列,其實我也很不會算/images/emoticon/emoticon16.gif,所以這次來拋磚引玉,偶爾也讓我任性一下XD,以下是解法:

var isValidSudoku = function(board) {
    //首先比較每個陣列中的內容有沒有重複的
    for(let i=0;i<=8;i++){
        //把每一列列出來
        let arrTemp = board[i];
        //判斷重複值,如果有重複就直接回傳false
        if (!checkRepeat(arrTemp))
            return false;
        
        //這邊取每一行的值取出來
        arrTemp = [];
        for(let j=0;j<=8;j++){
            //把值放進陣列中
            arrTemp.push(board[j][i]);
            
            //這邊另外寫一個判斷,因為九宮格是3*3的,所以判斷每三行跑一次
            if((i%3) == 0 && (j%3) == 0){
                //宣告新的arrTemp
                let arrTemp = [];
                //用迴圈取目前行開始三行的位置
                for(let k=i;k<(i+3);k++){
                    //把用slice抓到的三個值合併到arrTemp陣列中
                    arrTemp = arrTemp.concat(board[k].slice(j,j+3))
                }
                //判斷重複值,如果有重複就直接回傳false
                if(!checkRepeat(arrTemp))
                    return false;
            }
        }
        //判斷重複值,如果有重複就直接回傳false
        if (!checkRepeat(arrTemp))
            return false;
        
    }
    
    return true;
    
    /**判斷陣列中有沒有重複的值
    這個function是參考網路上寫出來的,會把出處連結放在文章結尾,
    覺得用這個方式還滿聰明的,大家可以看一下**/
    function checkRepeat(arrTemp){
        //把陣列內容輸出成字串
        var arrStr = JSON.stringify(arrTemp),str;
        //跑所有陣列的值
        for (let i=0; i<arrTemp.length;i++) {
            //這邊是我加的,因為.一定會重複,所以就不判斷.了
            if(arrTemp[i]=='.')
                continue;
            /*精華在這裡,
            用目前要判斷的值去找在字串中第一次出現的位置和最後一次出現的位置,
            如果有一樣就代表沒重複,不同就代表有重複,所以回傳False*/
            if (arrStr.indexOf(arrTemp[i]) != arrStr.lastIndexOf(arrTemp[i])){
                return false;
            }
        };
        //全部跑完沒有回傳false就代表沒重複,所以在最後回傳True
        return true;
    }
};

好的,其實一直以來程式類的題目效能都滿穩定的,可是這次我測出來特別飄XD,差不多在5X%到8X%,不曉得網路會不會有影響,哈哈哈哈,以下是成績:
https://ithelp.ithome.com.tw/upload/images/20180707/20106935HzhHJCqBAs.jpg
再來分享一個用物件來解的方式,這在討論區上的標題註明了擊敗了100%的答案XD,讓我們來看看這位大神怎麼做:
原解答位置

var isValidSudoku = function(board) {
    //首先跑每一列的迴圈
    for(let i=0; i<9; i++){
        /*宣告兩個物件,objH是列,objV是行,
        用來紀錄出現過的值*/
    	let objH={}, objV={}
        //跑每一行的迴圈
    	for(let j=0; j<9; j++){
            //把目前位置的值放進cur1及cur2中
    		let cur1 = board[i][j], cur2 = board[j][i];
            /*判斷是不是.,如果是有數字的話,
            就去判斷先前有沒有出現過這個數字,如果沒出現就把它記錄下來,
            這樣如果接下來有相同數字,就會有值,會直接回傳false*/
    		if(cur1!=='.'){
    			if(objH[cur1]) return false;
    			objH[cur1]=1;
    		}
            //行的也像列一樣做判斷處理
    		if(cur2!=='.'){
    			if(objV[cur2]) return false;
    			objV[cur2]=1;
    		}
    	}
    }
    //判斷完行和列,接著再來判斷九宮格的部分
    for(let i=0; i<9; i++){
        /*宣告用來紀錄值的物件obj,以及用來判斷行和列位置的m1和m2,
        m1會是000333666 m2是036036036,m1是行、m2是列,
        所以每列(m1)會跑三次,每次會都從(m2)第0行取到第2行、3取到6、6再取到8,
        跑完m1在直接跳到位置三第四行,繼續跑迴圈,
        由上而下、由左至右的跑每個九宮格。*/
    	let obj={}, m1=Math.floor(i/3)*3, m2=(i%3)*3;
    	for(let j=0; j<3; j++){
    		for(let k=0; k<3; k++){
                //用迴圈取九宮格的數字,並把目前的數字放進cur中
    			let cur = board[m1+j][m2+k];
                /*判斷是不是.,如果是有數字的話,
                就去判斷先前有沒有出現過這個數字,如果沒出現就把它記錄下來,
                這樣如果接下來有相同數字,就會有值,會直接回傳false*/
    			if(cur!=='.'){
    				if(obj[cur]) return false;
    				obj[cur]=1;
    			}
    		}
    	}
    }
    //全部跑完如果都沒回傳false代表是正確的題目,所以最後回傳true
    return true;
};

以上的m1=Math.floor(i/3)*3, m2=(i%3)*3;真的有點難解釋,不過如果試著用console.log把值給印出來就可以很明白的知道整個邏輯。如果以上有解釋錯誤或不清楚的地方,都可以在下方留言告訴我,我會再想想怎麼改會比較好,也歡迎各位大大提出自己的看法,我都會認真去看每個留言的!那這個禮拜的分享先到這邊(不知道為什麼這次的結尾非常詞窮XD),就謝謝大家觀賞/images/emoticon/emoticon41.gif

參考文章:
JavaScript判斷陣列重複內容的兩種方法(推)


圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中
2
小魚
iT邦大師 1 級 ‧ 2018-07-07 18:02:28

原來...放暑假了喔...
/images/emoticon/emoticon04.gif
好像缺席幾次了,
繼續缺席中...
不過這次是數獨啊...
最近有想寫個數獨的小遊戲...
我倒是覺得題目比較難出...

看更多先前的回應...收起先前的回應...
小魚 iT邦大師 1 級 ‧ 2018-07-08 10:59:17 檢舉

終於完成一關了
https://ithelp.ithome.com.tw/upload/images/20180708/20105694jzNgTtA28k.jpg
不過用最笨的方法來判斷其實也蠻快的,
畢竟資料量很少...

神Q超人 iT邦研究生 5 級 ‧ 2018-07-08 13:10:12 檢舉

大大好猛哦!!!
其實我也想過做一個關於數獨的小遊戲,
可是出題目真的太難XD
目前只想到把一些題目放進資料庫,
讀取出來後再隨機清掉數字而已,哈哈!

小魚 iT邦大師 1 級 ‧ 2018-07-08 19:54:12 檢舉

出題目真的很難,
而且又不是靠這個賺錢的,
不用那麼認真,
所以我是去買一本數獨的書,
直接把題目跟答案打進去...

神Q超人 iT邦研究生 5 級 ‧ 2018-07-09 17:06:22 檢舉

怎麼會突然想做這個遊戲,哈哈XD

小魚 iT邦大師 1 級 ‧ 2018-07-15 10:53:23 檢舉

終於更新到我的個人網站了,
在作品集那邊,
歡迎來看看。

小魚的個人網站

神Q超人 iT邦研究生 5 級 ‧ 2018-08-20 10:26:11 檢舉

小魚大大已經做了不少作品了耶!

小魚 iT邦大師 1 級 ‧ 2018-08-20 11:56:36 檢舉

還好啦, 以現在的標準來看都還不大行...

2
小魚
iT邦大師 1 級 ‧ 2018-07-08 20:01:16

我的是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;
        }

神Q超人 iT邦研究生 5 級 ‧ 2018-07-09 17:05:52 檢舉

我晚點試試看,
看能不能也有個分數出來!
感謝大大分享C#解法XD!

神Q超人 iT邦研究生 5 級 ‧ 2018-07-13 21:21:33 檢舉

小魚大大抱歉我盡力了/images/emoticon/emoticon20.gif
我無法把它無痛修改成可出成績的程式碼,嗚嗚,
每次都越改越歪,整個都變成我的形狀了XD
接下來的SQL就簡單處理了,哈哈哈!

小魚 iT邦大師 1 級 ‧ 2018-07-13 21:42:53 檢舉

沒關係啦,
沒分數就算了...
辛苦你了~

2
小碼農米爾
iT邦高手 1 級 ‧ 2018-07-10 15:45:00

出差五天,與世隔絕,終於回來了
/images/emoticon/emoticon37.gif

這次用 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

https://ithelp.ithome.com.tw/upload/images/20180710/20106865UYh7N56ek6.jpg


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

https://ithelp.ithome.com.tw/upload/images/20180710/20106865fVrNuCtoya.jpg


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

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

話說原來 ² 可以打的出來,一直以為數學公式才有。
/images/emoticon/emoticon37.gif

神Q超人 iT邦研究生 5 級 ‧ 2018-07-12 09:55:01 檢舉

出差五天也太久了,是出國嗎XD
哇,大大已經完全進入python的世界了嗎/images/emoticon/emoticon42.gif
要判斷3*3的小格子str(i//3*3 + j//3) + "=" + value應該都是大家卡最久的地方,哈哈哈!
把經過的數字放進物件裡用in判斷,看起來簡潔很多!
下一次SQL後我也要繼續用Python/images/emoticon/emoticon37.gif

在國內而已,不過出差的地方沒有網路。
/images/emoticon/emoticon02.gif

想多練練 Python,期待這周的題目,哈哈哈。

1
Kevin
iT邦新手 1 級 ‧ 2018-07-11 00:02:07

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

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;
				}
			}
		}
	}

};

https://ithelp.ithome.com.tw/upload/images/20180711/20110564UmQOB01dqJ.png
這圖似乎沒參考價值......

神Q超人 iT邦研究生 5 級 ‧ 2018-07-12 10:36:05 檢舉

沒關係啦XD,還是可以在發一篇詳細解說一下啊!
原諒我看不太懂C++,
因為之前工作的關係對他有一點陰影,嗚嗚/images/emoticon/emoticon20.gif
不過C++真的跑得很快,
JavaScript目前最快的答案也必須要76ms/images/emoticon/emoticon04.gif

小魚 iT邦大師 1 級 ‧ 2018-08-20 11:58:33 檢舉

C++沒那麼難啦...
我是從C++(應該是VB)開始學的,
只是很多事情都要自己做而已,
不像C#很多東西都幫你做好了,
不過現在C++也有很多方便的工具了...

我要留言

立即登入留言