রুবিতে N-Queens চ্যালেঞ্জ মাস্টারিং: একটি ধাপে ধাপে সমাধান

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

এটি এমন দেখায়:

একটি কোয়িন সব ডিরেকশনে চলতে পারে:

• ভার্টিক্যাল
• হরিজোন্টাল
• ডায়াগোনাল

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

এই আর্টিকেলে আপনি শিখবেন আমি কীভাবে সমাধানটি খুঁজে পেয়েছি।

পরিকল্পনা (The Plan)

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

এটি আপনাকে সমস্যাটি এবং সমাধানের ধাপগুলো স্পষ্ট করতে সাহায্য করে।

আপনি যদি পরিকল্পনা লিখতে সমস্যা হয় নিশ্চিত হন আপনি সমস্যাটি ১০০% বুঝতে পেরেছেন।

N-Queens সমাধানের জন্য আমার পরিকল্পনা:

• পজিশন 0,0-এ শুরু করুন
• যদি বৈধ পজিশন: কোয়িন রাখুন, কলাম এডভ্যান্স করুন (+ 1), রো 0 সেট করুন
  • টপ, বটম, লेफট, রাইট, ডায়াগোনাল চেক করুন
• অন্যথায়: ১ স্কোয়ার এডভ্যান্স করুন
  • আপ যান (row + 1) যদি করেন্ট পজিশন == n না হয়
  • ব্যাকট্র্যাক করুন যখন কোয়িন বর্তমান কলামে রাখা যায় না
    • শেষ কোয়িনটি রিমুভ করুন
    • রো এবং কলামকে শেষ কোয়িনের পজিশনে সেট করুন row + 1 সহ

এটি আমার początkow লিখাটির একটি ক্লিন ভার্সন।

আমি সেই ধাপগুলোতে গভীরে যাই যেগুলো আরও ডিটেইল চাই ইমপ্লিমেন্ট করার আগে।

এখন:

আপনার পরিকল্পনা পেर्फেক্ট হবে না (আমারও ছিল না) কিন্তু এটি আপনাকে কী দিয়ে কাজ করতে হবে সেটির একটি ধারণা দেবে।

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

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

বৈধ মুভ খুঁজে বের করা

একটি পজিশন বৈধ কিনা চেক করার জন্য আমাদের কয়েকটি ডিরেকশনে তাকাতে হবে।

২D বোর্ডের সাথে ঘামাঘামি করার বদলে, আমি বোর্ডে তাদের পজিশনসহ কোয়িনের একটি অ্যারে রাখতে সিদ্ধান্ত নিলাম।

তারপর আমরা এই কোয়িন অ্যারেকে আমরা যাচাই করতে চাই সেই পজিশনের বিরুদ্ধে চেক করি।

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

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

এটি একটি কোয়িন রিটার্ন করবে যদি রোটি নেওয়া হয়, অন্যথায় nil।

আপনাকে কলাম চেক করতে হবে না কারণ কোয়িন রাখার পর আমরা পরবর্তী কলামে যাই।

ডায়াগোনালের জন্য কিছু এক্সট্রা কাজ লাগে কারণ ৪টি আছে।

এখানে রাইট আপার ডায়াগোনালের জন্য কোড:

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

অন্যান্য ডায়াগোনালগুলো একই, পার্থক্য শুধু লুপের কন্ডিশন এবং ডিরেকশনে (row + 1 / row - 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 কীভাবে ইমপ্লিমেন্ট করবেন

এই নন-ট্রivial চ্যালেঞ্জ সমাধান করতে হলে আপনাকে একটি কী ইনসাইট, টেকনিক বা অ্যালগরিদম জানতে হবে।

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 

আপনি অন্য সমস্যায় স্টাক করলে এই পদ্ধতিও ব্যবহার করতে পারেন, কোনো ড্রইং প্রোগ্রামে বা কাগজে আঁকিয়ে 그 roze দিয়ে।

এটি কীভাবে কাজ করে সেটির সারাংশ:

• আমরা উপরে যেতে থাকি, যদি বোর্ডের টপে পৌঁছাই মানে এই কলামে কোয়িন ফিট করা যায়নি
• আমরা বর্তমান পজিশনকে শেষ কোয়িনে সেট করে এবং বোর্ড থেকে রিমুভ করে ব্যাকট্র্যাক করি
• যদি এই পজিশন থেকেও কোয়িন রাখা না যায় তবে আবার ব্যাকট্র্যাক করি

রো পজিশনে + 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 কোডিং চ্যালেঞ্জ এবং রুবিতে কীভাবে সমাধান করবেন সেটি শিখেছেন। আপনি আপনার সমস্যা সমাধানের দক্ষতা কীভাবে বাড়াবেন সেটিও শিখেছেন।

আপনি যদি এই আর্টিকেলটি পছন্দ করেন তবে যারা এতে লাভ করতে পারে তাদের সাথে শেয়ার করুন।

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