N-Queens là coding challenge thú vị: đặt N quân hậu trên bàn cờ N * N.
Trông như:
Quân hậu di chuyển mọi hướng:
- Vertical
- Horizontal
- Diagonal
Giải pháp (có nhiều) phải đặt tất cả quân hậu lên bàn cờ & mỗi hậu ngoài tầm tất cả hậu khác.
Bài này bạn học cách tôi ra giải pháp.
Kế hoạch
Khi giải challenge kiểu này, điểm khởi đầu tốt là viết kế hoạch bằng tiếng Anh thuần.
Giúp clear về vấn đề và bước giải.
Nếu khó viết kế hoạch đảm bảo hiểu vấn đề 100%.
Kế hoạch N-Queens của tôi:
- Bắt đầu @ position 0,0
- nếu valid position: đặt hậu, tiến cột (+ 1), set row về 0
- check top, bottom, left, right, diagonal
- ngược lại: tiến 1 ô
- lên (row + 1) trừ khi current position == n
- backtrack khi hậu không đặt được cột hiện tại
- xóa hậu cuối
- set row & column về vị trí hậu cuối + row + 1
Đây version clean của kế hoạch đầu.
Tôi drill down vào bước cần detail hơn trước khi implement.
Bây giờ:
Kế hoạch bạn không hoàn hảo (của tôi cũng không) nhưng cho idea hướng đi.
Nếu không viết kế hoạch solid không sai xem solution…
…hiểu solution chạy thế nào rồi tự viết.
Tìm Valid Move
Check position valid phải nhìn nhiều hướng.
Thay vì loay hoay với bàn cờ 2D, tôi quyết định mảng các hậu trên bàn cờ với vị trí.
Sau đó check mảng hậu này với position muốn validate.
Ví dụ, check hàng:
def queen_in_row(row)
@queens_in_board.find { |r, c| r == row }
end
Này trả về hậu nếu hàng bị chiếm, nil nếu không.
Bạn không check cột vì chúng ta sang cột sau khi đặt hậu.
Đối với diagonal cần thêm việc vì có 4 diagonal.
Code diagonal trên phải:
def right_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == n
diagonals << [row += 1, column += 1]
end
diagonals
end
Các diagonal khác tương tự, khác chỉ điều kiện loop và hướng (row + 1 / row - 1).
Tốn chút trial & error để đúng, nhưng ok.
Quan trọng test các method riêng lẻ đảm bảo chạy. Khi có set method chạy, gộp thành solution hoàn chỉnh.
Method gộp tất cả diagonal & check với mọi hậu trên bàn cờ:
def queen_in_diagonal(row, column, n)
diagonals = right_upper_diagonal_for(row, column, n) +
left_upper_diagonal_for(row, column, n) +
left_lower_diagonal_for(row, column, n) +
right_lower_diagonal_for(row, column, n)
diagonals.any? { |r, c| r == row && c == column } ||
diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end
Cách implement BackTracking
Giải challenge non-trivial cần key insight, technique hoặc algorithm.
Với N-Queens kỹ thuật là backtracking.
Backtracking là undo hành động trước (như đặt hậu) và thử lại config khác.
Tôi nghĩ đây phần khó, nhưng ra khá dễ.
Để hiểu, tôi chạy simulation nhỏ.
Tôi vẽ bàn cờ & box đại diện hậu:
Rồi di chuyển box quanh bàn cờ (chuột) simulate algorithm.
Code:
while row >= n
row = @queens_in_board[-1][0] + 1
column = @queens_in_board[-1][1]
puts "Backtracking, deleted: #{@queens_in_board.pop}"
end
Bạn cũng làm vậy cho bài khác khi stuck, vẽ trên paper hoặc drawing program và chơi.
Bản chất cách này chạy:
- Tiếp tục lên, nếu đỉnh bàn cờ nghĩa là không fit hậu cột này
- Backtrack: set current position về hậu cuối & xóa khỏi bàn cờ
- Nếu không đặt được từ position này, backtrack lại
+ 1 trên row position là cách chúng ta tiến hậu cuối reposition & mở config bàn cờ mới.
Chạy code n = 4 (không solution n = 2 & 3):
"placing at 0 0" "placing at 2 1" Backtracking, deleted: [2, 1] "placing at 3 1" "placing at 1 2" Backtracking, deleted: [1, 2] Backtracking, deleted: [3, 1] Backtracking, deleted: [0, 0] "placing at 1 0" "placing at 3 1" "placing at 0 2" "placing at 2 3"
GIF visual example algorithm:
Full Code
def solve_n_queens(n)
@queens_in_board = []
row = 0
column = 0
until @queens_in_board.size == n
if queen_in_row(row) || queen_in_diagonal(row, column, n)
row += 1
while row >= n
row = @queens_in_board[-1][0] + 1
column = @queens_in_board[-1][1]
puts "Backtracking, deleted: #{@queens_in_board.pop}"
end
else
place_queen(row, column)
p "placing at #{row} #{column}"
row = 0
column += 1
end
end
@queens_in_board
end
def queen_in_row(row)
@queens_in_board.find { |r, c| r == row }
end
def queen_in_diagonal(row, column, n)
diagonals = right_upper_diagonal_for(row, column, n) +
left_upper_diagonal_for(row, column, n) +
left_lower_diagonal_for(row, column, n) +
right_lower_diagonal_for(row, column, n)
diagonals.any? { |r, c| r == row && c == column } ||
diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end
def top_row?(row, n)
row == n
end
def place_queen(row, column)
@queens_in_board << [row, column]
end
def right_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == n
diagonals << [row += 1, column += 1]
end
diagonals
end
def left_upper_diagonal_for(row, column, n)
diagonals = []
until row == n || column == 0
diagonals << [row += 1, column -= 1]
end
diagonals
end
def right_lower_diagonal_for(row, column, n)
diagonals = []
until row == 0 || column == n
diagonals << [row -= 1, column += 1]
end
diagonals
end
def left_lower_diagonal_for(row, column, n)
diagonals = []
until row == 0 || column == 0
diagonals << [row -= 1, column -= 1]
end
diagonals
end
def print_board(n)
board = Array.new(n) { Array.new(n) { "." } }
@queens_in_board.each { |queen| board[queen[0]][queen[1]] = "Q" }
board.map { |n| n.join("|") }.reverse
end
p solve_n_queens(4)
p solve_n_queens(5)
puts print_board(5)
Recursive Version
Phiên bản alternative tìm TẤT CẢ solution.
def solve_n_queens(n, column = 0, queens_in_board = [])
@queens_in_board = queens_in_board
n.times do |row|
unless queen_in_row(row) || queen_in_diagonal(row, column, n)
place_queen(row, column)
solve_n_queens(n, column + 1, @queens_in_board)
remove_last_queen
end
end
puts print_board(n) if @queens_in_board.size == n
end
Chỉ method solve_n_queens đổi.
Version này dùng recursion (method gọi chính nó) explore tất cả partial solution.
Khi tìm complete solution, in dùng print_board.
Tóm tắt
Bạn đã học về N-Queens coding challenge & cách giải Ruby. Cũng học cải thiện problem-solving skill.
Nếu thích bài viết hãy chia sẻ cho aiได้ benefit.
Cảm ơn đã đọc!