Hướng dẫn fastest sudoku solver algorithm python - thuật toán giải sudoku nhanh nhất python
|
Tuần trước chúng tôi đã thấy cách thực hiện một người giải quyết Sudoku bằng Python. Ý tưởng là để lấp đầy các ứng cử viên rõ ràng nhất cho các ô trống và sau đó đoán cho một ô trống và lặp lại quá trình đệ quy, quay lại khi một dự đoán dẫn đến một lưới không có giải pháp. Show
Mặc dù quá trình này rất đơn giản, nhưng nó có nhược điểm là sản xuất quá nhiều kết hợp các giải pháp có thể. Trong thực tế, nó không đủ hiệu quả để giải các câu đố Sudoku khó hơn trong một khoảng thời gian hợp lý. Tuần này, chúng tôi sẽ thấy cách cải thiện khi triển khai tuần trước để tạo ra một người giải quyết hiệu quả hơn. Người giải quyết ban đầuChúng ta có thể thấy cách giải quyết đầu tiên hoạt động bằng cách kiểm tra mã của nó: def solve(grid):
grid = fill_singles(grid)
if is_solution(grid):
return grid
if not is_valid_grid(grid):
return None
return make_guess(grid)Nó bắt đầu bằng cách lấp đầy các ô trống có một ứng cử viên duy nhất theo các quy tắc của Sudoku (không lặp lại bất kỳ chữ số nào từ 1 đến 9 trong bất kỳ hàng, cột hoặc lưới phụ). Nó trả về một lưới hoàn toàn được lấp đầy khi nó tìm thấy. Để báo hiệu không giải quyết được lưới, nó trả về def filtered_solve(grid):
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)1. Việc không có được giải pháp diễn ra khi một tế bào không có ứng viên nào có thể được tìm thấy. Cuối cùng, nó đoán để lấp đầy ô trống tiếp theo với một ứng cử viên hợp lý để lặp lại quy trình (def filtered_solve(grid):
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)2 gọi def filtered_solve(grid):
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)3, tạo ra một quy trình đệ quy).Độ phức tạp theo cấp số nhânVấn đề với thuật toán cuối cùng là nó sẽ thử nhiều kết hợp ứng viên có thể. Như một ước tính đơn giản, hãy để Giả sử một nửa các ô (khoảng 40) trống và trung bình họ có 4 ứng cử viên có thể. Trong trường hợp đó, chúng tôi nói về thuật toán phải kiểm tra và quay lại hàng nghìn tỷ kết hợp có thể (9!^4). Rõ ràng, nó sẽ không tìm thấy một giải pháp trong bất kỳ khoảng thời gian hợp lý nào. Vấn đề ở đây là sự kết hợp của các ứng cử viên có thể trên lưới. Nó tăng theo cấp số nhân. Chúng ta sẽ thấy một cách để cắt giảm số lượng kết hợp để tìm giải pháp.combinations of possible candidates on the grid. It increases exponentially. We will see of a way to cut down on the number of combinations to find a solution. Thuật toán mới: Lọc ứng viênNhững gì chúng tôi sẽ làm sẽ là để lọc các ứng cử viên trước khi sử dụng chúng để đoán giá trị của các ô trống. Theo quy trình lọc này, chúng tôi sẽ giảm đáng kể số lượng kết hợp ứng cử viên có thể. Thuật toán mới này được thực hiện như sau: def filtered_solve(grid):
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)Có hai sự khác biệt chính. Đầu tiên, chúng tôi đã thêm một bộ lọc các ứng cử viên với chức năng def filtered_solve(grid):
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)4. Tiếp theo, chúng tôi đã sửa đổi các hàm def filtered_solve(grid):
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)5 và def filtered_solve(grid):
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)2 để chấp nhận các def filtered_solve(grid):
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)7 được lọc này làm tham số. Hãy cùng xem chi tiết các sửa đổi cần thiết.Lọc ứng viênChúng tôi sẽ lọc các ứng cử viên bằng cách điền vào mỗi ô trống với từng ứng cử viên của mình, mỗi lần một. Sau đó, chúng tôi sẽ kiểm tra xem lưới mới này, bao gồm giá trị ứng cử viên duy nhất, dẫn đến một lưới không có giải pháp (một lưới có ô không có ứng viên có thể). Nếu trường hợp đó, giá trị ứng cử viên của người Viking sẽ bị xóa khỏi danh sách các ứng cử viên có thể cho tế bào đó. from copy import deepcopy
def filter_candidates(grid):
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_candidatesHãy cùng xem cách thức hoạt động của điều này với câu đố tuần trước. puzzle = """043080250
600000000
000001094
900004070
000608000
010200003
820500000
000000005
034090710"""Và các ứng cử viên của nó: >>> candidates = get_candidates(grid) [[[1, 7], [4], [3], [9, 7], [8], [9, 6, 7], [2], [5], [1, 6, 7]], [[6], [8, 9, 5, 7], [1, 2, 5, 7, 8, 9], [9, 3, 4, 7], [2, 3, 4, 5, 7], [2, 3, 5, 7, 9], [8, 1, 3], [8, 3], [8, 1, 7]], [[2, 5, 7], [8, 5, 7], [8, 2, 5, 7], [3, 7], [2, 3, 5, 6, 7], [1], [8, 3, 6], [9], [4]], [[9], [8, 5, 6], [8, 2, 5, 6], [1, 3], [1, 3, 5], [4], [8, 1, 5, 6], [7], [8, 1, 2, 6]], [[2, 3, 4, 5, 7], [5, 7], [2, 5, 7], [6], [1, 3, 5, 7], [8], [1, 4, 5, 9], [2, 4], [1, 2, 9]], [[4, 5, 7], [1], [8, 5, 6, 7], [2], [5, 7], [9, 5, 7], [4, 5, 6, 8, 9], [8, 4, 6], [3]], [[8], [2], [1, 9, 6, 7], [5], [1, 3, 4, 6, 7], [3, 6, 7], [9, 3, 4, 6], [3, 4, 6], [9, 6]], [[1, 7], [9, 6, 7], [1, 9, 6, 7], [1, 3, 4, 7, 8], [1, 2, 3, 4, 6, 7], [2, 3, 6, 7], [3, 4, 6, 8, 9], [2, 3, 4, 6, 8], [5]], [[5], [3], [4], [8], [9], [2, 6], [7], [1], [8, 2, 6]]] Bây giờ, hãy để chúng tôi xem có bao nhiêu ứng cử viên chúng tôi có sau khi lọc: >>> filtered_candidates = filter_candidates(grid) [[1], [4], [3], [9], [8], [6], [2], [5], [6, 7]] [[6], [8, 9, 5, 7], [5, 7, 8, 9], [4], [2, 4, 5], [2, 5], [8, 1, 3], [8, 3], [1, 7]] [[2], [8, 5], [8, 5, 7], [3, 7], [3, 5, 6], [1], [8, 6], [9], [4]] [[9], [8, 5, 6], [8, 2, 5, 6], [1, 3], [1, 3, 5], [4], [8, 1, 5, 6], [7], [8]] [[3], [5, 7], [2, 5, 7], [6], [1, 3, 5, 7], [8], [1, 4, 9], [2, 4], [1, 2, 9]] [[4], [1], [8, 5, 6, 7], [2], [5, 7], [9, 5, 7], [5, 6, 8, 9], [8, 6], [3]] [[8], [2], [1, 9, 6], [5], [1, 3, 4, 6, 7], [3, 6, 7], [9, 3, 4, 6], [3, 4, 6], [9, 6]] [[7], [9, 6], [1, 9, 6], [1, 4], [1, 2, 3, 4, 6], [2, 3, 6], [3, 4, 6, 8, 9], [2, 3, 4, 6, 8], [5]] [[5], [3], [4], [8], [9], [2, 6], [7], [1], [2, 6]] Không tính các tế bào đầy (những người ban đầu có một ứng cử viên duy nhất), chúng tôi đã giảm tổng số ứng cử viên từ 185 xuống 140. Chúng tôi chuyển từ trung bình 3,5 ứng cử viên trên mỗi ô trống xuống còn khoảng 2,5. Đối với trường hợp cụ thể này, bằng một bộ lọc duy nhất, chúng tôi đã chuyển từ khoảng 10^28 kết hợp có thể đến 10^20. Chúng ta có thể thấy sự quan tâm của việc lọc cho thuật toán đệ quy của chúng ta. Bao gồm các ứng cử viên được lọcSửa đổi nhẹ sẽ là cần thiết cho các chức năng def filtered_solve(grid):
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)2 và def filtered_solve(grid):
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)5 để bao gồm các ứng cử viên được lọc làm tham số.def make_guess(grid, candidates=None):
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 = filtered_solve(grid)
if solution is not None:
return solution
# Discarding a wrong guess
grid[i][j] = 0Những thay đổi trên def filtered_solve(grid):
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)2 là nhỏ. Chúng tôi chỉ bao gồm def filtered_solve(grid):
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)7 dưới dạng tham số và tính toán nó nếu nó được truyền như một tham số. Sự khác biệt nhỏ thứ hai là chúng tôi gọi from copy import deepcopy
def filter_candidates(grid):
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_candidates2, người giải quyết mới của chúng tôi, đã đệ quy ở đây.Những thay đổi trên def filtered_solve(grid):
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)5 là tương tự nhưng chúng tôi cũng yêu cầu hàm trợ giúp, from copy import deepcopy
def filter_candidates(grid):
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_candidates4.def fill_singles(grid, candidates=None):
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 gridHàm from copy import deepcopy
def filter_candidates(grid):
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_candidates4 được gọi để cập nhật danh sách các ứng cử viên sau khi mỗi ô được điền. Chúng tôi làm như vậy bằng cách so sánh danh sách các ứng cử viên thông thường với danh sách được lọc và lấy danh sách các ứng cử viên ngắn hơn cho mỗi ô:def merge(candidates_1, candidates_2):
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_minVới điều này, chúng tôi đã kết thúc với tất cả các thay đổi cần thiết cho người giải quyết được cải thiện! Phần còn lại của các chức năng trợ giúp đã thay đổi. Hãy chắc chắn để kiểm tra bộ giải ban đầu để được giải thích chi tiết. Hãy cùng xem cách thức giải quyết mới hoạt động. Giải một câu đố Sudoku cứngTôi không đủ quen thuộc với Sudoku để đủ điều kiện câu đố này như một câu đố khó khăn, nhưng tôi đã xác minh rằng tuần trước, giải quyết của họ không có khả năng giải quyết nó. Câu đố (hãy nhớ rằng mỗi số 0 đại diện cho một ô trống): puzzle = """100920000
524010000
000000070
050008102
000000000
402700090
060000000
000030945
000071006"""Và giải pháp của nó bằng cách sử dụng from copy import deepcopy
def filter_candidates(grid):
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_candidates2:def filtered_solve(grid):
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)0Giải pháp chính xác! Mặc dù phải mất vài giây để có được một giải pháp, đây là một cải tiến lớn so với người giải quyết ban đầu. Bạn có thể thử sử dụng nó để giải câu đố này để so sánh. Về phía tôi, tôi đã xác minh rằng nó không thể giải quyết câu đố này ngay cả sau vài phút. Phần thưởng: Bạn có thể tìm thấy mã hoàn chỉnh của cả hai người giải quyết ở đây. You can find the complete code of both solvers here. Sudoku giải quyết nhanh nhất là gì?Theo Guinness World Records, thời gian nhanh nhất để hoàn thành một câu đố Sudoku rất dễ dàng của Sudoku là 1 phút 23,93 giây. Kỷ lục được thiết lập vào ngày 20 tháng 5 năm 2006 bởi Thomas Snyder, một nhà vô địch Sudoku của Mỹ. Làm thế nào để Thomas Snyder giải các câu đố Sudoku nhanh như vậy, và làm thế nào bạn có thể giải các câu đố Sudoku nhanh hơn?1 minute 23.93 seconds. The record was set on May 20, 2006 by Thomas Snyder, an American Sudoku champion. How does Thomas Snyder solve Sudoku puzzles so fast, and how can you solve Sudoku puzzles faster?
Thuật toán tốt nhất để giải quyết Sudoku là gì?Thuật toán quay lại là thuật toán nhanh nhất để giải các câu đố Sudoku, nó là loại nhanh nhất so với hai phương pháp khác.Ngoài ra, hãy lưu ý rằng mỗi thuật toán nhanh hơn với các vấn đề khó khăn hơn so với các vấn đề dễ dàng hơn. is the fastest algorithm to solve sudoku puzzles, It is by far the fastest compared to the other two methods. Also, let's note that each algorithm was faster with harder problems than with easier problems.
Quy tắc 45 trong Killer Sudoku là gì?Quy tắc 45 Tất cả các số trong một hàng đã cho, cột hoặc NONET nên thêm tới 45. Quy tắc này cũng có thể được sử dụng các câu đố nhỏ hơn: số là 21 cho câu đố 6x6 và 10 cho câu đố 4x4.Hãy xem lưới Sudoku sát thủ dưới đây.All the numbers in a given row, column or nonet should add up to 45. This rule can also be used smaller puzzles: the number is 21 for a 6x6 puzzle and 10 for a 4x4 puzzle. Take a look at the Killer Sudoku grid below.
Ai là người chơi Sudoku nhanh nhất?Nhà vô địch thế giới, Thomas Snyder, hiện đang giữ kỷ lục Guinness về giải pháp nhanh nhất.Anh ta được biết là đã mất chưa đầy 90 giây để giải câu đố cấp độ kỹ năng 'rất dễ dàng'.Thomas Snyder, currently holds the Guinness World Record for the fastest solution. He is known to have taken less than 90 seconds to solve a 'very easy' skill level sudoku puzzle. |
