แก้ปัญหา N-Queens ด้วย Ruby

N-Queens เป็นความท้าทายในการเขียนโค้ดที่น่าสนใจ โดยคุณจะต้องวาง N Queens ไว้บน N * N board .

ดูเหมือนว่านี้:

ราชินีสามารถเคลื่อนที่ได้ทุกทิศทาง:

• แนวตั้ง
• แนวนอน
• แนวทแยง

วิธีแก้ปัญหา (มีได้หลายอย่าง) ต้อง วางควีนทั้งหมดไว้บนกระดาน &ราชินีทุกตัวต้องอยู่ห่างจากราชินีทุกตัว

ในบทความนี้ คุณจะได้เรียนรู้วิธีที่ฉันคิดวิธีแก้ปัญหา

แผน

เมื่อแก้ปัญหาเหล่านี้ จุดเริ่มต้นที่ดีคือการเขียนแผนเป็นภาษาอังกฤษง่ายๆ

วิธีนี้จะช่วยให้คุณเข้าใจอย่างชัดเจนว่าปัญหาคืออะไรและขั้นตอนในการแก้ไข

หากคุณมีปัญหาในการเขียนแผน โปรดเข้าใจปัญหา 100% .

แผนของฉันสำหรับโซลูชัน N-Queens:

• เริ่มต้น @ ตำแหน่ง 0,0
• ถ้าตำแหน่งถูกต้อง:ใส่ queen, Advance column (+ 1), set row to 0
  • ตรวจสอบ บน ล่าง ซ้าย ขวา เส้นทแยงมุม
• อย่างอื่น:เลื่อนไป 1 ตาราง
  • ขึ้นไป (แถว + 1) เว้นแต่ตำแหน่งปัจจุบัน ==n
  • ย้อนรอยเมื่อไม่สามารถวางราชินีในคอลัมน์ปัจจุบันได้
    • เอาราชินีองค์สุดท้ายออก
    • กำหนดแถวและคอลัมน์เป็นตำแหน่งของควีนสุดท้ายด้วยแถว + 1

นี่เป็นเวอร์ชันที่สะอาดกว่าของสิ่งที่ฉันจดบันทึกไว้ในตอนแรก

ฉันเจาะลึกขั้นตอนที่ต้องใช้รายละเอียดเพิ่มเติมก่อนจึงจะสามารถใช้งานได้

ตอนนี้ :

แผนของคุณจะไม่สมบูรณ์แบบ (ของฉันไม่สมบูรณ์แบบ) แต่จะช่วยให้คุณทราบว่าควรดำเนินการอย่างไร

หากคุณไม่สามารถเขียนแผนงานที่มั่นคง การค้นหาวิธีแก้ปัญหาก็ไม่ใช่เรื่องผิด …

…เข้าใจว่าวิธีแก้ปัญหาทำงานอย่างไร จากนั้นเขียนของคุณเอง

ค้นหาการเคลื่อนไหวที่ถูกต้อง

ในการตรวจสอบว่าตำแหน่งนั้นถูกต้องหรือไม่ เราต้องดูจากหลายๆ ทิศทาง

แทนที่จะยุ่งกับบอร์ด 2 มิติ ฉันตัดสินใจมี ราชินีมากมาย ในกระดานที่มีตำแหน่งของตน

จากนั้นเราจะตรวจสอบราชินีแถวนี้กับตำแหน่งที่เราต้องการตรวจสอบ

ตัวอย่างเช่น สำหรับการตรวจสอบแถว:

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

ค่านี้จะคืนค่าเป็นราชินีถ้ามีคนแถวนั้นหรือไม่มีเลย

คุณไม่จำเป็นต้องตรวจสอบว่าคอลัมน์ว่างหรือไม่เพราะ เราจะย้ายไปยังคอลัมน์ถัดไปหลังจากวางราชินี .

สำหรับเส้นทแยงมุม ต้องใช้ความพยายามเป็นพิเศษเนื่องจากมี 4 เส้น

นี่คือรหัสสำหรับเส้นทแยงมุมบนขวา:

def right_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end

  diagonals
end

เส้นทแยงมุมอื่นๆ เหมือนกัน ความแตกต่างเพียงอย่างเดียวอยู่ในเงื่อนไขของลูป &ทิศทาง (แถว + 1 / แถว - 1)

ต้องใช้การทดลองและข้อผิดพลาดเล็กน้อยจึงจะถูกต้อง แต่ก็ไม่เป็นไร

สิ่งสำคัญคือต้องทดสอบวิธีการเหล่านี้แยกกันเพื่อให้แน่ใจว่าได้ผล . เมื่อคุณมีชุดวิธีการทำงานแล้ว คุณก็นำมารวมกันเพื่อสร้างโซลูชันที่สมบูรณ์ได้

นี่คือวิธีที่ดึงเส้นทแยงมุมทั้งหมดมารวมกันและตรวจสอบกับราชินีทุกตัวในกระดาน:

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

วิธีการใช้ BackTracking

การแก้ปัญหาที่ไม่สำคัญเหล่านี้จะทำให้คุณต้องรู้ข้อมูลเชิงลึก เทคนิค หรืออัลกอริทึมที่สำคัญ

ในกรณีของ N-Queens เทคนิคคือการย้อนรอย .

การย้อนรอยเป็นการยกเลิกการกระทำบางอย่างก่อนหน้านี้ (เช่น การวางราชินีบนกระดาน) และลองอีกครั้งด้วยการกำหนดค่าอื่น

ฉันคิดว่านี่จะเป็นส่วนที่ยากที่สุด แต่กลับกลายเป็นว่าง่ายทีเดียว

เพื่อหาสิ่งนี้ ฉันใช้การจำลองเล็กน้อย

ฉันวาดกระดานและกล่องเพื่อประคับประคองราชินี :

จากนั้นฉันก็ย้ายกล่องไปรอบๆ กระดาน (ใช้เมาส์โดยตรง) เพื่อจำลองอัลกอริทึม

นี่คือรหัส:

while row >= n
  row    = @queens_in_board[-1][0] + 1
  column = @queens_in_board[-1][1]

  puts "Backtracking, deleted: #{@queens_in_board.pop}"
end

คุณยังสามารถทำเช่นนี้สำหรับปัญหาอื่นๆ เมื่อคุณติดขัด วาดในโปรแกรมวาดภาพ หรือแม้แต่บนกระดาษและลองเล่นดู

นี่คือสาระสำคัญของวิธีการทำงาน:

• เราเดินขึ้นเรื่อยๆ หากเราไปถึงจุดสูงสุดของกระดาน แสดงว่าเราไม่สามารถใส่ราชินีในคอลัมน์นี้ได้
• เราย้อนรอยโดยกำหนดตำแหน่งปัจจุบันเป็นราชินีตัวสุดท้ายและนำออกจากกระดาน
• ถ้าเราไม่สามารถวางราชินีจากตำแหน่งนี้ เราจะย้อนรอยอีกครั้ง

+1 บนตำแหน่งแถวคือวิธีที่ เลื่อนราชินีตัวสุดท้ายเพื่อปรับตำแหน่ง &เปิดการกำหนดค่าบอร์ดใหม่

เมื่อรันโค้ดนี้สำหรับ n =4 (ไม่มีวิธีแก้ปัญหาสำหรับ 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 นี้เป็นตัวอย่างภาพของอัลกอริทึม:

โค้ดเต็ม

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)

เวอร์ชันเรียกซ้ำ

นี่เป็นเวอร์ชันทางเลือกที่ค้นหาวิธีแก้ปัญหาที่เป็นไปได้ทั้งหมด

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 วิธีการ

เวอร์ชันนี้ใช้การเรียกซ้ำ (เมธอดที่เรียกตัวเอง) เพื่อสำรวจโซลูชันบางส่วนทั้งหมด

เมื่อพบวิธีแก้ปัญหาที่สมบูรณ์ เราจะพิมพ์โดยใช้ print_board วิธีการ

สรุป

คุณได้เรียนรู้เกี่ยวกับความท้าทายในการเขียนโค้ดของ N-Queens และวิธีแก้ปัญหาใน Ruby แล้ว คุณยังได้เรียนรู้วิธีพัฒนาทักษะการแก้ปัญหาของคุณอีกด้วย

หากคุณชอบบทความนี้ โปรดแบ่งปันกับทุกคนที่ได้รับประโยชน์จากบทความนี้

ขอบคุณสำหรับการอ่าน!