نحوه طراحی و الگوریتم نویسی برنامه جدولساز

سلام
دوستان و جناب خجسته

چند وقت قبل یکی از دوستان پروژه ای در مورد طراحی و پیاده سازی نرم افزار جدول را از شرکتی قبول کرد و مشغول اجرا شد . متاسفانه در حال حاضر بعد از گذشت چند ماه اجرای پروژه با شکست مواجه شده است . و از طرفی مجبور به تحویل هم میباشد لذا از دوستان تقاضا راهنمایی داریم:

تا آنجا که بنده مطلع شدم در برنامه از بانکی که مشتمل بر هزاران کلمه با موضوعات مختلف میباشد استفاده خواهد شد.
کاربر میتواند جدول دلخواه با تعداد ستون و ردیف بین 5 تا 15 انتخاب کند.
کاربر میتواند به دلخواه تعدادی از خانه ها را سیاه کند.

پس از تنظیمات باید برنامه از بین کلمات بانک بطریق سعی و خطا خانه های جدول را با کلمات( حرف به حرف و افقی و عمودی) پر کند ( یعنی همان کاری که طراحان جدول به صورت سنتی انجام میدهند). پس از مشخص شدن حروف وکلمات کاربر برای هر کلمه سوالی را برای ارایه جدول به دیگران در نظر خواهد گرفت .

این دوست ما نیازمند به راهنمایی و الگوریتم پیشنهادی است و چنانچه سورس آماده وجود داشته باشد آمادگی پرداخت هزینه میباشد( حالا چقدر ؟؟ من نمیدانم).

با تشکر قبلی

سلام،

پر کردن یک جدول کلمات متقاطع با استفاده از تکنیک بازگشت به عقب به راحتی قابل انجام است.
تک تک خانه های جدول را بررسی کرده لیستی از از خانه هایی که به عنوان خانه شروع یک کلمه (حرف اول آن) افقی یا عمودی هستند تهیه می کنیم؛ هر خانه یک بار برای افقی و یک بار برای عمودی بطور جداگانه بررسی می شود. طبیعتا کلمه هایی صفر یا یک حرفی نداریم. در واقع این لیست معادل فهرستی از آیتم های شرح جدول است.
سپس از ابتدای لیست خانه های اول شروع کرده از درون بانک کلمات، با توجه به تعداد حرف های کلمه، و با توجه به خانه های از قبل پر شده در کلمه، کلمه ای از بانک انتخاب می شود و در جدول قرار می گیرد، سپش به خانه بعدی از لیست می رویم و عملیات را تکرار می کنیم. هر زمان که کلمه قابل استفاده دیگری در بانک یافت نشد به خانه قبلی برگشته و کلمه ممکن بعدی را برای آن اختیار می کنیم. زمانی که آخرین خانه نیز با موفقیت انجام شد کار تمام است، و اگر به جایی رسیدیم که برای اولین خانه کلمه دیگری موجود نبود مساله بدون جواب است.

البته این الگوریتم پایه و مستقیم است بدون هوشمندی و احتمالا قابل بهینه سازی.

یک یا دو سال گذشته دیدم نرم افزاری به نام جدول ساز در بازار فروخته می شود؛ شاید یک نسخه از آن مشکل دوست شما را حل کند. (محل مشاهده! تکنو 2000)

آفرین! :تشویق:

سلام
امیر جان

از راهنمایی شما بسیار متشکرم . علاقمند شدم خودم هم مقداری روی این پروژه وقت بگذارم. با استفاده از الگوریتم شما و همچنین مقاله بسیار عالی جناب خجسته دست بکار میشویم . امیدوارم در اجرا و روند برنامه در صورت برخورد مشکل راه گشا باشید.

مجددا از جنابعالی و جناب آقای خجسته کمال تشکر را دارم.

نقل قول:

---

از ابتدای لیست خانه های اول شروع کرده از درون بانک کلمات، با توجه به تعداد حرف های کلمه، و با توجه به خانه های از قبل پر شده در کلمه، کلمه ای از بانک انتخاب می شود و در جدول قرار می گیرد، سپش به خانه بعدی از لیست می رویم و عملیات را تکرار می کنیم. هر زمان که کلمه قابل استفاده دیگری در بانک یافت نشد به خانه قبلی برگشته و کلمه ممکن بعدی را برای آن اختیار می کنیم. زمانی که آخرین خانه نیز با موفقیت انجام شد کار تمام است، و اگر به جایی رسیدیم که برای اولین خانه کلمه دیگری موجود نبود مساله بدون جواب است.

---

با این توضیح که وقتی به عنوان مثال در پروسه بررسی افقی ( A.x ) و با توجه به داده های بانک و تعداد حروف کلمه ای که خانهء A در آن قرار داره ، کلمه ای انتخاب شد ، در روند بررسی های عمودی ( A.y ) ، باید در لیستی که خانهء A در آن قرار دارد کلمه ای قرار داده شود که نهایتا" حرف قرار گرفته در A در بررسی A.x و A.y یکی باشد ، من تو این روندی که توضیح دادی ، هیچ کنترلی برای یکسان بودن حرف موجود در خانه ای با مختصات A ندیدم :?:

لطفا کمی بیشتر توضیح بده . ممنون :oops:

من سالها پیش روی این مساله کار کرده بودم و اینها نتایج نهایی من از تحلیل مساله و اجرای آن است تا جایی که بخاطر میارم و چیزایی که حالا اضافه یا تصحیح می کنم. اگر تکنیک دیگری برای حل این مساله در نظر دارید لطفا مطرح کنید.

توضیح بیشتر:

تعریف:

• کلمه: توالی افقی یا عمودی دو یا بیشتر خانه در جدول محصور به خانه های سیاه و لبه های جدول.
• سرخانه: خانه ای که حرف ابتدای یک کلمه (سر آن) افقی و/یا عمودی در جدول است.

لیست سرخانه ها:
لیستی ترتیبی از تمام سرخانه های موجود در جدول، با ذکر جهت کلمه مربوطه و همراه با داده های دیگر مورد نیاز الگوریتم بازگشتی ما.
برخی خانه ها ممکن است دو بار در این لیست ظاهر شوند، یک با برای جهت افقی و یک بار برای جهت عمودی و این دو کاملا مستقل از هم بوده و در الگوریتم پایه رابطه آنها مانند رابطه هر دو سرخانه کاملا مستقل دیگر است.

مثلا در یک جدول 15×15 روزنامه ایران، 90 سرخانه وجود داشت (در نتیجه 90 شرح نیز نوشته شده بود). در بین این 90 سرخانه، 8 خانه بودند که دوبار ظاهر شده بودند. مثل خانه 1و1 که هم یک سرخانه افقی بود و هم یک سرخانه عمودی. و 74 سرخانه تک جهتی بودند.

پرکردن جدول:
روی لیست سرخانه ها جلو می رویم و برای هر سرخانه با توجه به جهت آن و تعداد حرف و همچنین حروفی که از پیش توسط مراحل قبلی در جدول نشسته اند، در بانک کلمات کلمات قابل استفاده را درنظر می گیریم و اولین را در جدول می نویسیم و به مرحله بعدی (سرخانه بعدی) می رویم و این عملیات را تا انتهای لیست سرخانه ها انجام می دهیم. در هر مرحله چنانجه کلمه دیگری برای انتخاب وجود نداشت به سرخانه قبلی برمی گردیم و انتخاب بعدی آن را برمی گزینیم.

بدیهی است در هر مرحله ممکن است تعدادی حرف از کلمه ای که می خواهیم در جدول بنویسیم از قبل توسط کلمات متقاطع دیگر مشخص شده باشند و این کلمات قابل استفاده ما را محدود خواهد کرد. الگوریتم به این صورت نیست که برای هر سرخانه وقتی کلمه ای مناسب پیدا می کنیم و می نویسیم کنترلی انجام دهیم؛ ما فقط به مرحله بعدی می رویم و کلمه نوشته شده خوبخود انتخاب های سرخانه های بعدی را محدود خواهد کرد.

این شیوه صرفا یک روش کامل است که تمامی پاسخ های ممکن مساله را حتما خواهد داد، اما تا اینجا قطعا بهینه نیست. از پایه این الگوریتم بازگشتی که بگذریم می توانیم روی بهینه سازی آن صحبت کنیم.

نقل قول:

---

با این توضیح که وقتی به عنوان مثال در پروسه بررسی افقی ( A.x ) و با توجه به داده های بانک و تعداد حروف کلمه ای که خانهء A در آن قرار داره ، کلمه ای انتخاب شد ، در روند بررسی های عمودی ( A.y ) ، باید در لیستی که خانهء A در آن قرار دارد کلمه ای قرار داده شود که نهایتا" حرف قرار گرفته در A در بررسی A.x و A.y یکی باشد ، من تو این روندی که توضیح دادی ، هیچ کنترلی برای یکسان بودن حرف موجود در خانه ای با مختصات A ندیدم

---

با توضیحات بالا A.x و A.y همزمان یا حتی لزوما پشت سر هم بررسی نمی شوند حتی اگر A هم سرخانه افقی باشد و هم سرخانه عمودی.
پس از قرار دادن یک کلمه افقی که در A شروع می شود، کنترل جهت عمودی برای A لزوما بهترین حرکت بعدی نیست، اما زمانی انجام خواهد گرفت یا حتی ممکن است قبلا انجام شده باشد.

امیدوارم مفید بوده باشد.

نقل قول:

---

بدیهی است در هر مرحله ممکن است تعدادی حرف از کلمه ای که می خواهیم در جدول بنویسیم از قبل توسط کلمات متقاطع دیگر مشخص شده باشند و این کلمات قابل استفاده ما را محدود خواهد کرد. الگوریتم به این صورت نیست که برای هر سرخانه وقتی کلمه ای مناسب پیدا می کنیم و می نویسیم کنترلی انجام دهیم؛ ما فقط به مرحله بعدی می رویم و کلمه نوشته شده خوبخود انتخاب های سرخانه های بعدی را محدود خواهد کرد.

---

ممنونم .