.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Determine if a 9 x 9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:
1.
Each row must contain the digits 1-9 without repetition.
2.
Each column must contain the digits 1-9 without repetition.
3.
Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without repetition.
Note:
•
A Sudoku board (partially filled) could be valid but is not necessarily solvable.
•
Only the filled cells need to be validated according to the mentioned rules.
Example 1:
Input: board =
[["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"]]
Output: true
Plain Text
복사
Example 2:
Input: board =
[["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"]]
Output: false
Explanation: Same as Example 1, except with the5 in the top left corner being modified to8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.
Plain Text
복사
Constraints:
•
board.length == 9
•
board[i].length == 9
•
board[i][j] is a digit 1-9 or '.'.
My solution
9x9 스도쿠 보드가 유효한지 확인합니다.
채워진 셀들은 아래의 규칙에 따라 유효성 검사를 합니다.
1.
각 행에는 반복되지 않는 1~9가 있어야 합니다.
2.
각 열에는 반복되지 않는 1~9가 있어야 합니다.
3.
그리드의 3x3 sub-box가 9개 있고 각각에 반복되지 않는 1~9가 있어야 한다.
Note.
•
스도쿠 보드(부분적으로 채워진)는 유효할 수 있지만 반드시 풀린 것은 아니다.
•
표시된 규칙에 따라 채워진 셀만 검증하면 된다.
1.
0,0의 5를 검사하기 위해서 0,0에서 0, 8까지 행을 따라 쭉 확인하고, 0,0에서 8,0까지 열을 따라 쭉 확인할 수 있다.
2.
그다음 0,0이 포함된 sub-box인 3x3 그리드를 확인하기 위해 0,0 ~ 2,2를 전부 확인해서 5가 있는지 확인해야 한다.
1은 for문에서 조작하기 나름 쉬운 편이다.
// check row
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] !== '.') {
for (let k = j + 1; k < 9; k++) {
if (board[i][j] === board[i][k]) {
return false;
}
}
}
}
}
// check column
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[j][i] !== '.') {
for (let k = j + 1; k < 9; k++) {
if (board[j][i] === board[k][i]) {
return false;
}
}
}
}
}
JavaScript
복사
2번을 확인하기 위한 방법은 조금 고민해볼 필요가 있다.
하드코딩한다면 어렵지는 않겠지만 이건 설계하기도 어렵고 가독성이 떨어질 것이다.
이를 확인하기 위해 이차원 Hashmap을 사용한다. 객체 하나를 선언하고 box 9개를 0 ~ 8이라는 프로퍼티로 나타낸다.
1.
각 박스 프로퍼티 값은 역시 객체인데, 그 객체의 프로퍼티는 number(1 ~ 9)를 의미한다. 입력으로 주어진 숫자를 프로퍼티로 true 값을 세팅해두면 for문을 돌면서 box를 방문했을 때 숫자가 존재하는지 체크할 수 있다.(ealry return)
subBox로 (0,0) ~ (8,8)까지의 좌표를 Math.floor(i / 3) * 3 + Math.floor(j / 3) 로 처리하면 몇번째 박스에 속하는지 판별할 수 있다.
(0, 0) ⇒ 0
(0, 1) ⇒ 0
,,,
(0, 3) ⇒ 1
(0, 6) ⇒ 2
,,,
(3, 0) ⇒ 3
(3, 1) ⇒ 3
,,,
(3, 3) ⇒ 4
(3, 4) ⇒ 4
,,,
(3, 6) ⇒ 5
,,,
(6, 0) ⇒ 6
,,,
(6, 3) ⇒ 7
,,,
(6, 6) ⇒ 8
,,,
(8, 8) ⇒ 8
Math.floor()
함수는 주어진 숫자와 같거나 작은 정수 중에서 가장 큰 수를 반환합니다.
2.
처음 방문하는 box면 객체가 세팅되어 있지 않으니 빈 객체를 할당해주는 로직도 추가한다.
3.
위 로직을 수행한 뒤 false를 리턴하지 않았다면 그 숫자를 box의 number에 true로 할당해준다.
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] !== '.') {
// get the sub-box number
const subBox = Math.floor(i / 3) * 3 + Math.floor(j / 3);
// check if the number is already in the sub-box
if (subBoxes[subBox] && subBoxes[subBox][board[i][j]]) {
return false;
}
// add the number to the sub-box
if (!subBoxes[subBox]) {
subBoxes[subBox] = {};
}
subBoxes[subBox][board[i][j]] = true;
console.log(subBoxes);
}
}
}
JavaScript
복사
Code
/**
* @param {character[][]} board
* @return {boolean}
*/
const isValidSudoku = function (board) {
// check row
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] !== '.') {
for (let k = j + 1; k < 9; k++) {
if (board[i][j] === board[i][k]) {
return false;
}
}
}
}
}
// check column
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[j][i] !== '.') {
for (let k = j + 1; k < 9; k++) {
if (board[j][i] === board[k][i]) {
return false;
}
}
}
}
}
// check 3x3 sub-boxes using a hashmap
const subBoxes = {};
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
if (board[i][j] !== '.') {
// get the sub-box number
const subBox = Math.floor(i / 3) * 3 + Math.floor(j / 3);
// check if the number is already in the sub-box
if (subBoxes[subBox] && subBoxes[subBox][board[i][j]]) {
return false;
}
// add the number to the sub-box
if (!subBoxes[subBox]) {
subBoxes[subBox] = {};
}
subBoxes[subBox][board[i][j]] = true;
console.log(subBoxes);
}
}
}
return true;
};
describe('isValidSudoku', () => {
it('TC1', () => {
expect(
isValidSudoku([
['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'],
])
).toStrictEqual(true);
});
// it('TC2', () => {
// expect(
// isValidSudoku([
// ['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'],
// ])
// ).toStrictEqual(false);
// });
});
JavaScript
복사
