เชี่ยวชาญ N-Queens Challenge ใน Ruby: วิธีแก้แบบขั้นตอน

N-Queens เป็น coding challenge น่าสนใจ ที่คุณต้องวาง N queens บน N * N board

长这样:

Queen เคลื่อนที่ได้ทุกทิศทาง:

• Vertical
• Horizontal
• Diagonal

Solution (อาจมีหลาย) ต้อง วาง queens ทั้งหมดบน board และทุก queen ต้องอยู่นอกขอบเขตของ queen อื่นทุกตัว

ในบทความนี้ คุณจะเรียนรู้วิธีที่ผมหา solution

The Plan

ตอนแก้ challenges แบบนี้ จุดเริ่มที่ดีคือเขียนแผนเป็น plain English

ช่วยให้คุณ clear เกี่ยวกับปัญหาและ steps แก้ไข

หากยากในการเขียนแผน ตรวจสอบให้แน่ใจว่าเข้าใจปัญหา 100%

แผนของผมสำหรับ N-Queens solution:

• Start @ position 0,0
• if valid position: put queen, advance column (+ 1), set row to 0
  • check top, bottom, left, right, diagonal
• else: advance 1 square
  • go up (row + 1) unless current position == n
  • backtrack when queen can't be placed in current column
    • remove last queen
    • set row และ column ไปที่ last queen's position with row + 1

นี่คือ version clean ของสิ่งที่ผมเขียนไว้ต้นๆ

ผมเจาะลึกลงใน steps ที่ต้องการรายละเอียดมากกว่าก่อน implement

ตอนนี้:

แผนของคุณไม่ต้อง perfect (ของผมก็ไม่) แตให้ idea ของสิ่งที่ต้องทำ

หากเขียนแผนไม่ได้ ไม่มีปัญหา lookup solution…

…เข้าใจ solution ทำงานอย่างไร แล้วเขียนของตัวเอง

Finding Valid Moves

เพื่อเช็คว่า position valid ต้อง看หลายทิศทาง

แทนที่จะ mess around กับ 2D board ผมตัดสินใจมี array of queens บน board พร้อม positions

จากนั้นเช็ค array นี้กับ position ที่อยาก validate

เช่น สำหรับ row check:

def queen_in_row(row)
  @queens_in_board.find { |r, c| r == row }
end

จะคืน queen หาก row ถูกครอง หรือ nil หากไม่

คุณไม่ต้องเช็ค column เพราะ เราไป column ถัดไปหลังวาง queen

สำหรับ diagonals ใช้งานเพิ่มเติมเพราะมี 4 ทิศทาง

โค้ดสำหรับ right upper diagonal:

def right_upper_diagonal_for(row, column, n)
  diagonals = []
  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end
  diagonals
end

Diagonals อื่นๆ เหมือนกัน แตกต่างแค่ conditions ของ loop และทิศทาง (row + 1 / row - 1)

ใช้ trial & error นิดหน่อย แต่ ok

สำคัญที่จะ test เมธอดเหล่านี้แยกต่างหากให้แน่ใจว่าทำงาน เมื่อมี working methods set คุณรวมพวกมันเป็น complete solution

นี่คือเมธอดรวม diagonals ทั้งหมดและเช็คกับทุก queen บน board:

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

วิธี Implement BackTracking

การแก้ challenges non-trivial ต้องการ key insight, technique หรือ algorithm

ในกรณี N-Queens technique คือ backtracking

Backtracking คือการ undo previous action (เช่น วาง queen บน board) และลองใหม่กับ configuration ต่างออกไป

ผมคิดว่าส่วนนี้ยากที่สุด แตกลับง่าย

เพื่อ figure out ผมรัน simulation นิดหน่อย

ผมวาด board และ กล่อง represent queens:

จากนั้นแค่ย้ายกล่องรอบ board (โดย mouse โดยตรง) เพื่อ simulate algorithm

โค้ด:

while row >= n
  row = @queens_in_board[-1][0] + 1
  column = @queens_in_board[-1][1]
  puts "Backtracking, deleted: #{@queens_in_board.pop}"
end

คุณทำได้สำหรับปัญหาอื่นๆ เมื่อ stuck วาดบน drawing program หรือกระดาษ และเล่นดู

นี่คือ essence ของการทำงาน:

• เราไปขึ้นเรื่อยๆ หากถึง top of board หมายถึงวาง queen บน column นี้ไม่ได้
• เรา backtrack โดยตั้ง current position ไปที่ last queen และ remove มันจาก board
• หากวาง queen จาก position นี้ไม่ได้ เรา backtrack อีก

+ 1 บน row position คือวิธี เรา advance last queen เพื่อ reposition และเปิด board configurations ใหม่

เมื่อรันโค้ดสำหรับ n = 4 (ไม่มี solutions สำหรับ n = 2 และ n = 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

Alternative version ที่หา ALL possible solutions

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

สิ่งที่เปลี่ยนแค่เมธอด solve_n_queens

Version นี้ใช้ recursion (เมธอดที่เรียกตัวเอง) เพื่อ explore all partial solutions

เมื่อเจอ complete solution เรา print ด้วย print_board

สรุป

คุณเรียนรู้ N-Queens coding challenge และวิธีแก้ใน Ruby คุณยังเรียนรู้วิธีปรับปรุงทักษะ problem-solving

หากชอบบทความนี้แชร์ให้คนที่ได้ประโยชน์

ขอบคุณที่อ่าน!