Làm cách nào để tôi có thể giải quyết các câu đố bằng gỗ của Đăng nhập bằng chương trình máy tính?

Question

Có ai có thể gợi ý cách giải quyết các câu đố bằng gỗ đăng nhập bằng một chương trình máy tính không?

Xem ở đây để hình dung các câu đố: http://www.puzzlethis.co.uk/products/madcow/the_log_pile.htm

Bức tranh chỉ cho thấy một số mảnh. Tập hợp đầy đủ của 10 miếng được cấu hình như sau với 1 đại diện cho một peg, -1 đại diện cho một lỗ và 0 đại diện cho cả một cái chốt cũng không phải là một lỗ.
-1,1,0, -1,0
1,0,1,0,0
1, -1,1,0,0
-1, -1,0,0, -1
-1,1,0,1,0
0,1,0,0,1
1,0, -1,0, -1
0, -1,0,1,0
0,0, -1,1, -1
1,0, -1,0,0

Các phần có thể được lồng vào nhau trong hai lớp 5 miếng mỗi lớp với lớp trên cùng ở 90 độ đến lớp dưới cùng như được hiển thị trong liên kết ở trên.

Tôi đã tự mình tạo ra một giải pháp cho vấn đề này bằng cách sử dụng Java nhưng tôi cảm thấy rằng đó là một giải pháp vụng về và tôi muốn xem một số giải pháp phức tạp hơn. Hãy đề nghị một cách tiếp cận chung hoặc để cung cấp một chương trình làm việc bằng ngôn ngữ bạn chọn.

Cách tiếp cận của tôi là sử dụng ký hiệu số ở trên để tạo một mảng "Nhật ký". Sau đó, tôi đã sử dụng trình tạo kết hợp/hoán vị để thử tất cả các sắp xếp có thể có của Nhật ký cho đến khi giải pháp được tìm thấy trong đó tất cả các nút giao bằng 0 (ví dụ: Peg to Hole, Hole to Peg hoặc Blank to Blank). Tôi đã sử dụng một số tốc độ để phát hiện giao lộ đầu tiên không thành công cho một hoán vị đã cho và chuyển sang hoán vị tiếp theo.

Tôi hy vọng bạn thấy điều này thú vị như tôi có.

Xin cảm ơn, Craig.

Answer 1

Theo lời khuyên của Jay Elston, tôi sẽ thực hiện nó bằng cách sử dụng mã giả sau đây:

Read in the pieces 
Annotate each piece with its number of pegs and holes 
Generate all possible base layers (10 over 5 = 252, selecting 5 from the set), 
    so that sum(above, pegs) == sum(below, holes) and sum(below, pegs) == sum(above, holes) 
    For each base layer, (5! = 120 of them, permuting the 'below' pieces) 
     compute 'rotated pieces' for the base layer 
     if one-to-one match between top layer and rotated base-layer pieces, 
      report successful solution 

Trường hợp "xoay mảnh" sẽ là, đối với một lớp cơ sở nhất định, các mảnh lý tưởng bạn sẽ cần phải che phủ nó. Bằng cách tính toán các phần này và kết hợp chúng với các phần lớp trên cùng, bạn có thể sử dụng kiểu O (N log N) để khớp các mảnh xoay với lớp trên cùng thực tế thay vì khớp với tất cả N! có thể sắp xếp lớp trên cùng. Ngoài ra, tại lần đầu tiên không khớp, bạn có thể bảo lãnh sớm.

Chìa khóa để viết các thuật toán hiệu quả là cắt giảm tìm kiếm của bạn càng sớm càng tốt và để khai thác bất kỳ đối xứng nào. Ví dụ, bạn có thể cắt giảm thời gian một nửa nếu bạn thấy rằng câu đố là đối xứng, và do đó bạn tự ý gán một phần cho lớp dưới cùng: bạn sẽ chỉ có 9 trên 4 lớp cơ sở để khám phá.

Answer 2

Prolog phổ biến cho các vấn đề thuộc loại này. Tôi đã thiết lập một số simpler puzzle problems có các giải pháp tương đối tốt đẹp trong Prolog.

Có những cách rất thanh lịch để giải quyết các loại vấn đề này trong Haskell, sử dụng chức năng và quay ngược lại. Một người bạn của tôi đã giải quyết một câu đố vật lý rất bực mình — Puzzling Pets — chỉ trong hơn 200 dòng, của Haskell, bao gồm mô tả tất cả các phần và mọi thứ. A   cách tốt để tìm hiểu các kỹ thuật liên quan sẽ là đọc giấy của John Hughes Why Functional Programming Matters, cài đặt Haskell Platform và thử dùng tay của bạn.

Answer 3

Sự cố này dường như là một dạng của Boolean satisfiability problem. Nếu nó là, cách tiếp cận tốt nhất được biết đến là sức mạnh vũ phu.

Nhưng có một số đối xứng và một số thuộc tính của sự cố có thể cho phép bạn giảm số lượng giải pháp bạn cần thử.Ví dụ -

• Nếu bạn chia các bản ghi thành hai 5 mảnh các tập con TOP và BOTTOM, cáC# chốt trong TOP cần phải phù hợp với # lỗ hổng trong BOTTOM, và # lỗ hổng trong nhu cầu TOP để khớp với # chốt trong số BOTTOM và # căn hộ trong TOP cần để khớp với # căn hộ trong BOTTOM. Nếu # chốt và # lỗ khớp nhau, thì # căn hộ sẽ khớp nhau, vì vậy bạn nên không cần phải kiểm tra # căn hộ.
• Có 10 * 9 * 8 * 7 * 6 cách bạn có thể phân đoạn nhật ký thành hai tập hợp con gồm 5 mảnh . (Khi bạn có chọn 5 nhật ký đầu tiên cho tập hợp con TOP, các nhật ký còn lại nằm trong tập con BOTTOM.
• Khi bạn thử nghiệm một tập con gồm 5 mảnh, có 5 * 8 * 6 * 4 * 2 cách bạn có thể Sắp xếp một lớp nhật ký, có 4 nhật ký còn lại, trong nhật ký thứ hai, bạn có thể chọn từ bốn, và có hai cách có thể định hướng với đối với nhật ký đầu tiên
• Một khi bạn có một lớp cơ sở, bạn có thể cố gắng để phù hợp với mỗi bản ghi từ các lớp khác cùng một lúc, cho đến khi bạn tìm thấy một trong đó không phù hợp.Tại thời điểm đó, bạn từ bỏ sắp xếp đăng nhập lớp cơ sở hiện tại và thử cái tiếp theo.

Answer 4

Tôi có một giải pháp (lộn xộn!) Trong javascript, nhưng gặp khó khăn khi đăng nó. Thuật toán cơ bản được sử dụng là: Tìm tất cả các lần lặp của 5 nhật ký từ tổng số 10 nhật ký và với mỗi bộ 5 nhật ký tạo mỗi lần lặp lại có thể với nhật ký bị đảo ngược. Đối với mỗi tiểu bang này, chúng tôi sẽ biết cần phải đặt mẫu nhật ký nào lên trên. Vì vậy, chúng tôi sau đó xác định xem 5 bản ghi còn lại có thể được đặt ở trên cùng hay không.

nào dẫn đến đại diện này của một giải pháp:

(Bottom, right-> left) 
[0,0,1,-1,1],[-1,-1,0,0,-1],[0,0,1,0,1],[-1,1,0,-1,0],[1,0,-1,0,0] 
(Top, up->down) 
[0,1,0,1,-1],[0,1,0,-1,0],[-1,0,-1,0,1],[1,0,0,1,0],[-1,1,-1,0,0] 


0 - flat 
1 - dowel 
-1 - hole