Trang chủ xs Cách chơi nonogram – Game siêu trí tuệ cực hấp dẫn

Cách chơi nonogram – Game siêu trí tuệ cực hấp dẫn

Cách chơi nonogram – Game siêu trí tuệ cực hấp dẫn. Game trí tuệ cổ điển với những hình ảnh được mã hoá trên bảng chơi bằng cách sử dụng tư duy logic. Cùng game hay tìm hiểu chi tiết qua bài viết dưới đây. 

1. Khái niệm game Nonogram

Nonogram là một trò chơi cổ điển truyền thống của nước Nhật Bản với những quy chuẩn nhất định. Game này còn được thế giới biết tới với những tên gọi khác nhau như Japanese Puzzles, Pic-a-Pix, Hanjie, Griddlers, Picross hay Logimage…

Nội dung của Nonogram là một ô đó mà trong đó bạn sẽ cần phát lộ hình ảnh được mã hoá ở trên bảng chơi bằng cách sử dụng tư duy logic

Để có thể phát lộ được hình ảnh được mã hoá thì cần phải tô màu hoặc là gạch chéo tất cả những ô của bảng chơi dựa trên những con số được gợi ý.

Mỗi hàng và cột chỉ có một đáp án.

Số hàng và cột luôn là bội số của 5.

Cách chơi Nonogram

Cách chơi Nonogram

Mỗi một số sẽ cho biết rằng bạn cần phải tô màu bao nhiêu ô liền kề. Một vài số ở bên cạnh hàng và cột lại biểu thị số nhóm ô màu. Cần phải có ít nhất một ô trống ở giữa những nhóm ô màu khác nhau. Thứ tự của các số cho biết thứ tự của các nhóm ô màu.

Phần lớn những nonogram được thiết kế cho con người đều sẽ sử dụng một giải pháp duy nhất, tuy nhiên thì những câu đó không có lời giải và những câu có nhiều chữ cái cũng vẫn tồn tại.

Mặc dù rằng có nhiều câu đố do con người tạo ra khá dễ giải, nhưng đối với những câu đố lớn hơn với nhiều lời giải có thể trở nên rất khó khăn. Bài toán giải nonogram được biết là trong NP-Complete, đề cập đến các bài toán có ngôn ngữ là NP và NP-hard.

2. Cách chơi Nonogram

2.1. Luật chơi Nonogram đen trắng

Trong luật chơi này thì mỗi một số sẽ đại diện cho số ô đen có mặt trong hàng và cột đó. Bạn cần phải tìm ra những ô đen đó được nằm ở nơi nào trên bảng bằng cách click lựa chọn sao cho tổng các hàng và cột đều đúng theo những con số cho trước. Chú ý rằng ở giữa hai khối đen thường sẽ có ít nhất một ô trắng. Khi số ô cho hàng hay cột đó đã đủ, bạn có thể đánh dấu những ô sẽ để trắng còn lại hình dấu chấm để tránh bị nhầm lẫn trong việc tìm những ô có hàng hoặc cột cắt qua.

2.2. Các thuật toán để giải Nonogram

Phương pháp tiếp cận rõ ràng nhất để có thể giải quyết một trong những câu đố đó chính là xem xét một hàng hoặc là một cột riêng lẻ. Bộ giải dòng sẽ tiến hành kiểm tra một dòng duy nhất để có thể tìm ra những khối có cùng màu trong dung dịch dòng hoặc nó sẽ phát hiện ra rằng không tồn tại dung dịch như vậy. Trình giải dòng này sẽ được khởi chạy trên một câu đố nonogram cơ bản bên dưới.

Thuật toán này được sử dụng ma trận sol anxk mà sau khi tính toán, trong nó có chứa số lượng chất tạo màu, chưa các khối ô đen. Sau đó, một mảngidedLine lưu trữ thông tin về các chất tạo màu khả thi có thể được áp dụng cho bất kỳ ô nhất định nào. Bằng cách này, máy tính không phải trích xuất thông tin này từ ma trận sol được tính toán , Nếu n là độ dài của dòng và k là số khối ô đen, điều này cuối cùng làm giảm độ phức tạp của trình giải dòng của chúng ta từ O (kn²) xuống O (n²).

Các thuật toán giải dòng này cũng có thể được áp dụng cho các dòng đã biết thông tin về một số khối. Ví dụ: nếu trình giải dòng được chạy trên cột j và một số thông tin được trích xuất trong khối thứ i (ví dụ: thuật toán tô màu cho một số khối màu đen), thì nếu trình giải dòng được chạy trên hàng i, có thể là với điều này mới thông tin, máy tính có thể trích xuất thêm một chút thông tin trong hàng này. Điều này được thể hiện qua những hình ảnh dưới đây:

2.3.Một thuật toán với một hàng đợi ưu tiên

Thuật toán này sử dụng hàng đợi ưu tiên để cố gắng giải một cách hiệu quả các câu đố được tạo ngẫu nhiên với nhiều giải pháp.

Một câu đố được tạo ngẫu nhiên bắt đầu dưới dạng một lưới không có màu và mỗi ô được tô màu trắng hoặc đen một cách ngẫu nhiên.

Đối với thuật toán này, bộ giải dòng từ phía trên được kết hợp với cấu trúc dữ liệu hàng đợi ưu tiên , giống như một hàng đợi thông thường, nhưng mỗi phần tử có một “mức độ ưu tiên” được liên kết với nó. Những người có mức độ ưu tiên cao được giải quyết trước. Xem bên dưới:

Thuật toán này sử dụng hàng đợi ưu tiên để sắp xếp các dòng câu đố theo lượng thông tin dự kiến ​​được trích xuất từ ​​mỗi dòng khi sử dụng bộ giải dòng. Ở phần đầu, những dòng có nhiều khối dài được ưu tiên. Khi một dòng được xử lý (ví dụ: một hàng), tất cả các dòng có thông tin mới thu được (cột) sẽ được thêm vào hàng đợi. Nếu họ đã ở trong hàng đợi, họ sẽ được ưu tiên.

Chỉ sử dụng thuật toán ở trên sẽ không giải được tất cả các câu đố nonogram được tạo ngẫu nhiên. Điều này là do hàng đợi ưu tiên có thể trở nên trống. Nếu điều này xảy ra, thì không có thông tin nào có thể đạt được bằng cách sử dụng bộ giải dòng. Điều này có nghĩa là đối với mỗi khối hiện chưa được tô màu, tồn tại một màu trắng và một màu đen cho hai dòng chứa nó (hàng / cột).

Để giải phần còn lại của câu đố, máy tính sẽ cố gắng đoán phương án ít xảy ra nhất. Điều này nghe có vẻ phản trực quan, nhưng bằng cách sử dụng tìm kiếm theo chiều rộng , máy tính có thể cố gắng tìm khối / màu nào có nhiều khả năng xảy ra mâu thuẫn nhất. Việc tìm kiếm tùy chọn có lẽ ít nhất thường sẽ dẫn đến mâu thuẫn nhanh nhất, cho phép máy tính cắt các nhánh khỏi cây tìm kiếm, cuối cùng làm giảm không gian tìm kiếm.

Một tìm kiếm theo chiều rộng là một thuật toán để vượt qua một cấu trúc dữ liệu cây / đồ thị. Nó bắt đầu từ gốc và kiểm tra tất cả các nút ở độ sâu hiện tại trước khi chuyển sang cấp độ tiếp theo. Thuật toán này khá tốn kém, vì vậy thứ tự kiểm tra các khối chưa biết này được xác định:

  1. Các khối đã được kiểm tra trong lần lặp cuối cùng
  2. Các hàng xóm của các khối có giá trị được xác định trong lần lặp cuối cùng
  3. Các khối có 2 hoặc nhiều hàng xóm đã biết
  4. Chặn với một người hàng xóm đã biết

Nếu không đạt được sự mâu thuẫn nào, một khối và màu không xác định được đoán khi tìm kiếm theo chiều rộng được kiểm tra, cho phép máy tính xác định màu của càng nhiều khối chưa biết càng tốt. Các dự đoán được lưu trữ trong một cấu trúc dữ liệu dựa trên cây để máy tính có thể quay ngược trở lại khi nó xảy ra mâu thuẫn.

Trên đây là một số hướng dẫn về cách chơi nonogram cơ bản nhất cho người mới bắt đầu, khái niệm, quy luật chơi cũng như những thuật toán cơ bản của trò chơi này. Chúc bạn luôn có thời gian trải nghiệm thú vị cùng game này.

Kết quả theo ngày
lich thang Hôm nay thang sau