ตัวแก้ Sudoku แบบเรียกซ้ำโดยใช้ Python
โปรแกรมแก้ Sudoku ที่ทำงานแบบวนซ้ำ ขอขอบคุณสำหรับความคิดเห็นของคุณเกี่ยวกับรูปแบบการเขียนโค้ดโครงสร้างและวิธีการปรับปรุง ขอบคุณมากสำหรับเวลาของคุณ.
โครงสร้างรหัส
Solver ทำงานโดยรับสตริง 81 หลักสำหรับการป้อนตัวต่อ Sudoku เลขศูนย์ถูกถ่ายเป็นเซลล์ว่าง มันแยกวิเคราะห์เป็นอาร์เรย์ Numpy ขนาด 9x9
get_candidatesฟังก์ชั่นสร้างรายชื่อของตัวเลขที่เป็นไปได้ในการกรอกข้อมูลแต่ละเซลล์ตามกฎของซูโดกุ (ไม่มีการทำซ้ำ 1-9 บาทพร้อมแถวคอลัมน์และ 3x3 ย่อยกริด)
solveฟังก์ชั่นหลักคือแก้ ขั้นแรกจะทิ้งผู้สมัครที่ไม่ถูกต้องด้วยfilter-candidatesฟังก์ชัน "ผู้สมัครที่ไม่ถูกต้อง" คือผู้ที่ถูกเติมลงในเซลล์ว่างทำให้เซลล์อื่นไม่มีผู้สมัครอีกต่อไปในตาราง Sudoku
หลังจากกรองผู้สมัครfill_singlesจะถูกเรียกให้เติมเซลล์ว่างที่มีผู้สมัครเหลืออยู่เพียงตัวเดียว หากกระบวนการนี้นำไปสู่ตาราง Sudoku ที่เต็มไปหมดระบบจะส่งคืนเป็นโซลูชัน มีประโยคที่จะส่งคืนNoneซึ่งใช้ในการย้อนกลับการเปลี่ยนแปลงโดยmake_guessฟังก์ชัน ฟังก์ชันนี้จะเติมเซลล์ว่างถัดไปที่มีจำนวนผู้สมัครน้อยที่สุดด้วยตัวเลือกหนึ่งซึ่งเป็นค่า "เดา" จากนั้นsolveจะเรียกซ้ำเพื่อค้นหาโซลูชันหรือไปยังตารางที่ไม่มีโซลูชัน (ซึ่งในกรณีนี้solveจะส่งคืนNoneและการเปลี่ยนแปลงการคาดเดาครั้งสุดท้ายจะถูกเปลี่ยนกลับ)
from copy import deepcopy
import numpy as np
def create_grid(puzzle_str: str) -> np.ndarray:
"""Create a 9x9 Sudoku grid from a string of digits"""
# Deleting whitespaces and newlines (\n)
lines = puzzle_str.replace(' ','').replace('\n','')
digits = list(map(int, lines))
# Turning it to a 9x9 numpy array
grid = np.array(digits).reshape(9,9)
return grid
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
subgrids = []
for box_i in range(3):
for box_j in range(3):
subgrid = []
for i in range(3):
for j in range(3):
subgrid.append(grid[3*box_i + i][3*box_j + j])
subgrids.append(subgrid)
return np.array(subgrids)
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
def is_valid_grid(grid : np.ndarray) -> bool:
"""Verify the input grid has a possible solution"""
candidates = get_candidates(grid)
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 0:
return False
return True
def is_solution(grid : np.ndarray) -> bool:
"""Verify if the input grid is a solution"""
if np.all(np.sum(grid, axis=1) == 45) and \
np.all(np.sum(grid, axis=0) == 45) and \
np.all(np.sum(get_subgrids(grid), axis=1) == 45):
return True
return False
def filter_candidates(grid : np.ndarray) -> list:
"""Filter input grid's list of candidates"""
test_grid = grid.copy()
candidates = get_candidates(grid)
filtered_candidates = deepcopy(candidates)
for i in range(9):
for j in range(9):
# Check for empty cells
if grid[i][j] == 0:
for candidate in candidates[i][j]:
# Use test candidate
test_grid[i][j] = candidate
# Remove candidate if it produces an invalid grid
if not is_valid_grid(fill_singles(test_grid)):
filtered_candidates[i][j].remove(candidate)
# Revert changes
test_grid[i][j] = 0
return filtered_candidates
def merge(candidates_1 : list, candidates_2 : list) -> list:
"""Take shortest candidate list from inputs for each cell"""
candidates_min = []
for i in range(9):
row = []
for j in range(9):
if len(candidates_1[i][j]) < len(candidates_2[i][j]):
row.append(candidates_1[i][j][:])
else:
row.append(candidates_2[i][j][:])
candidates_min.append(row)
return candidates_min
def fill_singles(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill input grid's cells with single candidates"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
any_fill = True
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
return grid
def make_guess(grid : np.ndarray, candidates=None) -> np.ndarray:
"""Fill next empty cell with least candidates with first candidate"""
grid = grid.copy()
if not candidates:
candidates = get_candidates(grid)
# Getting the shortest number of candidates > 1:
min_len = sorted(list(set(map(
len, np.array(candidates).reshape(1,81)[0]))))[1]
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == min_len:
for guess in candidates[i][j]:
grid[i][j] = guess
solution = solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid[i][j] = 0
def solve(grid : np.ndarray) -> np.ndarray:
"""Recursively find a solution filtering candidates and guessing values"""
candidates = filter_candidates(grid)
grid = fill_singles(grid, candidates)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid, candidates)
# # Example usage
# puzzle = """100920000
# 524010000
# 000000070
# 050008102
# 000000000
# 402700090
# 060000000
# 000030945
# 000071006"""
# grid = create_grid(puzzle)
# solve(grid)
```
คำตอบ
ฉันสามารถปรับปรุงประสิทธิภาพของโปรแกรมได้ประมาณ 900% โดยไม่ต้องทำความเข้าใจหรือเปลี่ยนอัลกอริทึมส่วนใหญ่ในเวลาประมาณหนึ่งชั่วโมง นี่คือสิ่งที่ฉันทำ:
ก่อนอื่นคุณต้องมีเกณฑ์มาตรฐาน ง่ายมากเพียงแค่ตั้งเวลาโปรแกรมของคุณ
start = time.time()
solve(grid)
print(time.time()-start)
บนคอมพิวเตอร์ของฉันใช้เวลาประมาณ 4.5 วินาที นี่คือพื้นฐานของเรา
สิ่งต่อไปคือโปรไฟล์ เครื่องมือที่ฉันเลือกคือ VizTracer ซึ่งพัฒนาขึ้นเอง :)https://github.com/gaogaotiantian/viztracer
VizTracer จะสร้างรายงาน HTML (หรือ json ที่สามารถโหลดโดย chrome :: // tracing) ของไทม์ไลน์ของการเรียกใช้โค้ดของคุณ ดูเหมือนว่าในเวอร์ชันดั้งเดิมของคุณ:
อย่างที่บอกมีการโทรเข้ามามากมาย สิ่งที่เราต้องทำคือหาว่าอะไรคือคอขวดตรงนี้ โครงสร้างไม่ซับซ้อนfill_singlesมีการเรียกใช้จำนวนมากและเราต้องซูมเข้าเพื่อตรวจสอบว่ามีอะไรอยู่ในนั้น
ชัดเจนมากว่าget_candidatesเป็นฟังก์ชันที่ทำให้เกิดเวลาfill_singlesส่วนใหญ่ซึ่งครอบครองไทม์ไลน์ส่วนใหญ่ นั่นคือฟังก์ชันที่เราต้องการพิจารณาก่อน
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
for i in range(9):
row_candidates = []
for j in range(9):
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
# If the case is filled take its value as the only candidate
if not grid[i][j]:
row_candidates.append(list(candidates))
else:
row_candidates.append([grid[i][j]])
grid_candidates.append(row_candidates)
return grid_candidates
สิ่งที่ดึงดูดสายตาของฉันเป็นอย่างแรกคือจุดจบของคุณที่ซ้อนกันเป็นวง คุณตรวจสอบว่าgrid[i][j]มีการเติมหรือไม่ ถ้าเป็นเช่นนั้นนั่นคือผู้สมัครเพียงคนเดียว อย่างไรก็ตามหากมีการเติมเต็มแสดงว่าไม่มีส่วนเกี่ยวข้องใดcandidatesๆ ซึ่งคุณคำนวณยากมากในการซ้อนกันของลูป
สิ่งแรกที่ฉันทำคือย้ายเช็คไปที่จุดเริ่มต้นของลูปสำหรับ
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = set(grid[i])
col = set(grid[:, j])
sub = set(subgrids[subgrid_index(i, j)])
common = row | col | sub
candidates = set(range(10)) - common
row_candidates.append(list(candidates))
การเพิ่มประสิทธิภาพนี้เพียงอย่างเดียวลดเวลาในการทำงานลงครึ่งหนึ่งตอนนี้เราอยู่ที่ประมาณ 2.3 วินาที
จากนั้นฉันสังเกตเห็นในการวนซ้ำของคุณคุณกำลังดำเนินการชุดซ้ำซ้อนจำนวนมาก แม้แต่ row / col / sub ก็ต้องคำนวณ 9 ครั้งเท่านั้นคุณกำลังคำนวณ 81 ครั้งซึ่งค่อนข้างแย่ ผมจึงย้ายการคำนวณออกจาก for loop
def get_candidates(grid : np.ndarray) -> list:
"""Get a list of candidates to fill empty cells of the input grid"""
def subgrid_index(i, j):
return (i//3) * 3 + j // 3
subgrids = get_subgrids(grid)
grid_candidates = []
row_sets = [set(grid[i]) for i in range(9)]
col_sets = [set(grid[:, j]) for j in range(9)]
subgrid_sets = [set(subgrids[i]) for i in range(9)]
total_sets = set(range(10))
for i in range(9):
row_candidates = []
for j in range(9):
if grid[i][j]:
row_candidates.append([grid[i][j]])
continue
# Row, column and subgrid digits
row = row_sets[i]
col = col_sets[j]
sub = subgrid_sets[subgrid_index(i, j)]
common = row | col | sub
candidates = total_sets - common
# If the case is filled take its value as the only candidate
row_candidates.append(list(candidates))
grid_candidates.append(row_candidates)
return grid_candidates
ซึ่งจะลดเวลาในการทำงานเหลือประมาณ 1.5 วินาที สังเกตว่าฉันยังไม่ได้พยายามทำความเข้าใจอัลกอริทึมของคุณ สิ่งเดียวที่ฉันทำคือใช้ VizTracer เพื่อค้นหาฟังก์ชันที่ต้องได้รับการปรับให้เหมาะสมและทำการแปลงตรรกะเดียวกัน ฉันปรับปรุงประสิทธิภาพขึ้นประมาณ 300% ในเวลา 15 นาที
ด้วยเหตุนี้ค่าใช้จ่ายของ VizTracer บน WSL จึงมีความสำคัญดังนั้นฉันจึงปิดการติดตามฟังก์ชัน C เหลือเพียงฟังก์ชัน Python และค่าใช้จ่ายประมาณ 10%
ตอนนี้get_candidatesได้รับการปรับปรุงแล้ว (แม้ว่าจะทำได้ดีกว่านี้) เราจำเป็นต้องถ่ายภาพให้ใหญ่ขึ้น สิ่งที่ฉันสังเกตได้จากผลของ VizTracer คือการfill_singlesโทรget_candidatesบ่อยมากเพียงแค่โทรมากเกินไป (นี่คือสิ่งที่สังเกตเห็นได้ยากใน cProfiler)
ขั้นตอนต่อไปคือการหาว่าเราfill_singlesโทรได้get_candidatesน้อยลงหรือไม่ ที่นี่ต้องมีความเข้าใจอัลกอริทึมในระดับหนึ่ง
while any_fill:
any_fill = False
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0:
grid[i][j] = candidates[i][j][0]
candidates = merge(get_candidates(grid), candidates)
any_fill = True
ดูเหมือนว่าที่นี่คุณพยายามกรอกข้อมูลในช่องว่างโดยมีผู้สมัครเพียงคนเดียวและคำนวณผู้สมัครของตารางทั้งหมดใหม่จากนั้นหาช่องว่างถัดไปที่มีผู้สมัครหนึ่งคน นี้เป็นวิธีการที่ถูกต้อง get_candidatesแต่เกิดจากสายมากเกินไปที่จะ หากลองคิดดูเมื่อเรากรอกตัวเลขnช่องว่างอื่น ๆ ทั้งหมดที่มีผู้สมัครเพียงคนเดียวที่ไม่nได้รับผลกระทบ ดังนั้นในช่วงหนึ่งของตารางเราสามารถลองเติมช่องว่างให้มากขึ้นได้ตราบใดที่เราไม่กรอกตัวเลขเดิมซ้ำสองครั้ง ด้วยวิธีนี้เราสามารถโทรได้get_candidatesน้อยลงซึ่งเป็นผู้บริโภคที่มีเวลามาก ฉันใช้ชุดเพื่อทำสิ่งนี้
filled_number = set()
for i in range(9):
for j in range(9):
if len(candidates[i][j]) == 1 and grid[i][j] == 0 and candidates[i][j][0] not in filled_number:
grid[i][j] = candidates[i][j][0]
filled_number.add(candidates[i][j][0])
any_fill = True
candidates = merge(get_candidates(grid), candidates)
สิ่งนี้ทำให้เวลาทำงานเป็น 0.9 วินาที
จากนั้นฉันดูรายงาน VizTracer ฉันรู้ว่าfill_singlesมักจะถูกเรียกโดยfilter_candidatesและสิ่งเดียวที่filter_candidatesสนใจคือfill_singlesส่งคืนตารางที่ถูกต้องหรือไม่ นี่เป็นข้อมูลที่เราอาจทราบตั้งแต่เนิ่นๆตราบใดที่ยังfill_singlesหาตำแหน่งที่ไม่มีผู้สมัคร ถ้าเรากลับก่อนเวลาเราไม่จำเป็นต้องคำนวณget_candidatesหลายครั้ง
ดังนั้นฉันจึงเปลี่ยนโครงสร้างโค้ดเล็กน้อยทำการfill_singlesส่งคืนNoneหากไม่พบตารางที่ถูกต้อง
ในที่สุดฉันก็สามารถทำเวลารันเป็น 0.5 วินาทีซึ่งเร็วกว่าเวอร์ชันเดิมถึง 900%
มันเป็นการผจญภัยที่สนุกจริงๆเพราะฉันกำลังทดสอบโปรเจ็กต์ VizTracer ของฉันและพยายามหาว่ามันมีประโยชน์หรือไม่ในการค้นหาส่วนที่เสียเวลา มันทำงานได้ดี :)
Numpyification
get_subgridsโดยพื้นฐานแล้วจะจัดเรียงอาร์เรย์ numpy ใหม่โดยมีจำนวนน้อยที่สุด สามารถทำได้ด้วย numpy เองตัวอย่างเช่น:
def get_subgrids(grid: np.ndarray) -> np.ndarray:
"""Divide the input grid into 9 3x3 sub-grids"""
swapped = np.swapaxes(np.reshape(grid, (3, 3, 3, 3)), 1, 2)
return np.reshape(swapped, (9, 9))
ข้อเสียที่ฉันคิดว่าคือการสลับแกนกลางสองแกนของอาร์เรย์ 4D นั้นเป็นการดัดความคิดเล็กน้อย
ประสิทธิภาพ
get_candidatesเวลาเกือบทั้งหมดจะใช้เวลาในการ ฉันคิดว่าสาเหตุหลัก ๆ คือ:
- มันถูกเรียกบ่อยเกินไป ตัวอย่างเช่นหลังจากกรอกข้อมูลในเซลล์ (เช่นใน
fill_singles) แทนที่จะคำนวณผู้สมัครใหม่ตั้งแต่ต้นการลบค่าใหม่ออกจากผู้สมัครในแถว / col / house เดียวกันจะเร็วกว่า - หากมีการเติมเซลล์รายชื่อผู้สมัครจะเป็นเพียงค่าที่กรอกข้อมูล แต่การคำนวณชุดที่มีราคาแพงก็ทำได้อยู่ดี เป็นเรื่องง่ายที่จะหลีกเลี่ยงเพียงแค่ย้ายคำสั่งเหล่านั้นไปไว้ในไฟล์
if.
ประสิทธิภาพของอัลกอริทึม
โปรแกรมแก้ปัญหานี้ใช้ประโยชน์จาก Naked Singles เป็น "เทคนิคการเผยแผ่" เท่านั้นการเพิ่ม Hidden Singles ถือเป็นประสบการณ์ที่ยิ่งใหญ่มากสำหรับนักแก้ปัญหา