Backtracking in Erlang

Question

Trước hết xin lỗi vì tiếng Anh của tôi.

Tôi muốn sử dụng thuật toán backtracking trong Erlang. Nó sẽ phục vụ như là một đoán để giải quyết một phần sudokus đầy. Một sudoku 9x9 được lưu trữ dưới dạng danh sách 81 phần tử, trong đó mọi phần tử lưu trữ số có thể có thể đi vào ô đó.

Đối với sudoku 4x4 giải pháp ban đầu của tôi trông giống như sau: [[1], [3], [2], [4], [4], [2], [3], [1], [ 2,3], [4], [1], [2,3], [2,3], [1], [4], [2,3]]

sudoku này có 2 giải pháp. Tôi phải viết cả hai. Sau khi giải pháp ban đầu đó đạt được, tôi cần phải thực hiện một thuật toán backtracking, nhưng tôi không biết làm thế nào để làm cho nó.

Suy nghĩ của tôi là viết ra các phần tử cố định vào một danh sách mới có tên là danh sách cố định sẽ thay đổi ô nhiều giải pháp thành [].

Đối với ví dụ được đề cập ở trên, danh sách cố định trông giống như sau: [[1], [3], [2], [4], [4], [2], [3], [1], [ ], [4], [1], [], [], [1], [4], []]

Từ đây tôi có "mẫu", tôi tìm độ dài thấp nhất trong danh sách giải pháp không bằng 1, và tôi thử số thứ nhất có thể của ô này và tôi đặt nó vào danh sách cố định đó. Ở đây tôi có một thuật toán để cập nhật các ô và kiểm tra nếu nó vẫn là một sudoku có thể giải được hay không. Nếu không, tôi không biết làm thế nào để bước lùi lại và thử một cái mới. Tôi biết mã giả của nó và tôi có thể sử dụng nó cho các ngôn ngữ mệnh lệnh nhưng không dùng cho ngôn ngữ. (prolog thực sự đã thực hiện thuật toán backtrack, nhưng erlang không)

Bất kỳ ý tưởng nào?

Answer 1

Re: chức năng bactracking My.

Đây là những chức năng chung cung cấp một khuôn khổ để xử lý theo dõi lại và các biến hợp lý tương tự như một công cụ prolog. Bạn phải cung cấp hàm (các biến vị ngữ) mô tả logic chương trình. Nếu bạn viết chúng như bạn sẽ làm trong prolog tôi có thể chỉ cho bạn cách dịch chúng thành erlang. Rất ngắn gọn bạn dịch cái gì đó như:

p :- q, r, s. 

trong prolog vào một cái gì đó giống như

p(Next0) -> 
    Next1 = fun() -> s(Next0) end, 
    Next2 = fun() -> r(Next1) end, 
    q(Next2). 

Ở đây tôi bỏ qua tất cả lập luận khác ngoại trừ continuations.

Tôi hy vọng điều này sẽ giúp bạn. Như tôi đã nói nếu bạn mô tả các thuật toán của mình, tôi có thể giúp bạn dịch chúng, tôi đã tìm kiếm một ví dụ điển hình. Bạn có thể, tất nhiên, cũng như làm điều đó một mình, nhưng điều này cung cấp một số trợ giúp.

Answer 2

Kiểm tra các bài viết trong blog của Robert Virding của:

http://rvirding.blogspot.com/2009/03/backtracking-in-erlang-part-1-control.html http://rvirding.blogspot.com/2009/04/backtracking-in-erlang-part-2-passing.html