الگوریتم Backtracking برای Sudoku

[jalalx]

سلام خدمت دوستان
من دنبال یه توضیح کامل(کد نمی خوام) برای پیاده سازی Backtracking برای حل جدول Sudoku هستم. اگه کسی می دونه چه جوری می شه با Backtracking پیاده سازی کنه ممنون می شم اینجا بذاره:قلب:!

[alijy19]

سلام
روش backtracking برای حل sudoku دقیقا همون جستجوی اول-عمق هست. برای همین از هر الگوریتمی که جستجوی اول-عمق رو انجام میده میتونید استفاده کنید.
در هر حال یکی از الگوریتمهای معروف برای حل sudoku با روش backtracking الگوریتم Ariadne's Thread هست.

الگوریتم Ariadne's Thread؛

1. برای هر کدوم از خونه های خالی جدول یه مجموعه شامل اعداد 1 تا 9 تعریف کنین.

2. اگه توی جدول هیچ خونه خالی باقی نمونده، sudoku حل شده. پایان.

3. یکی از خونه های خالی (مثلا C) رو انتخاب کنید و یکی از اعداد باقی مونده توی مجموعه تعریف شده اش (مثلا V) رو بهش اختصاص بدین.

4. یه کپی از جدول تهیه کنین و توش توی خونه C مقدار V رو اضافه کنین. از الان با این کپی کار کنین.

5. چک کنین که آیا هیچ کدوم از خونه های هم سطر، هم ستون و یا هم مربعی با C دارای مقدار V هستن یا نه. اگه نه، برید به مرحله 2.

6. اگه آره، باید backtrack انجام بدین. اگه جدولی که در حال حاضر دارین روش کار میکنین جدول اصلی هست (نه کپی) معنیش اینه که sudoku غیر قابل حله. پایان.

7. اگه روی یکی از کپی ها هستین اون کپی رو دور انداخته و از این به بعد از جدولی که اون کپی رو از روش تهیه کرده بودین استفاده کنین.

8. توی این جدول مقدار V رو از مجموعه مقادیر تعریف شده برای خونه C حذف کنید. اگه با این حذف این مجموعه تهی شد برید به مرحله 6.

9. در غیر این صورت برید به مرحله 2.


یه الگوریتم معروف دیگه هم هست به اسم Dancing Links که من هنوز باهاش کار نکردم، ولی میدونم از لینکهای دو طرفه برای تولید قابلیت بازگشتی بین دو گره (تو جستجوی اول-عمق) استفاده میکنه.

[armiya]

با سلام امکان داره جدول sudoku رو برام توضییح بدید










با تشکر

[whitehat]

اگه در مورد خود سودوکو می خواهید بدانید به لینک زیر مراجعه کنید
جدول سودوکو (http://fa.wikipedia.org/wiki/%D8%B3%D9%88%D8%AF%D9%88%DA%A9%D9%88)

[mey.hoss]

سلام! منظورتون از مرحله دو یا مرحله ۶ چیه؟؟‌ :(
برا طراحی خود جدول چه راه حلی دارین؟
لطفا کمک کنین . ممنون
email:
meyhoss_1@hotmail.com