2
8 개의 퀸즈 퍼즐은 8 개의 체스 보드에 8 개의 체스 퀸즈를 놓아 두 왕비가 서로를 위협하지 않도록하는 문제입니다. 따라서 해결책은 2 명의 여왕이 동일한 행, 열 또는 대각선을 공유하지 않아야합니다. 8 개의 퀸즈 퍼즐은 n = 2 또는 n = 3을 제외한 모든 자연수 n에 대한 해가 존재하는 n × n 체스 보드에 n 개의 여왕을 배치하는보다 일반적인 n-queens 문제의 예입니다.8 개의 퀸즈 퍼즐을 풀기위한 빠른 코드는 다음과 같습니다
그러나 아무도 나를 재귀 메서드 동안 무한 루프에 대한이 문제를 해결할 수 있습니까?
ps : 놀이터에 복사하여 붙여 넣기 만하면됩니다. 감사합니다!
class ChessBoard {
var limit: Int
var queens = [Queen]()
init(limit: Int) {
self.limit = limit
}
// Check if (i,j) is a safe position for queen
func isSafeForQueen(atRow row: Int, col: Int) -> Bool {
for q in queens {
// not in same row
if q.row == row { return false }
// not in same column
if q.col == col { return false }
// not in same diagol line
if abs(q.row-row) == abs(q.col-col) { return false }
}
return true
}
// recursive method
func dropQueen(atRow r: Int, c: Int) {
// running into last row
if r == limit {
if queens.count < 8 {
queens.removeLast()
let q = queens.last!
dropQueen(atRow: q.row, c: q.col+1)
}
output() // if success, log out the positions
return
}
// running into last column of current row
if c == limit {
queens.removeLast()
let q = queens.last!
// if no position for queen at current row, then back to last row
dropQueen(atRow: r-1, c: q.col+1)
}
// if this postion is safe for queen, then drop the queen and try next row; if not, try next spot
if isSafeForQueen(atRow: r, col: c) {
let q = Queen(row: r, col: c)
queens.append(q)
dropQueen(atRow: r+1, c: c)
} else {
dropQueen(atRow: r, c: c+1)
}
}
func play() {
dropQueen(atRow: 0, c: 0) // game will start at(0,0)
}
func output() -> String {
var s = ""
for q in queens {
s += "(\(q.row),\(q.col))"
}
return s
}
}
struct Queen {
var row: Int
var col: Int
}
// Tesing：
let b = ChessBoard(limit: 8)
//b.play()
고맙습니다. 당신의 대답을보기 전에 재귀 사용에 대한 많은 경험이 없습니다. 외관상으로는 나는 편익을 위해 재귀를 과용하고 컴퓨터에 모든 무거운 일을두고 성과를 명중했다. 그래서 코드의 핵심 부분을 변경하고 작동합니다. 나는 새로운 코멘트로 나의 코드를 넣을 것이다. 호기심에서 벗어나서 내가 옛날 방식으로 글을 쓰면 더 빨리 달릴 수 있을까? (예를 들어, C에서 사람들은 구조체 또는 클래스에 데이터를 저장하는 대신 여왕 (i, j)을 나타내는 array [i] = j를 사용합니까?) 많은 시간이 걸립니다. –
당신이 듣게되어 좋았지 만 원래 코드보다 훨씬 복잡하다는 사실은 혼란 스럽습니다. 재귀는 일을 더 단순하게 만든다. 당신은 혼자 힘든 길을 만들고 있습니다! 제 코드를 살펴보십시오 (위의 편집 참조). 하나의 간단하고 컴팩트 한 재귀 함수에서 전체 알고리즘. 그리고 이전에 말한 것처럼 : 재귀 알고리즘에서 역 추적을하지 마십시오! 'array'접근법에 관해서는, 네가 반복적으로 객체를 생성하고 처리하는 오버 헤드 (구조체'Queen'의 인스턴스)가 없으므로 약간 더 효율적입니다. –
마스터에게서 배웠습니다! 코딩을 시작할 때, 나는 본능 논리를 따랐을 뿐이다. 문제를 해결하는 방법은 step1, step2 일 수 있고, 코딩 스타일이 정의 된 것 같다. 일이 잘못 될 때마다 나는 그것을 고치려고합니다. 이것은 더 많은 코드를 추가한다는 것을 의미합니다. 대부분의 경우, 코드를 유연하고 재사용하기보다는 프로그램 실행을 우선 순위로 지정하십시오. '적은 수의 코드 줄이 더 낫다'또는 '단순함 ..'이라고 생각할 때마다 나는 더 동의하지 않고 어떻게 여기에서 얻을 수 있는지 모른다. 아마 약간의 코드는 더 많은 사고를 의미합니다. –