চেকমেট চেক করুন। সমাধান করার জন্য আরেকটি সমস্যা স্বাগতম! আপনি যদি দাবা খেলতে এবং কোডিং করতে পছন্দ করেন: এটি আপনার জন্য! আজ, আমরা রাজাকে যুদ্ধের ময়দানে আরও একটি দিন বাঁচতে সাহায্য করব, এবং অনেকগুলি কোডও লিখব।
আপনাকে একটি
8
বাই8
ম্যাট্রিক্স উপস্থাপন করা হয়েছে যা একটি দাবা বোর্ডে টুকরোগুলির অবস্থানের প্রতিনিধিত্ব করে। বোর্ডে শুধুমাত্র টুকরা কালো রাজা এবং বিভিন্ন সাদা টুকরা হয়. এই ম্যাট্রিক্স দেওয়া, রাজা চেক কিনা তা নির্ধারণ করুন.
প্রতিটি টুকরা কিভাবে চলে তার বিস্তারিত জানার জন্য, দেখুন
উদাহরণস্বরূপ, নিম্নলিখিত ম্যাট্রিক্স দেওয়া হয়েছে:
...K.... ........ .B...... ......P. .......R ..N..... ........ .....Q..
আপনার ফিরে আসা উচিত True
, যেহেতু বিশপ রাজাকে তির্যকভাবে আক্রমণ করছে।
প্রতিটি টুকরো এবং তার মুভ-সেটের শুরুর অবস্থানের পরিপ্রেক্ষিতে, আমরা "সহজে" প্রতিটি টুকরার পরবর্তী সম্ভাব্য প্রতিটি পদক্ষেপ গণনা করতে পারি।
এবং যেহেতু তারা সবাই যত তাড়াতাড়ি সম্ভব রাজাকে বন্দী করতে আগ্রহী, আমরা ধরে নিতে পারি যে তাদের পরবর্তী পদক্ষেপটি হবে কালো রাজাকে বন্দী করা । অতএব, যেহেতু আমরা কালো রাজার অবস্থানও জানি, তাই আমাদের শুধু কালো রাজার অবস্থানটি অন্যান্য টুকরাগুলির সম্ভাব্য পরবর্তী পদক্ষেপগুলির মধ্যে একটি কিনা তা পরীক্ষা করতে হবে। যদি তা হয়, পরবর্তী সাদা পালা চলাকালীন সাদা টুকরাটি কালো রাজাকে ধরার জন্য সেখানে চলে যাবে।
যেহেতু আমরা একটি 8x8 গ্রাফে আছি (স্পষ্ট হতে হলে, অন্য যেকোন মাত্রা একইভাবে কাজ করবে) এবং আমাদের প্রতিটি অংশের শুরুর স্থানাঙ্ক রয়েছে, আমরা x,y স্থানাঙ্কের সিরিজ তৈরি করতে পারি যা আমাদের পরবর্তী পদক্ষেপগুলি হবে। এটি করার জন্য, আমরা প্রথমে প্রতিটি অংশের জন্য একটি ক্লাস সংজ্ঞায়িত করি, এর স্থানাঙ্কগুলিকে সংজ্ঞায়িত করি এবং তারপর সেখান থেকে প্রতিটি সম্ভাব্য পদক্ষেপের গণনা করার নিয়মগুলি সংজ্ঞায়িত করি।
প্যান দিয়ে সহজ শুরু করা যাক। যাইহোক, আমি পাইথনে এটি তৈরি করছি, যেহেতু এটি এই মুহূর্তে সবচেয়ে জনপ্রিয় ভাষাগুলির মধ্যে একটি এবং যুক্তিযুক্তভাবে যে কেউ সবচেয়ে বেশি পঠনযোগ্য। তারপরও, এখন থেকে কোন ক্লাস অনুসরণ করতে হবে তা জানতে হবে ।
আসুন সংক্ষেপে ব্যাখ্যা করি: আমরা প্রথমে class Pawn
ক্লাস এবং __init__
এর স্থানাঙ্ক x,y
সংজ্ঞায়িত করি। এর পরে, সেখান থেকে প্যান সম্ভাব্য চালগুলি গণনা করার জন্য আমরা possibleMoves
পদ্ধতিটি সংজ্ঞায়িত করি। প্যান চালগুলি তুলনামূলকভাবে সহজ, তাই আমরা তাদের পরিবর্তনশীল moves
যোগ করি, এটি আমাদের গ্রিডের বাইরে সরানো হয় না তা পরীক্ষা করার পরে এবং moves
অ্যারেটি ফেরত দেয়। এখানে দুটি জিনিস লক্ষ্য করা উচিত, বিশেষ করে প্যানের জন্য:
আমরা ইচ্ছাকৃতভাবে স্বাভাবিক আন্দোলন এড়িয়ে যাই , যেহেতু আমরা কালো রাজাকে ক্যাপচার করতে আগ্রহী: যেহেতু প্যানটি কেবল তির্যকভাবে ক্যাপচার করতে পারে এবং আমরা টুকরোগুলিকে অন্য দিকে নিয়ে যাওয়ার বিষয়ে চিন্তা করি না, আমরা তার স্বাভাবিক গতিবিধি এড়িয়ে যেতে পারি।
এখন আমরা সহজভাবে প্যানকে তার স্থানাঙ্কগুলি দিয়ে এবং possibleMoves
পদ্ধতিতে কল করে পরীক্ষা করতে পারি, যেমন: print(Pawn(7,2).possibleMoves())
এবং আমাদের [(6,3),(8,3)]
এর মতো কিছু পাওয়া উচিত। [(6,3),(8,3)]
।
এছাড়াও, আপনি উপরে দেখতে পাচ্ছেন যে আমরা আমাদের গ্রিডের মাত্রাগুলিকে ভেরিয়েবল হিসাবে সংজ্ঞায়িত করেছি , তাই আমরা সম্ভবত অন্যান্য মাত্রার বোর্ডগুলিতে অ্যালগরিদম চালানোর জন্য তাদের পরিবর্তন করতে পারি।
এখন টাওয়ারে যাওয়া যাক।
আবার, আমরা টাওয়ার ক্লাসটি এর স্থানাঙ্কের সাথে শুরু করি এবং possibleMoves
ফাংশনটি সংজ্ঞায়িত করি। এখানে সমস্ত সম্ভাব্য চালগুলি সংগ্রহ করতে আমরা টাওয়ারের সমস্ত বিন্দুকে দুটি অক্ষে রেঞ্জ করি এবং পরিবর্তনশীল চালগুলিতে প্রতিটি একক স্থানাঙ্ক যোগ করি moves
যা সমস্ত লুপের পরে ফেরত দেওয়া হবে। আগের মতই, টাওয়ারের মুভ চেক করতে আমরা সহজভাবে print(Tower(5,3).possibleMoves())
এবং আমাদের এরকম কিছু পাওয়া উচিত: [(1,3), (2,3), (3,3), ..., (5,8)]
।
বিশপের চাল টাওয়ারের চেয়ে জটিল, তাই আমরা এখানে কি ঘটছে তা কিছুটা ব্যাখ্যা করতে পারি। মূলত আমাদের দুটি তির্যক অক্ষের শুরুর অবস্থান থেকে শুরু করে বিন্দু সংগ্রহ করতে হবে । ক্লাস এবং init পদ্ধতি ঘোষণা করার পরে, আমরা দুটি ভেরিয়েবল তৈরি করি: moves
, আগের মতো, এবং currentPos
, যা অক্ষ বরাবর চলার সময় আমরা যে পয়েন্টগুলি সংগ্রহ করেছি তার ট্র্যাক রাখতে ব্যবহার করা হবে। এখন while
লুপ ব্যবহার করে, এবং চেক করছি যে আমরা আমাদের গ্রিডের বাইরে সরে যাচ্ছি না, আমরা যেখানে সরাতে চাই সেই অনুযায়ী আমরা x
এবং y
বাড়াই এবং কমিয়ে দিই । উদাহরণ স্বরূপ, যদি আমরা এর প্রারম্ভিক অবস্থান থেকে উপরে-বামে যেতে চাই, তাহলে y
মান বৃদ্ধি করার সময় আমাদের x
মান হ্রাস করতে হবে। আমরা যদি ডানদিকে নিচে যেতে চাই, তাহলে y
মান হ্রাস করার সময় আমাদের x
মান বৃদ্ধি করতে হবে এবং আরও অনেক কিছু। পরিশেষে, আমরা কেবল আবার একবার moves
ফিরে.
ঠিক আছে, এখানে কি হচ্ছে? ঠিক আছে, যদি আমরা এটি সম্পর্কে চিন্তা করি, রানীর বিশপ এবং টাওয়ারের মিলিত চাল একই রকম । তিনি রানীর চেয়ে টাওয়ার আকৃতির বিশপ মেচা-বটের মতো। এই কারণে, তার চাল কোডিং সত্যিই সহজ. তার শ্রেণী ঘোষণা করার পর আমরা কেবল তার possibleMoves
সংজ্ঞায়িত করি বিশপের এবং টাওয়ারের সম্ভাব্য চালগুলির ফলে সৃষ্ট চালগুলির ইউনিয়ন অ্যারে হিসাবে।
লক্ষ্য করুন যে possibleMoves
ফাংশনে ক্লাস Bishop
এবং Tower
ইনস্ট্যান্স কল করার সময় তাদের পরামিতি x
এবং y
দেওয়া হয়েছে self.x, self.y
, তাই তারা আসলে রানী স্থানাঙ্ক।
নাইট আমার কাছে সবচেয়ে বিশেষ। তার মুভ-সেটটি অদ্ভুত, যেমন "L" আকৃতির, তাই আমি এটিকে কোড করার জন্য বিশেষভাবে চতুর বা দ্রুত উপায় খুঁজে পাইনি এবং আমি তার শুরুর অবস্থান থেকে তার সম্ভাব্য 8টি মুভের প্রতিটির হিসাব করে কঠিন কোডিং করেছিলাম।
রাজা সম্পর্কে সংক্ষিপ্ত ধারণা একটি দম্পতি. যেহেতু আমাদের রাজাকে স্থানান্তরিত করার প্রয়োজন নেই, শুধুমাত্র তিনি চেক করেছেন কি না তা জানাতে হবে, আমাদের সত্যিই তার মুভ-সেট বাস্তবায়ন করার দরকার নেই । যাইহোক, আমরা নিবন্ধের শেষে একটি সংক্ষিপ্ত বাস্তবায়নও দেখতে পাব। এছাড়াও, এটিকে কোডিং করা রানীর মুভ-সেটকে নারফিং করার মতো সহজ নয়, যেমনটি আমরা পরে দেখব। তাই আপাতত, আসুন তার নড়াচড়া এড়িয়ে যাই এবং সমাধানটি দেখি।
আমরা এখন কেবলমাত্র কয়েকটি স্থানাঙ্ক হিসাবে একটি পরিবর্তনশীল blackKing
তৈরি করি। তারপর প্রতিটি অংশের জন্য আমরা এর ক্লাসের একটি উদাহরণ তৈরি করি যা আমরা তৈরি করি এবং পদ্ধতিটিকে কল করি possibleMoves
এর পুরো সেটটি গণনা করার জন্য। একবার আমাদের কাছে এটি হয়ে গেলে, আমরা সেই মুভ-সেটগুলিতে blackKing
স্থানাঙ্কগুলি উপস্থিত আছে কিনা তা পরীক্ষা করি: যদি সেগুলি থাকে তবে আমরা মুদ্রণ করি যে রাজা সেই নির্দিষ্ট অংশ দ্বারা চেক করা হয়েছে। এখানে ফলাফল এই মত কিছু:
Pawn moves: [(8, 3), (6, 3)] Tower moves: [(1, 3), (2, 3), (3, 3), (4, 3), (6, 3), (7, 3), (8, 3), (5, 1), (5, 2), (5, 4), (5, 5), (5, 6), (5, 7), (5, 8)] Check by the tower! Bishop moves: [(3, 8), (1, 6), (1, 8), (3, 6), (4, 5), (5, 4), (6, 3), (7, 2), (8, 1)] Queen moves: [(4, 3), (5, 4), (6, 5), (7, 6), (8, 7), (2, 1), (2, 3), (1, 4), (4, 1), (1, 2), (2, 2), (4, 2), (5, 2), (6, 2), (7, 2), (8, 2), (3, 1), (3, 3), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8)] Knight moves: [(4, 7), (4, 5), (8, 7), (8, 5), (5, 4), (7, 4), (7, 8), (5, 8)] Check by the knight!
রাজার বেঁচে থাকার কিছু সম্ভাবনা আছে কিনা বা এটি আসলে চেক মেট কিনা তাও যদি আমরা গণনা করতে চাই তবে কী হবে? এই উদ্দেশ্যে, আমাদের রাজার পদক্ষেপের সেট গণনা করতে হবে।
এর একটু বর্ণনা করা যাক. প্রথমত, আমরা আমাদের ক্লাস এবং স্থানাঙ্কগুলিকে আগের মতো সংজ্ঞায়িত করি। এর পরে আমরা possibleMoves
পদ্ধতি তৈরি করি এবং রাজার সম্ভাব্য চালগুলি কোড করি (আবার, আমি নিশ্চিত যে একটি দ্রুততর উপায় আছে, তবে সেখানে মাত্র 8টি সম্ভাব্য চাল রয়েছে…)। এর পরে, আমরা পরীক্ষা করি কোন পদক্ষেপগুলি অবৈধ (বোর্ডের বাইরে সরানো) এবং শুধুমাত্র validMoves
ফেরত দেই।
তাই এখন, রাজার এখনও বেঁচে থাকার সুযোগ আছে কিনা তা পরীক্ষা করার জন্য, তার সম্ভাব্য চালগুলির মধ্যে কোনটি অন্য কোন চালের সেটে নেই কিনা তা পরীক্ষা করতে হবে। এটি করার জন্য আমরা কেবল রাজার চালগুলি এবং অন্যান্য চালগুলির উপর লুপ করি।
তাই আমাদের রাজা বেঁচে থাকার জন্য এখনও আশা আছে! আমি মনে করি তার জন্য ভাগ্যবান…
প্রথমত, যেহেতু প্রতিটি অংশ একটি ক্লাসের একটি উদাহরণ , আমাদের অবশ্যই সেই উদাহরণটি শুরু করার সময় বিবেচনা করতে হবে।
রানীর টাওয়ার এবং বিশপের একত্রিত চালের সেট দরকার। যেহেতু সময় জটিলতা মূল্যায়ন করার সময় আমাদের অবশ্যই সবচেয়ে খারাপ পরিস্থিতিতে ফোকাস করতে হবে , বিশপের টিসি টাওয়ারের টিসিতে বিরাজ করে। সুতরাং, আমাদের অবশ্যই রাণীর জন্য O(n) এর একটি টিসি বিবেচনা করতে হবে।
শেষ পর্যন্ত, রাজার একটি কঠিন কোডেড চাল রয়েছে, তবে একটি বৈধকরণ প্রক্রিয়াও জড়িত যা একটি ফর লুপ ব্যবহার করে । তাই টেকনিক্যালি, এমনকি যদি রাজার চালের সেট যেকোন ক্ষেত্রে তুলনামূলকভাবে ছোট হয়, আমাদের অবশ্যই তার টিসিকে O(n) হিসাবে বিবেচনা করতে হবে, বোর্ডে তার অবস্থানের উপরও নির্ভর করে।
এই মুহুর্তে, আমরা কালো রাজার চেক স্ট্যাটাস যাচাই এবং প্রিন্ট আউট করতে প্রতিটি অংশের জন্য একটি লুপ ব্যবহার করি। এটি আমাদের কোন সমস্যা দেয় না যেখানে tc ধ্রুবক থাকে (উদাহরণস্বরূপ টাওয়ারটি ধরুন: আমরা এর 14টি চাল গণনা করি এবং তারপরে তাদের উপর সর্বাধিক 14 বার লুপ করি, তাই আমরা এটিকে নির্দিষ্ট সময়ও বিবেচনা করতে পারি)। তারপরও, আমাদের সমস্যা হবে যেখানে tc O(n) বা তার উপরে, যেহেতু আমরা একটি লুপ যোগ করছি যা চাল সংখ্যা বৃদ্ধির সাথে সাথে বৃদ্ধি পাবে।
পরিশেষে, আমরা চেক মেট যাচাই করার জন্য লুপের জন্য একটি ডবল (অভ্যন্তরীণ) ব্যবহার করি , যা নিশ্চিতভাবে O(n²) এর একটি tc হতে চলেছে, যা রাজার চালের সংখ্যা এবং অন্যান্য টুকরোগুলির গতির উপর নির্ভর করে।