Game ghép tranh(N-Puzzle) là một trò chơi khá hay và trí tuệ, nó được biết đến với nhiều phiên bản và tên gọi khác nhau như: 8-puzzle, 15-puzzle, Gem puzzle, Boss puzzle. Bài toán N-puzzle là vấn đềcổ điển cho mô hình thuật toán liên quan đến trí tuệnhân tạo. Bài toán đặt ra là phải tìm đường đi từtrạng thái hiện tại tới trạng thái đích. Và cho tới nay vẫn chưa có thuật toán tối ưu đểgiải bài toán này. Phần mềm N-Puzzle là một chương trình xây dựng trò chơi và giải quyết bài toán này. Phần mềm được viết trên nền Java, sửdụng giao diện đồhọa đểmô phỏng trò chơi và thuật toán A* đểtìm đường đi. Người dùng có thểsửdụng chuột/bàn phím chơi với các kích thước khác nhau và với hình ảnh khác nhau hoặc có thểsửdụng chức năng tìm lời giải nhờthuật toán A*. Yêu cầu xây dựng bảng ô vuông n hàng, n cột. Bảng gồm 1 ô trống và n 2 -1 ô chứa các số trong phạm vi [1, n 2 -1]. Xuất phát từ m ột cách xếp bất kì, di chuyển ô trống lên trên, xuống dưới, sang phải, sang trái để đưa các ô vềtrạng thái đích. Sửdụng chuột hay phím chức năng đểdi chuyển ô trống. Chương trình có chức năng tự động chơi ởbất kì trạng thái nào đó. Mỗi trạng thái của bảng số là một hoán vịcủa n 2 phần tử. Ở đây ta có thểmởrộng bằng việc thêm hình ảnh vào game hoặc gắn sốvào hình ảnh đểgợi ý cho người chơi. Ởtrạng thái ban đầu, các ô được sắp xếp ngẫu nhiên, và nhiệm vụcủa người chơi là tìm được cách đưa chúng vềtrạng thái đích(ô đầu trống, các ô khác theo thứtựtăng dần từ trái qua phải, từtrên xuống dưới). Để đơn giản trong cách tiếp cận bài toán, ta giả định chỉcác ô trống di chuyển trong bảng là di chuyển đến các vịtrí khác nhau. Nhưvậy tại một trạng thái bất kì có tối đa 4 cách di chuyển đến trạng thái khác(trái, phải, lên, xuống).