Đệ quy Sudoku của Python với Lỗi Backtracking Brute Force

Question

Tôi đang làm một bộ giải đố Sudoku cho bài tập về nhà, nhưng tôi đang gặp phải một số khó khăn. Mã ngay bây giờ chu kỳ qua các giải pháp, mặc dù nó đạt đến nó cho các câu đố dễ dàng, và cho các câu đố khó khăn hơn, nó bị mắc kẹt với một số 9 không có lý do rõ ràng. Tôi sẽ đánh giá cao sự giúp đỡ nào về điều này. (check_cell xác định xem vị trí có hợp lệ hay không.)

1. Tính năng backtracking được triển khai chính xác trong mã này và nếu không, cách đó sẽ được khắc phục như thế nào?
2. Làm cách nào để ngăn người giải quyết không bị đóng băng? Nó giải quyết khoảng 3 hàng và sau đó đóng băng, thay đổi hầu hết các giá trị thành 9s.

Một số mã:

def solve_helper(self, row, col): 
# Try placing a number in each column of current row 
    board = self.the_board 
    if board[row][col] != 0: 
     ????? 
    elif board[row][col] == 0: 
     for i in range(1,10): 
      print("Setting value at i with ") + str (i) + (" located at ") + str(row) + str(col) 
      self.set_cell(row, col, i) 
      self.guesses = self.guesses + 1 
      if self.check_cell(row, col): 
       if self.solve_helper(row, col): return True 
      else: 
       self.set_cell(row, col, 0) 
    else: 
     return self.mover(row,col) 
    return False 

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0) 
    else: 
     print "SOLUTION FOUND" 
     return True 

Answer 1

Vấn đề bạn đang gặp phải là một số lượng các cuộc gọi đệ quy của bạn không trả lại kết quả đúng, vì vậy giải pháp của bạn, khi nó được tìm thấy, bị lãng quên về một vài cấp lên stack đệ quy. Dưới đây là sửa chữa đầu tiên mà bạn cần, thêm return để các cuộc gọi đệ quy thực hiện trong mover:

def mover(self, row, col): 
    if col + 1 != 9: 
     return self.solve_helper(row, (col+1)) # added return 
    elif row + 1 != 9: 
     print "Moving to row" + str(row + 1) 
     return self.solve_helper((row+1),0)  # here too 
    else: 
     print "SOLUTION FOUND" 
     return True 

Bạn cũng cần một cái gì đó tương tự như trong trường hợp đặc biệt của chức năng solve_helper nơi bạn bỏ qua các tế bào trước khi giải quyết. Sự kết thúc của hàm nên là:

else: 
    return self.mover(row, col) # added return 
return False 

Edit:

Ok, tôi đã tìm thấy một vài vấn đề ở những mã. Hai trong số đó là vấn đề logic với người giải quyết, và một là vấn đề hiển thị không gây ra bất kỳ vấn đề thực sự nào khác ngoài việc tìm kiếm kỳ lạ trong quá trình giải quyết.

Các vấn đề:

1. Đầu tiên, bạn mã mới nhất đã solve_helper tự xưng là, thay vì gọi mover. Điều này làm cho nó mất một cuộc gọi chức năng bổ sung trước khi di chuyển (mặc dù tôi nghĩ rằng nó có thể không thực sự phá vỡ các giải quyết).
2. Thứ hai, nếu solve_helper đặt ô thành 9, nhưng sau đó được quay lại (sau khi một số ô sau không thể giải được), số 9 không được đặt lại về 0 trước khi lùi lại.
3. Và cuối cùng, vấn đề hiển thị. Việc đặt ô thành 0 không dừng hiển thị giá trị cũ của chúng. Điều này trông rất giống với vấn đề ở # 2, (với 9s bị bỏ lại sau khi backtracking) nhưng trên thực tế nó chỉ là mỹ phẩm.

Vấn đề đầu tiên rất dễ khắc phục. Chỉ cần thay đổi cuộc gọi solve_helper thành cuộc gọi mover. Đó thực sự là những gì bạn có trong mã ban đầu mà bạn đưa vào câu hỏi. Gọi solve_helper trực tiếp không thực sự nhận được kết quả sai (kể từ khi solve_helper sẽ bỏ qua ô đã điền sẵn lần thứ hai), nhưng nó thêm một cuộc gọi hàm không cần thiết vào mỗi cấp đệ quy của bạn.

Vấn đề thứ hai phức tạp hơn một chút và đây là nơi bạn bị kẹt trên một số bảng. Những gì bạn cần làm là di chuyển dòng self.set_cell(row, col, 0) ra khỏi khối else hiện tại đang thực hiện. Trên thực tế, bạn có thể di chuyển nó ra ngoài vòng lặp hoàn toàn, nếu bạn muốn (vì nó chỉ thực sự cần thiết nếu bạn backtracking sau khi không có giá trị nào cho ô hiện tại hoạt động).Dưới đây là những gì tôi nghĩ rằng đây là sự sắp xếp tốt nhất của vòng lặp for (cũng di chuyển return False tuyên bố lên):

for i in range(1,10): 
    print("Setting value ") + str (i) + (" at ") + str(row) + ", " + str(col) 
    self.set_cell(row, col, i) 
    self.guesses = self.guesses + 1 
    if self.check_cell(row, col): 
     if self.mover(row, col): 
      return True 
print "Backtracking" 
self.set_cell(row, col, 0) 
return False 

Cuối cùng, khắc phục sự cố màn hình yêu cầu hai thay đổi. Đầu tiên, loại bỏ điều kiện trong set_cell. Bạn muốn cập nhật màn hình luôn. Tiếp theo, trong update_textfield, hãy di chuyển cuộc gọi delete bên ngoài khối if để luôn xảy ra (rời khỏi số insert trong số if). Điều này làm cho nó để thiết lập một tế bào bằng không sẽ xóa các giá trị trước đó, nhưng không làm cho nó hiển thị một ký tự 0 thực tế (nó sẽ hiển thị không có gì).

Tôi nghĩ việc này nên thực hiện. Lưu ý rằng thuật toán bạn đang sử dụng vẫn khá chậm. Giải quyết a board I found on the internet in a quick Google search đã thực hiện 122482 dự đoán và hơn 5 phút, nhưng cuối cùng nó cũng hoạt động. Các bảng khác (đặc biệt là các bo mạch yêu cầu 8 hoặc 9 trong vài không gian mở đầu tiên) có thể mất nhiều thời gian hơn.