หน้าแรก>การเขียนโปรแกรมที่เกี่ยวข้อง>หลาม
ดาวน์โหลด

ซูโดกุในบรรจุภัณฑ์หลาม

แก้ซูโดกุไม่ใช่ในหลาม แต่ในแพ็คเกจหลาม

การแก้ไขเวอร์ชันของแพ็คเกจ python จากความต้องการของคุณนั้น NP-สมบูรณ์ ในกรณีที่แย่ที่สุดก็จะทำงานช้าแบบทวีคูณ ซูโดกุยังเป็น NP-complete อีกด้วย ซึ่งหมายความว่าเราสามารถแก้ซูโดกุได้ด้วยแพ็คเกจ Python

แต่ละเซลล์ในตารางซูโดกุคือแพ็คเกจ 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

หรือเป็น oneliner: 

$ 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 แต่ในความเป็นจริง พื้นที่ปัญหานั้นน้อยกว่ามาก แพ็คเกจมักจะขึ้นอยู่กับช่วงเดียวของแพ็คเกจอื่น และช่วงนั้นมักจะเพิ่มขึ้นแบบซ้ำซากจำเจ คุณแทบไม่เคยเจอกรณีเอ็กซ์โพเนนเชียลเลย ความละเอียดส่วนใหญ่ใน python สามารถทำได้โดยไม่ต้องย้อนรอยด้วยซ้ำ ปัญหาคอขวดของประสิทธิภาพคือการดึงและแยกวิเคราะห์ข้อมูลเมตาแทน และสำหรับ Python โดยเฉพาะการสร้างการกระจายแหล่งที่มา

ขยาย
ข้อมูลเพิ่มเติม
แอปที่เกี่ยวข้อง
แนะนำสำหรับคุณ
ข้อมูลที่เกี่ยวข้อง ทั้งหมด