js 爬山演算法解八皇后

 

一開始有皇后狀態
每一個皇后都移動除了自己目前格子以外 y 的上或下, 所以整個棋盤共有 8 * 2 = 16 個 successor
也可以除了自己之外的 7 格 8 * 7 = 56 個 successor
至少要跑 20 皇后 30 秒內要找到解答, 最好狀況不管 N 皇后能 30 秒內找到解答

虛擬碼

while (true) {
    //皇后移動上或下衝突數最少者
    NEXT = highest-valued successor of CURRENT
    if score(CURRENT) better than score(NEXT) then
        return CURRENT
    else 
        CURRENT = NEXT
}

let ans = hillClimbingEightQueens(8)
console.log(ans.join(' '))


function hillClimbingEightQueens(numOfQueen) {
    let current = initialState(numOfQueen)
    console.log('初始狀態', current)

    while (true) {
        let emptyBoard = initEmptyBoard(current.length)
        let queens = getQueens(current)
        let board = fillQueen(emptyBoard, current)
        let score = calcResult(board, queens)
        console.log('目前分數')
        console.log(score)

        let scores = calcScores(current)
        //取得下一個棋盤 (找衝突最少的)
        const next = scores.reduce((a, b) => a.total < b.total ? a : b);
        console.log('下個最佳分數')
        console.log(next)

        // 如果找到解
        if (next.total === 0) {
            console.log('找到最佳解')
            return next.simple
        }

        // 如果沒有比 current 更好 (卡在 local optima)
        if (next.total >= score.total) {
            console.log('陷入 local optima 重啟')
            current = initialState(numOfQueen)
            // return current
        } else {
            current = next.simple
        }

    }


    // 一開始有皇后狀態
    // 每一個皇后都移動除了自己目前格子以外 y 的上或下, 所以整個棋盤共有 8 * 2 = 16 個 successor
    // 也可以除了自己之外的 7 格 8 * 7 = 56 個 successor
    // 至少要跑 20 皇后 30 秒內要找到解答, 最好不管 N 皇后能 30 秒內找到解答

    // while (true) {
    //     皇后移動上或下衝突數最少者
    //     NEXT = highest-valued successor of CURRENT
    //     if score(CURRENT) better than score(NEXT) then
    //         return CURRENT
    //     else 
    //         CURRENT = NEXT
    // }
}

//把待候選名單的分數計算出來
function calcScores(current) {
    //待計算的候選人
    let arr = candidates(current)
    // console.log(arr)
    let scores = []
    for (let item of arr) {
        let emptyBoard = initEmptyBoard(current.length)
        let queens = getQueens(item)
        let board = fillQueen(emptyBoard, item)
        let score = calcResult(board, queens)
        scores.push(score)
    }
    return scores
}

//待計算的候選名單
function candidates(current) {
    let result = []
    for (let x = 0; x < current.length; x++) {
        for (let y = 0; y < current.length; y++) {
            //複製 instance
            let newArr = [...current]
            //取得目前的皇后
            let queen = newArr[x]
            if (queen === y) continue
            else {
                newArr[x] = y
                result.push(newArr)
            }
        }
    }
    return result
}


//亂數建立皇后在棋盤位置的 array
function initialState(num) {
    let result = []
    for (let i = 0; i < num; i++) {
        let pos = Math.floor(Math.random() * num);
        result.push(pos);
    }
    return result

    //上次因為是輸入皇后 string 所以需要有這串, 這次自己 random 決定位置所以這段免了
    //.join(' ').split(' ').map(x => parseInt(x))
}


/** 計算結果*/
function calcResult(board, queens) {
    let result = []
    let total = 0
    for (let i = 0; i < queens.length; i++) {
        let queen = queens[i]
        let count = scan(queen, board)
        result.push({ x: queen.x, y: queen.y, count: count })
        // console.log(`queen:(${queen.x},${queen.y})-${count}次`)
        total += count
    }

    // console.log(`共:${total}次`)

    return { 'board': result, 'total': total, 'simple': result.map(item => item.y) }

    // return total
}

/**印出棋盤 */
function printBoard(board) {
    for (let y = 0; y < board.length; y++) {
        let str = ''
        for (let x = 0; x < board.length; x++) {
            str += board[y][x] + ' '
        }
        console.log(str)
    }
}


/**組合所有掃描的函數 */
function scan(queen, board) {
    let count = 0
    count += scanRow(queen, board)

    //左上至右下
    count += scanToTopLeft(queen, board)
    count += scanToBottomRight(queen, board)

    //右上至左下
    count += scanToTopRight(queen, board)
    count += scanToBottomLeft(queen, board)

    return count
}

/**掃描目前棋子到左下 */
function scanToBottomLeft(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x -= 1
    y += 1

    while (true) {
        if (x < 0 || y >= board.length) break
        if (board[y][x] === 'Q') count++
        x -= 1
        y += 1
    }
    return count
}

/**掃描目前棋子到右上 */
function scanToTopRight(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x += 1
    y -= 1

    while (true) {
        if (x >= board.length || y < 0) break
        if (board[y][x] === 'Q') count++
        x += 1
        y -= 1
    }
    return count
}

/**掃描目前棋子到左上 */
function scanToTopLeft(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x -= 1
    y -= 1

    while (true) {
        if (x < 0 || y < 0) break
        if (board[y][x] === 'Q') count++
        x -= 1
        y -= 1
    }
    return count
}


/**掃描目前棋子到右下 */
function scanToBottomRight(queen, board) {
    let y = queen.y
    let x = queen.x
    let count = 0
    x += 1
    y += 1

    while (true) {
        if (x >= board.length || y >= board.length) break
        if (board[y][x] === 'Q') count++
        x += 1
        y += 1
    }
    return count
}

/**掃描整個橫向 */
function scanRow(queen, board) {
    let num = board.length
    let y = queen.y
    let count = 0
    for (let x = 0; x < num; x++) {
        if (x === queen.x) continue
        if (board[y][x] === 'Q') count++
    }
    return count
}

/**簡化取得皇后 xy 位置 */
function getQueens(initQueenPos) {
    let queens = []
    for (let i = 0; i < initQueenPos.length; i++) {
        let queen = { x: i, y: initQueenPos[i] }
        queens.push(queen)
    }
    return queens
}

/**建立棋盤 */
function initEmptyBoard(num) {
    let board = []
    for (let y = 0; y < num; y++) {
        board.push([])
        for (let x = 0; x < num; x++) {
            board[y].push('X')
        }
    }
    return board
}

/**填滿皇后 */
function fillQueen(board, initQueenPos) {
    for (let i = 0; i < initQueenPos.length; i++) {
        //取得皇后位置
        let queen = initQueenPos[i]
        //填入皇后
        board[queen][i] = 'Q'
    }
    return board
}