Trò chơi này có giải pháp

Question

Tôi đang phát triển một trò chơi đơn giản bằng cách sử dụng Java swing. Tôi muốn biết liệu trò chơi cụ thể này có giải pháp trong kịch bản sau không. Nếu tôi tin rằng về mặt lý thuyết thì một giải pháp không thể đến được vào thời điểm này, tôi sẽ ném một thông báo cho người dùng.

3x3
http://img814.imageshack.us/img814/7449/screenshot20100924at206.png

4x4
http://img39.imageshack.us/img39/1851/screenshot20100924at241.png

Mục tiêu của trò chơi này là để lấp đầy số 1-8 (hoặc 1-15) bằng cách sử dụng một không gian có sẵn để đẩy những con số đến không gian trống đó. Mỗi lần tôi kết thúc với sự kết hợp được hiển thị ở trên. Tôi chỉ muốn thuyết phục bản thân rằng không có cách nào để đạt được giải pháp thích hợp từ kịch bản trên. Hãy giúp tôi.

EDIT: Giải pháp đã được niêm yết tại here và here

Answer 1

Vâng, và không. Nếu bạn tạo ra các số ngẫu nhiên, tôi tin rằng có một tình huống có thể xảy ra khiến cho câu đố không thể giải quyết được. Cách tôi muốn đề nghị tạo ra một câu đố bắt đầu với câu đố đã giải quyết, và thực hiện một số (tăng dần dựa trên độ khó) của di chuyển ngược lại. Bằng cách đó bạn biết rằng câu đố cuối cùng là khả năng giải quyết được.

Answer 2

Thảo luận này về The 15 Puzzle có thể sẽ cung cấp cho bạn câu trả lời. Tôi nghi ngờ rằng việc phân tích các hoán vị trong câu đố đó sẽ áp dụng cho câu đố nhỏ hơn của bạn.

Answer 3

Từ wikipedia tiếng Pháp trên "Taquin" (15 câu đố):

Giai thoại

Chức Initiale du taquin de Sam Loyd
Loyd affirma qu'il avait «rendu le megae entier fou »avec un taquin modifié. Dans la cấu hình đề xuất, les carreaux 14 và 15 inétés inétés, chúng ta có thể sử dụng trong một giọt nhỏ. Loyd prétendait avoir promis 1 000 USD à celui qui remettrait les carreaux dans l'ordre, mais la récompense n'aurait jamais été réclamée.
La résolution de ce problème est không thể. Phần D'une, il faut en effet trao đổi các địa điểm des carreaux 14 et 15, et l'on peut montrer que cette opération nécessite un nombre suy giảm de glissements. D'autre một phần, il faut que la trường hợp vide retrouve sa nơi ban đầu, opération qui, lượng tử elle, nécessite un nombre cặp de glissements. Có thể bạn có thể tìm thấy một số từ 1 đến 15 trong trường hợp vide est initialement en haut à gauche.

---

Giai thoại

vị trí ban đầu của 15 câu đố Sam Loyd của
Loyd cho biết ông đã "làm cho thế giới điên" với một câu đố 15 sửa đổi. Trong cấu hình được đề xuất, các ô 14 và 15 được đảo ngược, không gian trống được đặt ở dưới cùng bên phải. Loyd tuyên bố đã hứa 1 000 USD cho một người sẽ đặt gạch theo thứ tự, nhưng phần thưởng không bao giờ được tuyên bố. Giải quyết vấn đề này là không thể.Một mặt, nó phải thực sự trao đổi các vị trí của các gạch 14 và 15, và nó có thể được hiển thị rằng hoạt động này đòi hỏi một số lẻ của các slide. Mặt khác, không gian trống phải quay trở lại vị trí ban đầu của nó, một hoạt động đòi hỏi số lượng trang trình bày thậm chí còn nhiều. Có thể đặt các số từ 1 đến 15 nếu không gian trống ban đầu ở phía trên bên trái.

---

Resources:

• fr.wikipedia - Taquin