রুবির সাথে এন-কুইন্স সমস্যা সমাধান করা

N-Queens হল একটি আকর্ষণীয় কোডিং চ্যালেঞ্জ যেখানে আপনাকে N Queens একটি N * N বোর্ডে রাখতে হবে .

এটা এই মত দেখায়:

একজন রানী সব দিকে যেতে পারে:

• উল্লম্ব
• অনুভূমিক
• কর্ণ

সমাধানটি (অনেকগুলি হতে পারে) অবশ্যই সকল রানীকে বোর্ডে রাখতে হবে এবং প্রতিটি রানীকে অবশ্যই অন্য রানির নাগালের বাইরে থাকতে হবে।

এই নিবন্ধে আপনি শিখতে যাচ্ছেন কিভাবে আমি সমাধান নিয়ে এসেছি।

পরিকল্পনা

এই ধরনের চ্যালেঞ্জগুলি সমাধান করার সময় শুরু করার জন্য একটি ভাল জায়গা হল সরল ইংরেজিতে একটি পরিকল্পনা লিখুন৷

এটি আপনাকে সমস্যাটি কী এবং এটি সমাধানের পদক্ষেপগুলি সম্পর্কে পরিষ্কার করতে সহায়তা করে৷

আপনার পরিকল্পনা লিখতে সমস্যা হলে নিশ্চিত করুন যে আপনি সমস্যাটি 100% বুঝতে পেরেছেন .

এন-কুইন্স সমাধানের জন্য আমার পরিকল্পনা:

• শুরু @ অবস্থান 0,0
• যদি বৈধ অবস্থান:রানী রাখুন, অগ্রিম কলাম (+ 1), সারি 0 এ সেট করুন
  • শীর্ষ, নীচে, বাম, ডান, তির্যক চেক করুন
• অন্যথায়:অগ্রিম 1 বর্গ
  • উপরে যান (সারি + 1) যদি না বর্তমান অবস্থান ==n
  • ব্যাকট্র্যাক করুন যখন রানীকে বর্তমান কলামে রাখা যাবে না
    • শেষ রানীকে সরিয়ে দিন
    • সারি + 1 সহ শেষ রাণীর অবস্থানে সারি এবং কলাম সেট করুন

এটি আমি প্রাথমিকভাবে যা লিখেছিলাম তার একটি পরিষ্কার সংস্করণ৷

আমি সেগুলি বাস্তবায়ন করতে পারার আগে যে ধাপগুলি আরও বিশদ প্রয়োজন সেগুলি সম্পর্কে ড্রিল ডাউন করি৷

এখন :

আপনার পরিকল্পনা নিখুঁত হবে না (আমার ছিল না) তবে এটি আপনাকে কোন দিকে কাজ করতে হবে তার একটি ধারণা দেবে।

আপনি যদি একটি কঠিন পরিকল্পনা লিখতে না পারেন সমাধান খুঁজতে কোন ভুল নেই …

…সমাধান কিভাবে কাজ করে তা বুঝুন তারপর আপনার নিজের লিখুন।

বৈধ চাল খোঁজা

একটি অবস্থান বৈধ কিনা তা পরীক্ষা করতে আমাদের বিভিন্ন দিকে তাকাতে হবে।

একটি 2D বোর্ডের সাথে তালগোল পাকানোর পরিবর্তে, আমি রাণীদের একটি অ্যারে রাখার সিদ্ধান্ত নিয়েছি তাদের অবস্থান সহ বোর্ডে।

তারপর আমরা যে অবস্থানটি যাচাই করতে চাই তার বিপরীতে আমরা রানীদের এই অ্যারেটি পরীক্ষা করি।

উদাহরণস্বরূপ, সারি চেকের জন্য:

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

ব্যাকট্র্যাকিং কিভাবে প্রয়োগ করবেন

এই অ-তুচ্ছ চ্যালেঞ্জগুলি সমাধান করার জন্য আপনাকে একটি মূল অন্তর্দৃষ্টি, কৌশল বা অ্যালগরিদম জানতে হবে৷

এন-কুইন্সের ক্ষেত্রে কৌশলটি ব্যাকট্র্যাক করছে .

ব্যাকট্র্যাকিং হল পূর্ববর্তী কিছু ক্রিয়াকে পূর্বাবস্থায় ফিরিয়ে আনা (যেমন বোর্ডে একটি রাণী স্থাপন করা) এবং একটি ভিন্ন কনফিগারেশনের সাথে আবার চেষ্টা করা৷

আমি ভেবেছিলাম এটি সবচেয়ে কঠিন অংশ হবে, কিন্তু এটি বেশ সহজ হয়ে উঠেছে৷

এটা বের করার জন্য আমি একটু সিমুলেশন চালালাম।

আমি নিজেই একটি বোর্ড এবং কিছু রাণীদের প্রতিনিধিত্বকারী বাক্স এঁকেছি :

তারপর আমি অ্যালগরিদম অনুকরণ করতে বোর্ডের চারপাশে বাক্সগুলিকে (সরাসরি আমার মাউস দিয়ে) সরিয়ে দিয়েছি৷

এখানে কোড:

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"

এই জিআইএফ হল অ্যালগরিদমের একটি চাক্ষুষ উদাহরণ:

সম্পূর্ণ কোড

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 ব্যবহার করে প্রিন্ট করি পদ্ধতি।

সারাংশ

আপনি এন-কুইন্স কোডিং চ্যালেঞ্জ এবং রুবিতে কীভাবে এটি সমাধান করবেন সে সম্পর্কে শিখেছেন। আপনি কীভাবে আপনার সমস্যা সমাধানের দক্ষতা উন্নত করবেন তাও শিখেছেন।

আপনি যদি এই নিবন্ধটি পছন্দ করেন তবে দয়া করে এটি থেকে উপকৃত হতে পারে এমন কারো সাথে শেয়ার করুন৷

পড়ার জন্য ধন্যবাদ!