Thuật toán đằng sau việc tạo ra tàu quét mìn

Question

Tôi đã trải qua nhiều trang web giảng dạy về cách giải quyết nó, nhưng đã tự hỏi làm thế nào để tạo ra nó. Tôi không quan tâm nhiều đến khía cạnh mã hóa của nó, nhưng muốn biết thêm về các thuật toán đằng sau nó. Ví dụ, khi lưới được tạo ra với 10 mỏ hoặc hơn, tôi sẽ sử dụng bất kỳ chức năng ngẫu nhiên để phân phối chính nó trên lưới, nhưng sau đó một lần nữa làm thế nào để tôi thiết lập các con số liên quan đến nó và quyết định mở hộp? Tôi không thể định hình bất kỳ thuật toán chung nào về cách tôi sẽ thực hiện điều đó.

Answer 1

Có lẽ cái gì đó trong dòng:

grid = [n,m] // initialize all cells to 0 
for k = 1 to number_of_mines 
    get random mine_x and mine_y where grid(mine_x, mine_y) is not a mine 
    for x = -1 to 1 
     for y = -1 to 1 
     if x = 0 and y = 0 then 
      grid[mine_x, mine_y] = -number_of_mines // negative value = mine 
     else 
      increment grid[mine_x + x, mine_y + y] by 1 

Đó là khá nhiều nó ...

** EDIT **

Bởi vì thuật toán này thể chì vào việc tạo ra một hội đồng quản trị với một số mỏ nhóm quá nhiều với nhau, hoặc tệ hơn rất phân tán (do đó nhàm chán để giải quyết), sau đó bạn có thể thêm xác nhận thêm khi tạo ra mine_x và số mine_y. Ví dụ, để đảm bảo rằng ít nhất 3 tế bào lân cận không phải là mỏ, hoặc thậm chí có lẽ ủng hộ việc hạn chế số lượng các mỏ mà quá xa nhau vv

** CẬP NHẬT **

tôi đã tự do chơi một chút với JS bin ở đây đã đưa ra một chức năng Minesweeper game demo. Điều này chỉ đơn giản là để chứng minh các thuật toán được mô tả trong câu trả lời này. Tôi không tối ưu hóa sự ngẫu nhiên của vị trí mỏ được tạo ra, do đó một số trò chơi có thể là không thể hoặc quá dễ dàng. Ngoài ra, không có xác nhận là có bao nhiêu mỏ có trong lưới điện, vì vậy bạn thực sự có thể tạo ra một 2 2 lưới với 1000 mỏ .... nhưng điều đó sẽ chỉ dẫn đến một vòng lặp vô hạn :) Thưởng thức!

Answer 2

Bạn chỉ cần gieo hạt và sau đó, bạn đi qua mọi ô và đếm các mỏ lân cận.

Hoặc bạn đặt mọi bộ đếm thành 0 và với mỗi ô giống, bạn tăng tất cả các bộ đếm ô lân cận.

Answer 3

Nếu bạn muốn đặt m mỏ trên N hình vuông và bạn có quyền truy cập vào trình tạo số ngẫu nhiên, bạn chỉ cần đi qua các ô vuông còn lại và tính mỗi ô vuông (# mỏ còn lại)/(# hình vuông còn lại) và đặt một mỏ nếu số ngẫu nhiên của bạn bằng hoặc thấp hơn giá trị đó.

Bây giờ, nếu bạn muốn dán nhãn mỗi vuông với số lượng các mỏ lân cận, bạn có thể chỉ làm điều đó trực tiếp:

count(x,y) = sum(
    for i = -1 to 1 
    for j = -1 to 1 
     1 if (x+i,y+j) contains a mine 
     0 otherwise 
) 

hoặc nếu bạn thích, bạn có thể bắt đầu với một loạt các số không và tăng mỗi bởi một trong hình vuông 3x3 có một mỏ ở trung tâm. (Nó không làm tổn thương số ô vuông với mỏ.)

Điều này tạo ra trò chơi quét mìn hoàn toàn ngẫu nhiên và được chú thích một cách chính xác. Tuy nhiên, một số trò chơi ngẫu nhiên có thể không phải là trò chơi thú vị; chọn trò chơi ngẫu nhiên nhưng thú vị là một nhiệm vụ khó khăn hơn nhiều.