@ N-Queen 문제의 정의
문제야 워낙 유명하니까 위키피디아 링크로 넘기고...
N * N 의 체스판에 Queen 을 N 개 배치한다고 하면 N^2 Combination N 가지의 조합이 나온다.
N이 2,3 일 경우 N-Queen의 해는 없으므로 가장 작은 N은 4인데, N이 4일 때 무려 1820 개의 조합이 나온다.
이 때, 백트래킹을 이용하여 해가 될 수 없는 부분해들을 소거하면서 진행하면 조합 수를 엄청나게 줄일 수 있다.
푸는 방법도 백트래킹을 이용하면 어렵지 않으므로 소스를 참조할 것
(링크를 따라가면 코드 하이라이트 된 소스를 볼 수 있음)
=begin
N-Queen Problem
=end
def place_queen(queen_count)
place(0, queen_count, [])
end
def place(row, queen_count, columns)
if row == queen_count
print_queen_place(queen_count, columns)
return
end
movable_cols = get_movable_places(row, queen_count, columns)
movable_cols.each do |col|
columns[row] = col
place(row + 1, queen_count, columns)
end
end
def get_movable_places(row, queen_count, columns)
places = []
(0...queen_count).each { |i| places[i] = 1 }
(0...row).each do |rowidx|
prev_place = columns[rowidx]
places[prev_place] = 0
oppo_angle_left = prev_place - (row - rowidx).abs
oppo_angle_right = prev_place + (row - rowidx).abs
places[oppo_angle_left] = 0 if oppo_angle_left >= 0
places[oppo_angle_right] = 0 if oppo_angle_right < queen_count
end
movable_cols = []
places.each_index { |i| movable_cols.push i if 1 == places[i] }
movable_cols
end
def print_queen_place(queen_count, columns)
puts "Queen -------------------------------------"
(0...queen_count).each do |i|
(0...queen_count).each do |j|
if j == columns[i]
print 'Q'
else
print '.'
end
end
puts
end
end
place_queen(4)
'Dev.Programming > DS/Algorithm' 카테고리의 다른 글
| 분리 집합 (0) | 2009/05/11 |
|---|---|
| 수식 트리 in Ruby (4) | 2009/05/11 |
| Backtracking : N-Queen Problem (2) | 2009/05/07 |
| Backtracking : 미로 찾기 (0) | 2009/05/07 |
| Divide & Conquer : n 번째 피보나치 수열의 수를 구하기 (2) | 2009/05/06 |
| Divide & Conquer : 거듭제곱 알고리즘 (0) | 2009/05/06 |
