5

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

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"]
]
``````

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"]
]
``````

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

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

### 4 則留言

2

iT邦大師 1 級 ‧ 2018-07-07 18:02:28

2

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

``````        /// <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++)
{
}
for(int i=0;i<num;i++)
{
List<List<int>> list = new List<List<int>>();
for(int j=0;j<num;j++)
}

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

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

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

``````

2

``````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
``````

`=FLOOR.MATH(\$A2/3)*3+FLOOR.MATH(B\$1/3)`

checkRepeat 內繞 arrTemp 的迴圈也算 n，

1
Kevin
iT邦新手 4 級 ‧ 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;
}
}
}
}

};
``````

JavaScript目前最快的答案也必須要76ms

C++沒那麼難啦...