[TIL] 2021.03.16

👩🏻‍💻 오늘 공부한 내용

접근수준 ( https://yagom.net/ )

• 높은 접근 수준 open > public > internal > fileprivate > private 낮은 접근수준
• 상속을 가능하게 하려면 open 그렇지 않으면 public

스도쿠

스도쿠 빈칸 생성

private func generateSudoku(){
    var zeroNum = Int(arc4random_uniform(5) + 1)
    // level에 따라 빈칸 갯수 정의
    if level == 1{
        zeroNum += 35
    } else if level == 2{
        zeroNum += 40
    } else {
        zeroNum += 45
    }

    game_sudoku = original_sudoku
    
    var x = 0
    while zeroNum > 0{
        let num = Int(arc4random_uniform(5)) // 한 줄에 생성할 빈칸 갯수
        
        for _ in 0...num { 
            let y = Int(arc4random_uniform(9))
            
            if game_sudoku[x][y] != 0 {
                game_sudoku[x][y] = 0
                zeroNum -= 1
            }
        }
        
        if x == 8{
            x = 0
        }else {
            x += 1
        }
    }
}

스도쿠 유일성 ( 참고 사이트 )

• backtracking 사용
• 빈칸에 가능한 숫자를 일일이 집어넣고 규칙에 어긋나면 다시 돌아와 다른 숫자를 집어넣는 방식

// 유일성 체크
private func uniqueSudoku()-> Int{
    var check_row: [[Bool]] = []
    var check_col: [[Bool]] = []
    var check_square: [[Bool]] = []
    let boolArr: [Bool] = [false, false, false, false, false, false, false, false, false]
    
    for _ in 0...8{
        check_row.append(boolArr)
        check_col.append(boolArr)
        check_square.append(boolArr)
    }
    
    var count = 0
    
    func solveSudoku(_ x : Int, _ y : Int){
        if count > 1 {
            return
        }
        if(x == 8 && y == 8) {
            count += 1
            return
        }
        
        if(game_sudoku[x][y] != 0){ // 빈칸이 아니면 
            if y < 8{
                solveSudoku(x, y+1)
            }else {
                solveSudoku(x+1, 0)
            }
            
        } else { // 빈칸이면 
            for i in 0...8{
                if(!check_row[x][i] && !check_col[y][i] && !check_square[(x/3) * 3 + (y/3)][i]){
                    
                    check_row[x][i] = true
                    check_col[y][i] = true
                    check_square[(x/3) * 3 + (y/3)][i] = true
                    game_sudoku[x][y] = i + 1
                    
                    if y < 8{
                        solveSudoku(x, y+1)
                    }else {
                        solveSudoku(x+1, 0)
                    }
                    
                    check_row[x][i] = false
                    check_col[y][i] = false
                    check_square[(x/3) * 3 + (y/3)][i] = false
                    game_sudoku[x][y] = 0
                }
            }
        }
    }
    
    for i in 0...8{
        for j in 0...8{
            if(game_sudoku[i][j] != 0){
                check_row[i][game_sudoku[i][j]-1] = true
                check_col[j][game_sudoku[i][j]-1] = true
                check_square[(i/3) * 3 + (j/3)][game_sudoku[i][j]-1] = true
            }
        }
    }
    
    solveSudoku(0,0)
    
    return count
}

public func getSudoku(level: Int)->[[[Int]]]{
    self.level = level
    resetSudoku()
    
    while uniqueSudoku() != 1{ 
    	// uniqueSudoku()가 1이 아니면 해가 둘 이상 -> 빈칸 재생성
        generateSudoku()
    }
    
    return [original_sudoku, game_sudoku]
}

✍🏻 오늘은...

스도쿠를 구하는 알고리즘을 활용하여 해가 유일한지 확인하였다. 해가 유일하지 않으면 빈칸을 재생성하는 방법으로 구현하였는데 이런식으로 하다보니 빈칸의 갯수가 많아질수록 시간이 오래걸린다. 빈칸이 45 ~ 50 정도만 되도 조금 버벅이는것 같다. 이런 무식한 방법이 답인건가.. 😭 조금 더 고민해보고 배포해야겠다.