التحدي الأكبر ...من يستطيع كتابة خوارزمية لحل لعبة sudoku

السلام عليكم

أولاً : للتعريف باللعبة لمن لا يعرفها ومعلومات عنها وبايتها وطرق حلها وخلافة من معلومات عن اللعبة تفضلوا بزيارة هذا الرابط

ثانياً : لإختبار صحة حل خريطة سودوكو فحلها هو إختبار كل عنصر من عناصر المصفوفة بأنة لا يتكرر فى الصف والعمود والمربع الأصغر الموجود به وهكذا لجميع عناصر المصفوفة ولهذا يمكن كتابة دالة لهذا الغرض بأى لغة برمجة .

ثانياً : خوارزمية حل اللعبة يمكن حلها بسهولة بإستخدام مبدأ التراجعية فى لغة البرمجة .

ثالثاً : وهو أصعب جذء فى لعبة السودوكو وهو خوارزمية توليد الخريطة .

أعرف مبدأ التراجعية ولكني افكر في كود يعمل عمل العقل البشري في استراتجياته في حل اللعبة فما رأيك؟

السلام عليكم

سيكون الأمر صعب , لقد حاولت سابقاً وضع خوارزمية حل لا تعتمد على مبدأ التراجعية ومملت منها وفى النهاية رجعت وإستخدمت التراجعية مع أنها تستغرق وقت طويل "بالنسبة لسرعة الجهاز" فى حل بعض المسائل ولكن هذه أفضل طريقة لتعامل الحاسب مع هذه النوعية مع أنها لا تصلح كطريقة للبشر فى حل لعبة السودوكو لأنها مملة ولكن للجهاز هى ليست كذلك .

السلام عليكم

كيفك حالك لينكساوى عاودت كتابة خوارزمية لطريقة الحل كالبشر وهذه المرة تحصلت عليها " شكراً لك لأنك جعلتى أعاود التفكير فى الخوارزمية من جديد " والخوارزمية بإختصار هى البحث فى رقعة السودوكو على الخانة التى لا تقبل إلا قيمة واحدة لا غير ثم تضع تلك القيمة ثم تبحث عن خانة أخرى لا تقبل إلا قيمة واجدة ثم تضع القيمة بها وهكذا إلى أن تنهى حل رقعة السودوكو , ولكن أنت تعلم أن هناك رقع من السودوكو تحتاج لتخمين لوضع قمية وتجربتها أهى التى تحققق الحل أم لا ذلك النوع من رقع السودوكو لا تستطيع هذة الخوارزمية حله , ولكن الخوارزمية التراجعة تحل تلك النوعية من الرقع .

هناك شرح بسيط للخوارزمية داخل الكود

هذا الكود للخوارزمية كتبتة بلغة الجافا :

sudoku.java

وهذا ملف لرقع سودوكو جاهزة لتجربة البرنامج عليها حتى أطور خوارزمية توليد السودوكو التى أنشأتها لتنتج رقع ذات حل وحيد "ولكن ليس الآن"

sudoku.txt

إن كان هناك وقت سأصمم اللعبة فى شكلها الرسومي لننشرها لهواه لعبة السودوكو .

موضوع جميل

soduko يمكن ان ننظر لها على انها constraint satisfaction problem حيث ان المتغيرات variables هي الcells والقيود هي allDifferent والدومين هو من 1....9 في حالة ان n=3

بعدها يمكننا ان نحلها باي CSP solver موجود مثل javaCream (اللي وده يجرب شي جديد يحاول يحلها بهالطريقه ةيخبرنا عن النتايج )

لي عوده بعد مااترك الجهاز الغثيث اللي اعمل عليه الان

أحسنت يا أخي

السلام عليكم

لينكساوى لا أرى مشاركتك أو حتى نقدك للكود حتى نتشارك ونستفبد جميعاً , أخى Eisa Ayed فى إنتظار مشاركتك .

انا صممت لعبة سودوكو قبل اربع سنوات بلغة سي بلاس والحل توقعته سهل بس التخمين راح يعقد الكود

وهذا كود لعبتي اتمتعو بشاشة السوداء هههههه

finall suduko.txt

السلام عليكم

- رائع عزيزى zaraki_kenpache , هلا أرسلت لنا البرنامج التفيذى مع ملف المشروع للبرنامج , لأن الكود مكون من 1365 سطر , وتتبع الأخطاء البرمجية مع إختلاف المترجمات أمر مرهق .

شكرا لمشاركاتكم

أنا أريد المشاركة بذكر الكود التي يصنع اللعبة وهو كود صعب كتبعه أحد المبرمجين الأجانب

حمله من هنا

http://www.mediafire.com/download.php?dimdtmxut9u73i5

السلام عليكم

شكراً لك أخى لينكس مان , وموجد أيضاً أكواد أخرى عديدة لتكوين لعبة السودوكو بلغات مختلفة فقط إبحث فى محرك البحث عن sudoku solver أو sudoku generator وسوف تجد العديد من الأكواد ولكن الأهم هو ماهى الطريقة التى تتبعها هذة الأكواد فى اللعبة فهناك أكواد مبرمجة جيداً وهناك أكواد تنفذ المهمة ولكن تكون غير واضحة وترهق المبرمج فى تتبع مسار عملها .

فدراسة الكود البرمجى بشكل جيد وفهمه وتتبعه سوف يتيح لك أفكار جديدة فى تطويرة للأفضل ولكن قبل دراسة الكود يجب أن تعرف ماهى الطريقة "الخوارزمية" المتبعة فى الكود ليسهل عليك فهمه بسهولة .

سأكون صريحا معك أخي حاولت تتبع الكود ولكن كان صعبا معقدا أو أنا لست خبيرا في الدالفي

السلام عليكم

اقتباس

سأكون صريحا معك أخي حاولت تتبع الكود ولكن كان صعبا معقدا أو أنا لست خبيرا في الدالفي

ومن الأفضل أيضاً تحديد كود ليس به المزيد من الأكواد الإضافية الخاصة بواجهة اللعبة والتعامل معها والتحديد فى البداية على الخوارزمية المراد دراستها حتى لا تختلط عليك الأمور .

وهذه بعض من الأكواد للعبة بعدة لغات وهناك أيضاً اللعبة بلغات أخرى فقط قم بالبحث إن أردتها :

لغة جافا

NPGeneratorV1_0_1src.zip

sudokiller.zip

لغة C

solver_1.10.zip

solver_1.11.zip

solver_1.20.zip

لغة ++c

SuDoKu_Gen_C++.zip

لغة #c

sudoku_src.zip

Sudoku-source-v2.0.zip

لغة php

php-sudoku-code.zip

لغة javaScript

sudoku-javaScript.zip

لغة VB

Abhishek_Sudoku_src1-vb.zip

Sudoku-vb.zip

وهناك العديد من الأكواد الموجودة للعبة بلغات عديدة فقط عليك البحث والأختيار بين أفضل الأكواد فهناك أكواد مكتبوبة بطريقة رائعة و سهلة التتبع وهناك منها ما يضيع وقتك .

وانا مسافر بالطيار ه تذكرت هالموضوع وكتبت القوريثم (اكيد مو كامل) لحل المساله..

المشكله ان الlatex المدعم بالمنتدى مايظهر الكوة بكله الصحيح..

\begin{algorithm}

Let V=set of cells in the soduko\\
Let D= set of domains for each $v \in V$\\
Let C=set of constraints $c(X_{1},X_{2}...X_{n})$\\
DeleteInfeasibleValues(V)\\
assignment=$\emptyset$\\
SolveSoduko(assignment)

\caption{start(Node n)}
\label{aa}
\end{algorithm}

\begin{algorithm}

if(assignment.isSolution())\\\hspace*{.3cm}
return assignment\\
else\\
Let V=getChildren(assignment)\\\hspace*{.3cm}
for each  $v \in V$\\\hspace*{.4cm}
if($consistent(v,d_{v}$) where $d_{v}\in D_V$\\\hspace*{.6cm}
V=$d_{v}$\\\hspace*{.6cm}
assignment.addVariable(V)\\\hspace*{.6cm}
SolveSoduko(assignment)\\\hspace*{.6cm}

\caption{SolveSoduko(assignment)}
\label{a}
\end{algorithm}

اقتباس

ثانياً : خوارزمية حل اللعبة يمكن حلها بسهولة بإستخدام مبدأ التراجعية فى لغة البرمجة .

معليش ما هي التراجعية ... هل هي نفسها الـ Recursion؟؟؟

اقتباس

معليش ما هي التراجعية ... هل هي نفسها الـ Recursion؟؟؟

لا ليست إياها

بل المقصود بها الحل التراجعي او النهج العكسي في حل اللعبة وهي احدى الطرائق الاربعة المسلوكة في حلها

وانظر للاستزادة هذا الرابط

http://www.oloommagazine.com/Articles/ArticleDetails.aspx?ID=2147

السلام عليكم

sanousy.howari كتب:

معليش ما هي التراجعية ... هل هي نفسها الـ Recursion؟؟؟

إليك أخى الكريم شرح مبسط قمت بعمله فى صوره متحركة لمبدأ التراجعية فى لعبة السودوكو

طريقة الحل تكون كما فى الشكل التالى :

يتم إختبار أول خلية فارغه يتم وضع إحدى القيم من 1 وحتى 9 بحيث لا تكون تلك القيمة موجودة فى العمود أو الصف المقابلين للخلية وأيضاً يجب أن لا تكون القيمة موجودة فى المربع الثلاثى "الصغير" الذى يحوى الخلية .

وشرح هذا على المثال السابق تم وضع 1 فى الخلية 0,0 فتعارضت مع الشروط فتم وضع القيمة 2 حققت الشروط ثم تم الإنتقال للخلية التالية 0,3 ويتم إختبار القيم من 1 إلى 9 وهكذا ثم الإنتقال للخلية الفارغة التالية لها إلى أن تصادف خلية لا تقبل أى من القيم من 1 إلى 9 كما فى الخلية 1,2 وعند هذه اللحظة يتم تفريغ هذه الخلية ويتم الرجوع للخلية السابقة لها لإختبار القيمة التالية للقيمة الموجودة بها فإن لم يجد قيمة مناسبة يتم الرجوع مرة أخرى للخلف وهكذا ... وعند إيجاد قيمة تحقق الشروط نبدأ بالإنتقال للخلية الفارغة التالية للأمام وهكذا حتى يتم حل اللعبة وهذا ما يعرف "بمبدأ التراجعية" وبنفس الطريقة يتم حل لعبة المتاهة.

وعند وصول القيمة فى الخلية التى تم البدأ منها إلى القيمة 9 ولم يتم ملئ رقعة السودوكو فهذا يعنى أن هذه الرقعة ليس لها حل .

هذا من أحد الطرق المستخدمة فى حل لعبة السودوكو من خلال جهاز الحاسب لأن تلك الطريقة تعتبر من الطرق المملة لو إستخدمها الإنسان فى حل اللعبة ولكنها مجدية مع جهاز الحاسب

بعد أن تم شرح طريقة الحل نقوم الأن بشرح الكود الذى يقوم بهذه المهمة ستكون الأكواد بلغة الجافا :

يتم تعريف مصفوفة عامة باسم sudokuArr بها رقعة السودوكو المراد حلها ويتم وضع قيم 0 فى الخلايا الفارغة فى المصفوفة

وهذا كود حل الرقعة :

	boolean solve(byte row, byte col)
	{
    	// لضبط إختبار العناصر بالترتيب فى المصفوفة
   	if (col == 9) {
        	col = 0;
        	if (row == 8)
            	return true;
        	row++;
    	}
		// شرط تخطى قيم المصفوفة الإبتدائية
    	if( sudokuArr[row][col] != 0 )
			return solve( row, col+1 );

 		for( byte val=1;val<10;val++ )
 		{
        	if( check(row,col,val) )
        	{
   			sudokuArr[row][col] = val ;
   			if (solve(row,col+1))return true;
        	}
 		}
 		sudokuArr[row][col]=0;
 		return false;
	}

وفى بداية هذا الكود حيث أنه يتم الزيادة بمقدار 1 فى كل مرة فيجب وضع شرط لنجعل الإنتقال فى خلايا المصفوفة الثنائية بالتتابع حيث أننا نقوم بزيادة col فقط بمقدار 1 فى كل مرة وعند إنتهاء المصفوفة تعيد القيمة true

ثم شرط تخطى القيم الموضوعة مسبقاً فى رقعت السودوكو وذلك عن طريق الإستدعاء الذاتى مرة أخرى لنفس الدالة للخلية التالية

- ثم ندخل فى حلقة إختبار القيم الصالحة للخلية من القيمة 1 إلى 9 بإستخدام دالة التحقق check فإن كانت القيمة صالحة يتم إضافتها للمصفوفة ويتم إستدعاء الدالة مرة أخرى للخلية التالية فى الشرط التالى

sudokuArr[row][col] = val ;
if (solve(row,col+1))return true;

هذا الشرط يدخلنا فى حلقة إستدعاء ذاتى تنتهى بإنتهاء المصفوفة عندما تعيد الدالة فى بداية الكود القيمة true أى الوصول لنهاية المصفوفة ومن ثم تعيد القيمة true أى تم حل الرقعة .

وإن إنهت حلقة for ولم توجد قيمة صالحة لتلك الخلية يتم وضع القيمة 0 فى هذه الخلية والعودة للخلية السابقة لها .

وهذا كود دالة التحقق check :

   boolean check( byte row,byte col, byte val )
   {
  	for( int i = 0; i < 9; i++ ) if( sudokuArr[row] == val ) return false ;
  	for( int i = 0; i < 9; i++ ) if( sudokuArr[col] == val ) return false ;
  	row = (byte)((row / 3) * 3 );
  	col = (byte)((col / 3) * 3 );
  	for( byte r = 0; r < 3; r++ )
 		for( byte c = 0; c < 3; c++ ) if( sudokuArr[row+r][col+c] == val ) return false ;
  	return true ;
   }

وهذا برنامج لتطبيق الدوال السابق ذكرها :

sudoku2.java

دمتم فى رعايه الله

+1 لك يا أحمد

السلام عليكم

شكراً عزيزى لينكس مان , مررورك وقراءه مشاركتى هذا يكفينى عزيزى .

اقتباس

وانا مسافر بالطيار ه تذكرت هالموضوع وكتبت القوريثم (اكيد مو كامل) لحل المساله..

المشكله ان الlatex المدعم بالمنتدى مايظهر الكوة بكله الصحيح..

\begin{algorithm}

Let V=set of cells in the soduko\\
Let D= set of domains for each $v \in V$\\
Let C=set of constraints $c(X_{1},X_{2}...X_{n})$\\
DeleteInfeasibleValues(V)\\
assignment=$\emptyset$\\
SolveSoduko(assignment)

\caption{start(Node n)}
\label{aa}
\end{algorithm}

\begin{algorithm}

if(assignment.isSolution())\\\hspace*{.3cm}
return assignment\\
else\\
Let V=getChildren(assignment)\\\hspace*{.3cm}
for each  $v \in V$\\\hspace*{.4cm}
if($consistent(v,d_{v}$) where $d_{v}\in D_V$\\\hspace*{.6cm}
V=$d_{v}$\\\hspace*{.6cm}
assignment.addVariable(V)\\\hspace*{.6cm}
SolveSoduko(assignment)\\\hspace*{.6cm}

\caption{SolveSoduko(assignment)}
\label{a}
\end{algorithm}