Bài viết sưu tầm

Bài toán trò chơi 8 số

Trong bảng ô vuông 3 hàng, 3 cột , mỗi ô chứa một số nằm trong phạm vi từ 1 đến 8 sao cho không có 2 ô có cùng giá trị, có một ô trong bảng bị trống (không chứa giá trị nào cả. Xuất phát từ một sắp xếp nào đó các số trong bảng, hãy dịch chuyển ô trống sang phải, sang trái, lên trên hoặc xuống dưới (nếu có thể được) để đưa về bảng ban đầu về bảng qui ước trước. Chẳng hạn Hình 1. dưới đây là bảng xuất phát và Hình 2. là bảng mà ta phải thực hiện các bước di chuyển ô trống để đạt được.           

Hình 2.1- Trạng thái ban đầu

Hình 2.2 Trạng thái kết thúc

Giá trị các phần tử trong bảng xác định trạng thái bài toán. Vì vậy có thể mô tả trạng thái của bài toán bằng một ma trận A_3*3= (a_ij) , a_ijÎ{0..8}, a_ij < > a_kl, "i<>k, j<> l

-                    Biểu diễn theo một hàm

Gọi hàm f_u là hàm biểu diễn cho toán tử chuyển ô trống lên trên; gọi B (B= (b_ij)) là trạng thái sau khi di chuyển ô trống ở trạng thái A (A= (a_ij)) lên trên, nghĩa là: B= f_u(A), giả sử ô trống đang ở vị trí (i₀, j₀) (hay nói cách khác a_{i0 j0} = 0) thì hàm f được xác định như sau:

                  a_ij                     "(i, j)             nếu  i₀ = 1     

f_u(a_ij)  =    a_ij                     nếu  (i, j) ¹(i₀-1, j₀) và (i, j) ¹(i₀, j₀) và i₀ >1     

                  a_{i0-1, j0}                  nếu  (i, j) = (i₀, j₀), i₀ >1

                  a_{i0, j0}                     nếu  (i, j) = (i₀-1, j₀), i₀ >1

Tương tự, có thể xác định các phép chuyển ô trống xuống dưới f_d, qua trái f_l, qua phải f_r như sau:

                  a_ij                     "(i, j)             nếu  i₀ = 3     

f_d(a_ij) =     a_ij                     nếu  (i, j) ¹(i₀+1, j₀) và (i, j) ¹(i₀, j₀) và i₀ <3    

                  a_{i0-1, j0}                  nếu  (i, j) = (i₀, j₀), i₀ <3

                  a_{i0, j0}                     nếu  (i, j) = (i₀+1, j₀), i₀ <3

                       a_ij                     "(i, j)             nếu  j₀ = 1     

f_l(a_ij) =     a_ij                     nếu  (i, j) ¹(i₀, j₀-1) và (i, j) ¹(i₀, j₀) và j₀ > 1    

                  a_{i0-1, j0}                  nếu  (i, j) = (i₀, j₀), j₀ > 1

                  a_{i0, j0}                     nếu  (i, j) = (i₀, j₀-1), j₀ > 1

                  a_ij                     "(i, j)             nếu  j₀ = 3     

f_r(a_ij) =     a_ij                     nếu  (i, j) ¹(i₀, j₀+1) và (i, j) ¹(i₀, j₀) và j₀ < 3   

                  a_{i0-1, j0}                  nếu  (i, j) = (i₀, j₀), j₀ < 3

                  a_{i0, j0}                     nếu  (i, j) = (i₀, j₀+1), j₀ < 3