Về Trò chơi 15 | Lịch sử, tính chẵn lẻ và 14-15 của Sam Loyd

Cơn sốt năm 1880

Trò chơi này ra đời ở bang New York vào những năm 1870; Noyes Chapman, một trưởng bưu cục ở Canastota, thường được coi là người phát minh. Đầu năm 1880, nó trở thành một cơn sốt, trước tiên trên khắp Hoa Kỳ rồi đến châu Âu.

14-15 của Sam Loyd

Nhà sáng tác câu đố người Mỹ Sam Loyd sau này tự nhận mình đã phát minh ra trò chơi, và kể về giải thưởng 1.000 đô la cho bất kỳ ai giải được nó khi chỉ có 14 và 15 bị đổi chỗ. Không ai giành được giải, và cũng không ai có thể: thế đó không thể giải. Lời tự nhận là người phát minh của ông cũng không đúng.

Vì sao một nửa số thế là bất khả

Hãy coi ô trống là ô số thứ mười sáu. Mỗi lần trượt đổi chỗ ô trống với một ô số. Để trở về góc của nó, ô trống phải đi sang trái bao nhiêu lần thì sang phải bấy nhiêu lần, đi lên bao nhiêu lần thì đi xuống bấy nhiêu lần, nên một thế có ô trống ở góc luôn cách thứ tự đã giải một số chẵn lần đổi chỗ. Đổi chỗ 14 và 15 là một lần đổi chỗ, tức là lẻ, nên không chuỗi trượt nào đạt tới được. Năm 1879, William Johnson và William Story đã chứng minh rằng đúng một nửa số cách sắp xếp có thể đạt tới.

Phép thử cho mọi thế

Đếm số cặp ô số đứng sai thứ tự khi bạn đọc khay theo từng hàng. Trên bàn 3×3 hoặc 5×5, một thế giải được khi số đó là chẵn. Trên bàn 4×4, hãy cộng thêm hàng của ô trống tính từ dưới lên: thế đó giải được khi tổng là lẻ.

Giải bằng máy tính

Máy tính có thể tìm đường trở về bằng A*, thuật toán luôn xét thế hứa hẹn nhất trước. Nó ước lượng số nước còn cần từ khoảng cách của mỗi ô số đến ô đích, cộng thêm hai nước cho mỗi cặp ô số chặn nhau trên chính hàng hoặc cột của chúng. Tìm lời giải ngắn nhất trở nên rất khó trên các bàn lớn. Các thế khó nhất của trò chơi 15 cần 80 nước, còn trò chơi 8 không bao giờ cần quá 31.

Thử trong PictorX

Mở Trò chơi 15 và bấm vào một ô số để trượt nó. Xáo trộn sắp các ô số thành một thế mới giải được, Giải phát một lời giải từng nước một, còn Hiện ô đúng chỗ tô màu số trên những ô số đã nằm đúng chỗ. Chọn 14-15 của Loyd để xem thế không thể giải, và dùng Kích thước để chuyển giữa 3×3, 4×4 và 5×5.

Hỏi thường xuyên

Ai đã phát minh ra trò chơi 15?

Noyes Chapman, một trưởng bưu cục ở Canastota, New York, thường được coi là người phát minh, vào những năm 1870. Lời tự nhận sau này của Sam Loyd là sai.

Trò chơi 14-15 có giải được không?

Không. Nó chỉ cách thứ tự đã giải một lần đổi chỗ, còn mọi thế mà các lần trượt đạt tới đều cách một số chẵn lần đổi chỗ.

Trò chơi 15 có bao nhiêu thế?

16 ô có thể được lấp đầy theo 20.922.789.888.000 cách. Đúng một nửa trong số đó, 10.461.394.944.000, có thể đạt tới bằng cách trượt.

PictorX có tải gì lên không?

Không. Trò chơi được vẽ trên canvas trong trình duyệt. Lưu sẽ tải xuống một PNG, và Chỉnh sửa mở ảnh đó trong trình chỉnh sửa PictorX.