Sudoku Solver بالعربي

333

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

الترميز Notations

لعبة السودوكو لمن لا يعرفها تبدو كالتالي

نتيجة بحث الصور عن سودوكو

في البداية نحتاج لترميز كل مربع لتمييزه عن بقية المربعات فنختار الحروف للصفوف والأرقام للأعمدة فتكون الصفوف ABCDEFGHI والأعمدة 123456789 فيكون الناتج لدينا المربع التالي:

A1 A2 A3| A4 A5 A6| A7 A8 A9      
B1 B2 B3| B4 B5 B6| B7 B8 B9
C1 C2 C3| C4 C5 C6| C7 C8 C9 
---------+---------+--------  
D1 D2 D3| D4 D5 D6| D7 D8 D9    
E1 E2 E3| E4 E5 E6| E7 E8 E9     
F1 F2 F3| F4 F5 F6| F7 F8 F9  
---------+---------+--------
G1 G2 G3| G4 G5 G6| G7 G8 G9    
H1 H2 H3| H4 H5 H6| H7 H8 H9    
I1 I2 I3| I4 I5 I6| I7 I8 I9   

سنسمي المربع الصغير صندوق أي أن A1 تعتبر صندوق له وحدات units هي عدد الصناديق الصغيرة في المربع ال3*3 و 20 قرين peers الرقم الواحد لا يجب أن يتكرر مرتين في المربع ال3*3 أو في الpeers. فمثلا لو فرضنا أننا نريد تحديد الوحدات والpeers للصندوق C2 نجد أنهم كالتالى:

الوحدات :

A1 A2 A3 
B1 B2 B3 
C1 C2 C3

وال peers:

C1  C2 C3 C4 C5 C6 C7 C8 C9

    A2
    B2
    C2
    D2
    E2
    F2
    G2
    H2
    I2        

والآن نقوم بكتابة كود البايثون الذي يقوم بتجهيز وترميز صناديق السودوكو وأيضا تحديد الوحدات وال peers لكل صندوق على حدى.

#function for putting A with 1 to get A1, B1,etc..
def cross(A, B):
    "Cross product of elements in A and elements in B."
    return [a+b for a in A for b in B]

digits   = '123456789'
rows     = 'ABCDEFGHI'
cols     = digits
squares  = cross(rows, cols)
unitlist = ([cross(rows, c) for c in cols] +
            [cross(r, cols) for r in rows] +
            [cross(rs, cs) for rs in ('ABC','DEF','GHI') for cs in ('123','456','789')])
#detecting units for each square
units = dict((s, [u for u in unitlist if s in u]) 
             for s in squares)
#detecting peers for each square
peers = dict((s, set(sum(units[s],[]))-set([s]))
             for s in squares)

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

فمثلا في الصورة الأولى المعروضة في أول المقال يكون أول صندوق أعلى يسار الpuzzle اسمه A1 ولكن قيمته 5 ال dict يسمح لك بربط قيمة ال A1 بال 5.

مثال :

{'my_dict = {1: 'apple', 2: 'ball

فيسمى ال1 بال key أي المفتاح  و apple بال value أو القيمة.

بمعنى أن السطر (dict((s, […]) for s in squares ينشيء dict يربط كل صندوق صغير بقيمة موجودة في ال list […].

وهذا الجزء […] بداخله [u for u in unitlist if s in u] يعني أن القيمة المربوط بها تكون هي قائمة الوحدات حيث S هي أحد عناصر u.

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

الوحدات هي dict فيه كل صندوق مرتبط بباقي الصناديق الموجودة في المربع 3*3.

والسطر الثاني يقول ال peesr هي dict فيه كل صندوق مرتبط بمجموعة من الصناديق مكونة بواسطة اتحاد مربعات وحدات s بدون s نفسها.

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

def test():
    "A set of unit tests."
    assert len(squares) == 81
    assert len(unitlist) == 27
    assert all(len(units[s]) == 3 for s in squares)
    assert all(len(peers[s]) == 20 for s in squares)
    assert units['C2'] == [['A2', 'B2', 'C2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2'],
                           ['C1', 'C2', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9'],
                           ['A1', 'A2', 'A3', 'B1', 'B2', 'B3', 'C1', 'C2', 'C3']]
    assert peers['C2'] == set(['A2', 'B2', 'D2', 'E2', 'F2', 'G2', 'H2', 'I2',
                               'C1', 'C3', 'C4', 'C5', 'C6', 'C7', 'C8', 'C9',
                               'A1', 'A3', 'B1', 'B3'])
    print 'All tests pass.'

الآن بما أن لدينا الوحدات وال peers نحتاج إلى شيئين رئيسيين:

الأول تمثيل نصي للغز كهذا :

4 . . |. . . |8 . 5 
. 3 . |. . . |. . . 
. . . |7 . . |. . . 
------+------+------
. 2 . |. . . |. 6 . 
. . . |. 8 . |4 . . 
. . . |. 1 . |. . . 
------+------+------
. . . |6 . 3 |. 7 . 
5 . . |2 . . |. . . 
1 . 4 |. . . |. . .

وتمثيل حقيقي لحالة اللغز والحلول الممكنة له أي مكان كل نقطة نكتب كل الأرقام من 1 ل 9 وهي جميع الاحتمالات الممكنة للخانة الواحدة.

4 123456789 123456789 |123456789 123456789 123456789 |8 123456789 5 
123456789 3 123456789 |123456789 123456789 123456789 |123456789 123456789 123456789 
123456789 123456789 123456789 |7 123456789 123456789 |123456789 123456789 123456789 
------------------------------+----------------------+-----------------------------
123456789 2 123456789 |123456789 123456789 123456789 |123456789 6 123456789 
123456789 123456789 123456789 |123456789 8 123456789 |4 123456789 123456789 
123456789 123456789 123456789 |123456789 1 123456789 |123456789 123456789 123456789 
------------------------------+----------------------+-----------------------------
123456789 123456789 123456789 |6 123456789 3 |123456789 7 123456789 
5 123456789 123456789 |2 123456789 123456789 |123456789 123456789 123456789 
1 123456789 4 |123456789 123456789 123456789 |123456789 123456789 123456789 

الآن نقوم بإنشاء ال puzzle وهو عبارة عن كل رمز مربوط بالقيمة الخاصة به أي فكرة ال dict التي تكلمنا عنها سابقا فمثلا الA1 : 5 وال A2 : 123456789 وهكذا..

def parse_grid(grid):
    """Convert grid to a dict of possible values, {square: digits}, or
    return False if a contradiction is detected."""
    ## To start, every square can be any digit; then assign values from the grid.
    values = dict((s, digits) for s in squares)
    for s,d in grid_values(grid).items():
        if d in digits and not assign(values, s, d):
            return False ## (Fail if we can't assign d to square s.)
    return values

def grid_values(grid):
    "Convert grid into a dict of {square: char} with '0' or '.' for empties."
    chars = [c for c in grid if c in digits or c in '0.']
    assert len(chars) == 81
    return dict(zip(squares, chars))

امتداد القيود أو Constraint Propagation :

بالنسبة لأولئك الذين لديهم خبرة في حل السودوكو نحن نعرف قاعدتين رئيسيتين غاية في الأهمية لإيجاد الحل بسرعة وتوفير الوقت :

(1)إذا كان هناك صندوق بالفعل لديه قيمة واحدة مثل A1 : 5 بالتالي قم بإزالة ال 5 من جميع ال peers.

(2)إذا كنت تقف مثلا في A2 وهي فارغة وكل الأماكن الفارغة في peers A2 لا تقبل الرقم 9 إذا اجعل قيمة A2: 9.

دالة assign هي دالة مسئولة عن التحقق من منطقية الوضع فمثلا لو كان عندك A1: 7 وحاولت وضع A2: 7 فستكون النتيجة سلبية أي أن هذا الإجراء لا يجوز.

اتضح أن الطريق الأفضل ليس تحديد قيمة لكل صندوق بل تقليل القيم المحتملة لكل صندوق برفض واستبعاد القيم التي ظهرت بالفعل في ال peers أو ال unit وبالتالي تكون عملية الAssign هي عملية إزالة elimination للعديد من الأرقام وفي النهاية تعيين assign قيمة واحدة متاحة.

def assign(values, s, d):
    """Eliminate all the other values (except d) from values[s] and propagate.
    Return values, except return False if a contradiction is detected."""
    other_values = values[s].replace(d, '')
    if all(eliminate(values, s, d2) for d2 in other_values):
        return values
    else:
        return False

def eliminate(values, s, d):
    """Eliminate d from values[s]; propagate when values or places <= 2.
    Return values, except return False if a contradiction is detected."""
    if d not in values[s]:
        return values ## Already eliminated
    values[s] = values[s].replace(d,'')
    ## (1) If a square s is reduced to one value d2, then eliminate d2 from the peers.
    if len(values[s]) == 0:
	return False ## Contradiction: removed last value
    elif len(values[s]) == 1:
        d2 = values[s]
        if not all(eliminate(values, s2, d2) for s2 in peers[s]):
            return False
    ## (2) If a unit u is reduced to only one place for a value d, then put it there.
    for u in units[s]:
	dplaces = [s for s in u if d in values[s]]
	if len(dplaces) == 0:
	    return False ## Contradiction: no place for this value
	elif len(dplaces) == 1:
	    # d can only be in one place in unit; assign it there
            if not assign(values, dplaces[0], d):
                return False
    return values

الآن نستطيع طباعة ال puzzle لنرى نتيجة الelimination

def display(values):
    "Display these values as a 2-D grid."
    width = 1+max(len(values[s]) for s in squares)
    line = '+'.join(['-'*(width*3)]*3)
    for r in rows:
        print ''.join(values[r+c].center(width)+('|' if c in '36' else '')
                      for c in cols)
        if r in 'CF': print line
    print

الآن دعنا نقوم بحل سودوكو من المستوى easy puzzle.

سنقوم بإدخال ال puzzle بالشكل التالي مثلا لو A1: 5 وA2 مطلوب قيمتها أي فارغة وA3 ب 6 نقوم بكتابتها بالشكل التالي:

"5.6"

ومن ثم نقوم بإدخال السودوكو بالشكل التالي

>>> grid1 = '003020600900305001001806400008102900700000008006708200002609500800203009005010300'

>>> display(parse_grid(grid1))
4 8 3 |9 2 1 |6 5 7 
9 6 7 |3 4 5 |8 2 1 
2 5 1 |8 7 6 |4 9 3 
------+------+------
5 4 8 |1 3 2 |9 7 6 
7 2 9 |5 6 4 |1 3 8 
1 3 6 |7 9 8 |2 4 5 
------+------+------
3 7 2 |6 8 9 |5 1 4 
8 1 4 |2 5 3 |7 6 9 
6 9 5 |4 1 7 |3 8 2

في هذه الحالة تم حل ال puzzle لأنها في ال easy mode ولكن ماذا إن كانت أصعب بقليل مثل هذه مثلا:

>>> grid2 = '4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'

>>> display(parse_grid(grid2))

تكون النتيجة كالآتي :

   4      1679   12679  |  139     2369    269   |   8      1239     5    
 26789     3    1256789 | 14589   24569   245689 | 12679    1249   124679 
  2689   15689   125689 |   7     234569  245689 | 12369   12349   123469 
------------------------+------------------------+------------------------
  3789     2     15789  |  3459   34579    4579  | 13579     6     13789  
  3679   15679   15679  |  359      8     25679  |   4     12359   12379  
 36789     4     56789  |  359      1     25679  | 23579   23589   23789  
------------------------+------------------------+------------------------
  289      89     289   |   6      459      3    |  1259     7     12489  
   5      6789     3    |   2      479      1    |   69     489     4689  
   1      6789     4    |  589     579     5789  | 23569   23589   23689  

بالتالي لازال أمامنا طريق طويل لحل puzzle كهذه فهناك 61 صندوق غير متأكدين منهم بالتالي يمكننا استخدام تقنيات أخرى كتقنية التوائم المجردة أو Naked twins والتي تعتمد على البحث عن صندوقين في نفس الوحدة لديهم هما الاثنين نفس الرقمين المحتملين مثال:

لو كانت A5: 26 , A6 : 26 بالتالي بإمكاننا استنتاج أن 2 و 6 في هذين الصندوقين فقط  على الرغم من عدم معرفتنا أيهما يقع أين .. ومن ثم إزالتهما من احتمالات بقية الخانات في الصف والعمود والمربع 3*3 بإمكاننا استخدام سطر كود بسيط لتحديد شيء كهذا elif len(values[s]) == 2.

يعد كتابة أكواد لطرق كهذه طريقا ممكنا ولكنه ستطلب مئات الأسطر من الأكواد ولن نستطيع أبدا التأكد من إمكانية حل اللغز..

ال Search

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

كمثال دعنا نفترض أن A2 لديها اربع احتمالات (1679) و A3 لديها 5 احتمالات (12679) معا يصبحون 20 احتمالا وإذا استمررنا في الضرب سيكون لدينا  احتمال للpuzzle كاملة.

في الحقيقة أمامنا خيارين للتعامل مع هذا الكم الهائل من الاحتمالات الأول أن نتعامل بإسلوب القوة الغاشمة. افترض أن لدينا برنامج رائع يقوم بتنفيذ أمر واحد لتقييم موقف كامل وأن لدينا إمكانية للوصول إلى تقنية حوسبة من الجيل التالي دعنا نقول مثلا 10GHz بروسيسور ودعنا نفترض أيضا أن لدينا المقدرة لشراء مليون بروسيسور بنفس القدرة وأثناء تسوقنا استطعنا الحصول على آلة زمن والعودة بالزمن للخلف 13 بليون سنة .. لبداية الكون ومن هناك استطعنا بشكل ما أن نجعل برنامجنا يبدأ بالعمل في هذه الحالة سنكون الآن قد حسبنا ما يقارب 1% فقط من احتمالات هذه الpuzzle الواحدة!!!

الخيار الثاني  هو بطريقة ما نقوم بحساب أكثر من احتمال في مرة واحدة صحيح أن هذا يبدو مستحيلا ولكن لحسن الحظ هذا تماما ما يفعله ال Constraint propagation حيث نكون غير مضطرين لتجربة جميع الاحتمالات بل يكفي اختيار احتمال واحد ثم القيام بإزالة بعض الاحتمالات الأخرى بناء عليه. على سبيل المثال، يحتوي الصندوق H7 من هذا اللغز على احتمالين ، 6 و 9. يمكننا أن نحاول 9 ونرى بسرعة وجود تناقض. هذا يعني أننا استبعدنا ليس مجرد احتمال واحد ، ولكن نصف خيارات 4 * 1038 بالكامل.

في الواقع، اتضح أنه لحل هذا اللغز بالتحديد, نحتاج إلى النظر في 25 احتمالا فقط وعلينا فقط البحث في احتمالات 9 خانات من ال61 خانة الغير مملوءة ويقوم ال constraint propagation.

لحل 95 hard puzzle في المتوسط نحتاج إلى الأخذ بالاعتبار 64 احتمالا للpuzzle الواحدة وعلى أي حال علينا البحث في 16 صندوق على الأقل.

ما هي خوارزمية البحث ؟ 

في البداية علينا التأكد من أننا لم نصل للحل أو لتناقض في الحل على حد السواء إذا لم تكن هذه هي الحالة نقوم باختيار صندوق فارغ والتفكير في جميع القيم الممكنة له نقوم بتجربة احتمال واحد في كل مرة وبداية البحث من النتيجة الحاصلة بطريقة أخرى بإمكاننا القول أننا نبحث عن قيمة d بحيث يمكننا البحث بنجاح عن حل من نتيجة تعيين المربع s إلى d. إذا أدى البحث لوضع فاشل وفاشل هنا تعني متناقض نقوم بالعودة وتجربة قيمة أخرى لل d يسمى هذا البحث بالبحث المتكرر Recursive Search  ويطلق عليه depth first search لأننا ندرس جميع الاحتمالات ل  قبل أن نتحرك لقيمة أخرى لل s

ولتجنب مضاعفات تداخل البيانات نقوم بعمل نسخة من القيم لكل مرة نقوم فيها بعملية البحث وبهذه الطريقة، يكون كل فرع من فروع البحث مستقلاً ولا يحدث خلط بينه وبين فرع آخر. لهذا اختار المؤلف وضع قيم السودكو على هيئة String كي يستطيع نسخهم بالأمر  الأمر الذي يجعل عملية النسخ بسيطة وعملية فإذا كتبها ك أرقام أو ك list سيضطر لاستخدام  وهو أمر أقل في الكفاءة.

أما البديل لهذا فهو متابعة الحلول وتخزين كل تغيير في كل احتمال ثم تغييرها جميعا عندما تصل لطريق مسدود وهو ما يسمى بالBack tracking search واستخدامه يكون منطقيا في حالتنا لأن كل تغيير واحد يؤدي إلى تغييرات كامل في هيكل احتمالات الpuzzle ولكنه أكثر تعقيدا لهذا لن نستخدمه هنا.

هناك خيارين علينا العناية بهما أثناء محاولة كتابة كود ال search:

الخيار الأول ترتيب المتغيرات variable ordering أي المتغيرات أو الصناديق نبدأ بها أولا و

الخيار الثاني ترتيب القيم value ordering أي رقم نجربه أولا

بالنسبة للخيار الأول سنستخدم heuristic شائع يسمى minimum remaining values ما يعني أن نختار الصندوق ذو الاحتمالات الأقل.

لماذا ؟

تخيل أننا اخترنا B3 التي لديها 7 احتمالات عندها احتمال أن نكون مخطئين هو 6/7 في حين لو اخترنا G2 الذي يمتلك احتمالين فقط فعندها احتمال الخطأ يكون 1/2 بالتالي نختار الصندوق ذو الاحتمالات الأقل كي يكون احتمال أن نكون مخطئين أقل.

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

الآن نكون قد أصبحنا مستعدين لكتابة دالة الحل من خلال كتابة دالة البحث دعنا نرى كيف:

def solve(grid): return search(parse_grid(grid))

def search(values):
    "Using depth-first search and propagation, try all possible values."
    if values is False:
        return False ## Failed earlier
    if all(len(values[s]) == 1 for s in squares): 
        return values ## Solved!
    ## Chose the unfilled square s with the fewest possibilities
    n,s = min((len(values[s]), s) for s in squares if len(values[s]) > 1)
    return some(search(assign(values.copy(), s, d)) 
		for d in values[s])

def some(seq):
    "Return some element of seq that is true."
    for e in seq:
        if e: return e
    return False

that’s it!

بهذا يكون الكود قد انتهى وبهذا نكون قد بنينا Sudoku Solver كامل في صفحة واحدة تقريبا.

“المقال مترجم عن مقالة لبيتر نورفيج سيتم ذكرها في المصادر مع بعض التعديلات حسب الحاجة”

 

 

مصدر مصدر1
تعليقات