الصفحة الرئيسية>المتعلقة بالبرمجة>بايثون
تنزيل

سودوكو في عبوة بايثون

حل سودوكو ليس في بايثون، ولكن في حزم بايثون.

يعد حل إصدارات حزمة python من متطلباتك أمرًا مكتملًا NP، وفي أسوأ الحالات يعمل ببطء شديد. تعتبر لعبة Sudokus أيضًا NP-Complete، مما يعني أنه يمكننا حل لعبة Sudokus باستخدام عبوات بايثون.

كل خلية في شبكة سودوكو عبارة عن حزمة sudoku_{x}_{y} (0 مفهرسة)، والإصدار (1-9) هو القيمة الموجودة في الحقل، لذا يمكنك كتابة pyproject.toml والحزم المثبتة هي الحل. 

[ project ]
name = " sudoku "
version = " 1.0.0 "
dependencies = [
    " sudoku_3_1 == 2 " ,
    " sudoku_5_7 == 6 " ,
    " sudoku_0_7 == 5 "
    ...
]

الاستخدام

يمكنك كتابة سودوكو كملف CSV: 

 5,3,_,_,7,_,_,_,_
6,_,_,1,9,5,_,_,_
_,9,8,_,_,_,_,6,_
8,_,_,_,6,_,_,_,3
4,_,_,8,_,3,_,_,1
7,_,_,_,2,_,_,_,6
_,6,_,_,_,_,2,8,_
_,_,_,4,1,9,_,_,5
_,_,_,_,8,_,_,7,9

تحويله إلى متطلبات: 

python csv_to_requirements.py sudoku.csv requirements.in
 sudoku_0_0 == 5
sudoku_1_0 == 3
[...]
sudoku_7_8 == 7
sudoku_8_8 == 9

قم بحلها باستخدام مدير الحزم المفضل لديك، على سبيل المثال: 

uv pip compile --find-links packages/ --no-annotate --no-header requirements.in > requirements.txt

أو (بطيء) 

pip-compile --find-links packages/ --no-annotate --no-header requirements.in -o requirements.txt
 sudoku-0-0==5
sudoku-0-1==6
sudoku-0-2==1
sudoku-0-3==8
sudoku-0-4==4
[...]

تقديم الحل: 

python render_solution.py requirements.txt
 5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9

أو كخط واحد: 

$ python csv_to_requirements.py royle.csv - | uv pip compile --find-links packages/ --no-annotate --no-header - | python render_solution.py -
Resolved 81 packages in 126ms
5,3,4,6,7,8,9,1,2
6,7,2,1,9,5,3,4,8
1,9,8,3,4,2,5,6,7
8,5,9,7,6,1,4,2,3
4,2,6,8,5,3,7,9,1
7,1,3,9,2,4,8,5,6
9,6,1,5,3,7,2,8,4
2,8,7,4,1,9,6,3,5
3,4,5,2,8,6,1,7,9

المعيار 

 $ hyperfine --warmup 5 "uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in"
Benchmark 1: uv pip compile --find-links packages/ --no-index --no-annotate --no-header requirements.in
  Time (mean ± σ):      29.7 ms ±   1.6 ms    [User: 29.9 ms, System: 21.0 ms]
  Range (min … max):    27.5 ms …  35.0 ms    97 runs

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

في حين أن حل التبعية هو NP كامل وتكون خوارزمية الدعم الخاصة بها عادةً شكلاً من أشكال حل SAT، إلا أن مساحة المشكلة في الواقع أصغر بكثير: تعتمد الحزم عادةً على نطاق واحد لحزمة أخرى، وعادةً ما يتزايد هذا النطاق بشكل رتيب. لن تواجه أبدًا حالة أسية تقريبًا، حيث يمكن تنفيذ معظم الحلول في لغة بايثون دون التراجع. يتمثل عنق الزجاجة في الأداء بدلاً من ذلك في جلب البيانات الوصفية وتحليلها، وبالنسبة لبيثون على وجه التحديد، تقوم ببناء توزيعات المصدر.

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل