Bài toán Game Of Life

[iamvtn]

Bài toán Game Of Life được nhà toán học người Anh John Horton Conway đưa ra vào năm 1970.

Game Of Life là một chương trình giả lập một sự tiến triển của sự sống, không phải là một trò chơi với người sử dụng. Trên một lưới chữ nhật không có giới hạn, mỗi ô hoặc là ô trống hoặc đang có một tế bào chiếm giữ. Ô có tế bào được gọi là ô sống, ngược lại là ô chết. Mỗi thời điểm ổn định của toàn bộ lưới chúng ta gọi là một trạng thái. Để chuyển sang trạng thái mới, một ô sẽ thay đổi tình trạng sống hay chết tùy thuộc vào số ô sống chung quanh nó trong trạng thái cũ theo các quy tắc sau:

1. Một ô có tám ô kế cận.
   
2. Một ô đang sống mà không có hoặc chỉ có 1 ô kế cận sống thì ô đó sẽ chết do đơn độc.
   
3. Một ô đang sống mà có từ 4 ô kế cận trở lên sống thì ô đó cũng sẽ chết do quá đông.
   
4. Một ô đang sống mà có 2 hoặc 3 ô kế cận sống thì nó sẽ sống tiếp trong trạng thái sau.
   
5. Một ô đang chết trở thành sống trong trạng thái sau nếu nó có chính xác 3 ô kế cận sống.
   
6. Sự chuyển trạng thái của các ô là đồng thời, có nghĩa là căn cứ vào số ô kế cận sống hay chết trong một trạng thái để quyết định sự sống chết của các ô ở trạng thái sau.

Ví dụ:

Chúng ta gọi một đối tượng lưới chứa các ô sống và chết như vậy là một cấu hình.

Trong hình sau, con số ở mỗi ô biểu diễn số ô sống chung quanh nó, theo quy tắc thì cấu hình này sẽ không còn ô nào sống ở trạng thái sau.


Trong khi đó cấu hình tiếp theo sẽ bền vững và không bao giờ thay đổi.


Với một trạng thái khởi đầu nào đó, chúng ta khó lường trước được điều gì sẽ xảy ra. Một vài cấu hình đơn giản ban đầu có thể biến đổi qua nhiều bước để thành các cấu hình phức tạp hơn nhiều, hoặc chết dần một cách chậm chạp, hoặc sẽ đạt đến sự bền vững, hoặc chỉ còn là sự chuyển đổi lặp lại giữa một vài trạng thái.

Mục đích của bài toán là viết một chương trình hiển thị các trạng thái liên tiếp nhau của một cấu hình từ một trạng thái ban đầu nào đó. Đây là một bài toán được đưa vào làm bài tập lớn của môn Cấu trúc dữ liệu và giải thuật của một số trường Đại học.

Mã nguồn của bài toán này thì các bạn có thể tìm thấy rất nhiều trên internet nhưng cái quan trọng và đáng quan tâm hơn là một giải thuật dễ hiểu & chính xác.

Tham khảo http://en.wikipedia.org/wiki/Conways_Game_of_Life

(bài này tớ sưu tầm được rất là hay nên nêu ra đây anh em bàn luận chơi )