Python, 4x5 board, 5 mines.

This is the reference implementation, with fixes thanks to @138Aspen. I just thought I'd put it here to help give people ideas.

This implementation uses dynamic programming to prevent duplication of work, exploits mirror symmetries, and maintains a fist of all possible boards with a given revealed square status to check for guaranteed safe squares.

On my current laptop, when run using pypy, it can optimally solve the 4x5 board with 5 mines in 72 seconds.

# Minesweeper solver
# Class just contains partially revealed boards that all look the same
# from the outside

# This is a branch, that uses strings.

# Boards have every cell revealed.
# Revealed is partially revealed. Boards must match revealed on every
# cell that is revealed.

# Meanings:
# '0'-'8': Safe square with that # of surrounding mines
# '*'    : Mine
# '_'    : Unrevealed
import copy
import itertools
import time

class Position:
    def __init__(self, dimensions, revealed, boards):
        self.dim_r,self.dim_c=dimensions
        self.rev=revealed
        self.boards=boards
        assert len(revealed)==self.dim_r*self.dim_c

    def click(self,loc):
        # Takes a location, returns all possible revealed positions, with boards
        # split up accordingly
        try:
            assert self.rev[loc]=='_'
        except AssertionError:
            print(self,loc,self.rev)
            assert self.rev[loc]=='_'
        # Create all possible new boards, split up by revealed item.
        board_dict={}
        for board in self.boards:
            clicked_cell=board[loc]
            if clicked_cell in board_dict:
                board_dict[clicked_cell].append(board)
            else:
                board_dict[clicked_cell]=[board]
        new_positions=[]
        for rev_cell in board_dict.keys():
            # Make the new board without copying
            new_rev=''.join([self.rev[:loc],rev_cell,self.rev[loc+1:]])
            new_pos=Position((self.dim_r,self.dim_c),new_rev,board_dict[rev_cell])
            new_positions.append(new_pos)
        return new_positions

    def someBestClick(self):
        click_list=[]
        # Set of boards is all we know when outputting, may be smaller than
        # complete set
        # If we've clicked on a bomb, no way to win, no best click.
        if '*' in self.rev:
            return 0,[]
        unrevealed = [loc for loc in range(len(self.rev)) if self.rev[loc]=='_']
        # If there is only 1 possible board, you're done. The click list is every
        # unrevealed square on the board without a bomb under it.
        if len(self.boards)==1:
            return 1,[loc for loc in unrevealed if self.boards[0][loc]!='*']

        # If there is an unrevaled locaiton on the board that is bomb free in
        # every sub-board, use it.
        for loc in unrevealed:
            if all(board[loc]!='*' for board in self.boards):
                return sum(pos.memoBestClick()[0] for pos in self.click(loc)),[loc]

        # The broadest test - try everywhere.
        click_list=[]
        most_wins=0
        for loc in unrevealed:
            wins=sum(pos.memoBestClick()[0] for pos in self.click(loc) if pos.rev[loc]!='*')
            if wins>=most_wins:
                if wins>most_wins:
                    click_list=[]
                    most_wins=wins
                click_list.append(loc)
        return most_wins,click_list

    def memoBestClick(self):
        global memo
        global memo_counter
        memo_counter +=1
        if not self.rev in memo:
            # These lines check for mirror images of the board being in the memo table

            vert_reversed_memo_str=                                         \
            ''.join([self.rev[y*self.dim_c:(y+1)*self.dim_c]
                     for y in range(self.dim_r)][::-1])

            if vert_reversed_memo_str in memo:
                vert_reversed_output=memo[vert_reversed_memo_str]
                return vert_reversed_output[0],                             \
                        [(self.dim_r-1-loc//self.dim_c)*self.dim_c+loc%self.dim_c
                         for loc in vert_reversed_output[1]]

            horiz_reversed_memo_str=                                        \
            ''.join(self.rev[y*self.dim_c:(y+1)*self.dim_c][::-1]
                    for y in range(self.dim_r))

            if horiz_reversed_memo_str in memo:
                horiz_reversed_output=memo[horiz_reversed_memo_str]
                return horiz_reversed_output[0],                            \
                        [(loc//self.dim_c)*self.dim_c+loc%self.dim_c
                         for loc in horiz_reversed_output[1]]
            both_reversed_memo_str=self.rev[::-1]
            if both_reversed_memo_str in memo:
                both_reversed_output=memo[both_reversed_memo_str]
                return both_reversed_output[0],                             \
                        [len(self.rev)-1-loc
                         for loc in both_reversed_output[1]]

            global restart_counter
            global restart_memo

            if len(self.rev)-self.rev.count('_') <= restart_max:
                restart_memo[self.rev]=self.someBestClick()
                memo[self.rev]=restart_memo[self.rev]
                return restart_memo[self.rev]
            # Needed because of memory issues
            if len(memo)>5*10**6:
                memo=copy.deepcopy(restart_memo)
                restart_counter+=1
            memo[self.rev]=self.someBestClick()
        return memo[self.rev]

def makeBlankPosition(dimensions,mines):
    dim_r,dim_c=dimensions
    # Makes all locations on the board
    all_loc=itertools.product(range(dim_c),range(dim_r))
    # Makes all possible distributions of mines
    all_mine_layouts=itertools.combinations(all_loc,mines)
    boards=[]
    for mine_layout in all_mine_layouts:
        boards.append(makeBoardFromMines(dimensions,mine_layout))
    return Position(dimensions, '_'*dim_c*dim_r, boards)

def makeBoardFromMines(dimensions,mine_layout):
    dim_r,dim_c=dimensions
    def mineNum(loc):
        if (loc%dim_c,loc//dim_c) in mine_layout:
            return '*'
        return str(sum(((loc%dim_c+dif[0],loc//dim_c+dif[1]) in mine_layout) for dif in
                   [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]))
    return ''.join(map(mineNum,(loc for loc in range(dim_r*dim_c))))

def makePosition(dimensions,mines,revealed):
    blank_pos=makeBlankPosition(dimensions,mines)
    boards_subset=[]
    for board in blank_pos.boards:
        if all(revealed[cell_num]==board[cell_num] or revealed[cell_num]=='_' for cell_num in range(len(board))):
            boards_subset.append(board)
    return Position(dimensions, revealed, boards_subset)

def winRate(dimensions,mines,revealed):
    pos=makePosition(dimensions,mines,revealed)
    global memo
    memo={}
    wins=pos.memoBestClick()
    return wins[0],len(pos.boards),wins[1],memo

global memo_counter
memo_counter=0
global restart_counter
restart_counter=0
global restart_memo
restart_memo={}
global restart_max
restart_max=6
dimensions, mines, revealed = eval(input())
start_time=time.time()
wins, total_boards, moves, memo = winRate(dimensions, mines, revealed)
move_points=[(move//dimensions[1],move%dimensions[1]) for move in moves]
print("""Best moves are %s.\n%i wins out of %i boards. Ratio of %f. %i 
positions searched.\n%f seconds taken."""%(move_points, wins, total_boards,
wins/total_boards, len(memo),time.time()-start_time))

C++

C++ port of @isaacg's Python answer.

Try it online!

#include <cassert>
#include <chrono>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

// Forward declaration
struct Position;

// Global memoization variables
unordered_map<string, pair<int, vector<int>>> memo;
unordered_map<string, pair<int, vector<int>>> restart_memo;
int memo_counter = 0;
int restart_counter = 0;
int restart_max = 6;

struct Position {
    int dim_r, dim_c;
    string rev;  // string representing the revealed state (each char: '_' for unrevealed, or a digit or '*' if revealed)
    vector<string> boards; // each board is a full board outcome as a string

    Position(int r, int c, const string &revealed, const vector<string> &b)
        : dim_r(r), dim_c(c), rev(revealed), boards(b) {
        assert((int)rev.size() == dim_r * dim_c);
    }

    // click: given a location (index into rev), generates all new Positions
    // by splitting the boards based on what value is revealed in that cell.
    vector<Position> click(int loc) const {
        assert(rev[loc] == '_');  // must be unrevealed
        unordered_map<char, vector<string>> board_dict;
        for (const auto &board : boards) {
            char clicked_cell = board[loc];
            board_dict[clicked_cell].push_back(board);
        }
        vector<Position> new_positions;
        // For each revealed cell possibility, update the revealed string and list of boards.
        for (auto &entry : board_dict) {
            char rev_cell = entry.first;
            string new_rev = rev;
            new_rev[loc] = rev_cell;
            new_positions.push_back(Position(dim_r, dim_c, new_rev, entry.second));
        }
        return new_positions;
    }

    // someBestClick returns a pair where:
    //   first  = total wins from descendant positions,
    //   second = vector of best moves (cell indices)
    pair<int, vector<int>> someBestClick() {
        // If a bomb has already been revealed, no win is possible.
        if (rev.find('*') != string::npos) {
            return {0, {}};
        }
        // Collect all unrevealed positions
        vector<int> unrevealed;
        for (int i = 0; i < (int)rev.size(); i++) {
            if (rev[i] == '_')
                unrevealed.push_back(i);
        }
        // If there is only one possible board, every unrevealed square that is not a bomb is a winning move.
        if (boards.size() == 1) {
            vector<int> moves;
            for (int loc : unrevealed) {
                if (boards[0][loc] != '*') {
                    moves.push_back(loc);
                }
            }
            return {1, moves};
        }

        // If there is an unrevealed location that is safe in every sub-board, use it.
        for (int loc : unrevealed) {
            bool safeEverywhere = true;
            for (const auto &board : boards) {
                if (board[loc] == '*') {
                    safeEverywhere = false;
                    break;
                }
            }
            if (safeEverywhere) {
                int sumWins = 0;
                vector<Position> clicked = click(loc);
                for (auto &pos : clicked) {
                    sumWins += pos.memoBestClick().first;
                }
                return {sumWins, {loc}};
            }
        }

        // Broadest test - try all unrevealed locations and pick those whose descendant wins sum is maximal.
        int most_wins = 0;
        vector<int> click_list;
        for (int loc : unrevealed) {
            int wins = 0;
            vector<Position> descendant = click(loc);
            for (auto &pos : descendant) {
                // Ensure that if a bomb was revealed on that click, we do not add its wins.
                if (pos.rev[loc] == '*')
                    continue;
                wins += pos.memoBestClick().first;
            }
            if (wins > most_wins) {
                most_wins = wins;
                click_list.clear();
                click_list.push_back(loc);
            } else if (wins == most_wins) {
                click_list.push_back(loc);
            }
        }
        return {most_wins, click_list};
    }

    // memoBestClick uses a global memo table to cache results.
    pair<int, vector<int>> memoBestClick() {
        memo_counter++;
        if (memo.find(rev) == memo.end()) {
            // Check mirror images
            // 1. Vertical reversal: reverse the order of rows.
            string vert_reversed;
            for (int y = dim_r - 1; y >= 0; y--) {
                vert_reversed += rev.substr(y * dim_c, dim_c);
            }
            if (memo.find(vert_reversed) != memo.end()) {
                auto vert_output = memo[vert_reversed];
                vector<int> transformed;
                for (int loc : vert_output.second) {
                    int r = loc / dim_c;
                    int c = loc % dim_c;
                    int new_r = dim_r - 1 - r;
                    int new_loc = new_r * dim_c + c;
                    transformed.push_back(new_loc);
                }
                return {vert_output.first, transformed};
            }
            // 2. Horizontal reversal: reverse each row.
            string horiz_reversed;
            for (int y = 0; y < dim_r; y++) {
                string row = rev.substr(y * dim_c, dim_c);
                reverse(row.begin(), row.end());
                horiz_reversed += row;
            }
            if (memo.find(horiz_reversed) != memo.end()) {
                auto horiz_output = memo[horiz_reversed];
                vector<int> transformed;
                for (int loc : horiz_output.second) {
                    int r = loc / dim_c;
                    int c = loc % dim_c;
                    int new_c = dim_c - 1 - c;
                    int new_loc = r * dim_c + new_c;
                    transformed.push_back(new_loc);
                }
                return {horiz_output.first, transformed};
            }
            // 3. Both reversed: reverse entire string.
            string both_reversed = rev;
            reverse(both_reversed.begin(), both_reversed.end());
            if (memo.find(both_reversed) != memo.end()) {
                auto both_output = memo[both_reversed];
                vector<int> transformed;
                int total = rev.size();
                for (int loc : both_output.second) {
                    transformed.push_back(total - 1 - loc);
                }
                return {both_output.first, transformed};
            }

            if ((int)rev.size() - count(rev.begin(), rev.end(), '_') <= restart_max) {
                auto best = this->someBestClick();
                restart_memo[rev] = best;
                memo[rev] = best;
                return best;
            }

            if (memo.size() > 5000000) {
                memo = restart_memo;
                restart_counter++;
            }
            memo[rev] = this->someBestClick();
        }
        return memo[rev];
    }
};

// --- Helper functions for board generation ---

// Given a dimensions pair and a mine_layout (vector of (col,row) pairs),
// returns a board string. For each cell, if the cell has a bomb ('*') it is '*'.
// Otherwise, it is the count of bombs adjacent to that cell.
string makeBoardFromMines(pair<int, int> dimensions, const vector<pair<int, int>> &mine_layout) {
    int dim_r = dimensions.first, dim_c = dimensions.second;
    unordered_set<int> mineSet;
    // We use location index = row * dim_c + col.
    for (const auto &p : mine_layout) {
        int col = p.first;
        int row = p.second;
        mineSet.insert(row * dim_c + col);
    }
    string board;
    board.resize(dim_r * dim_c);
    for (int loc = 0; loc < dim_r * dim_c; loc++) {
        if (mineSet.count(loc)) {
            board[loc] = '*';
        } else {
            int count_mines = 0;
            int row = loc / dim_c;
            int col = loc % dim_c;
            for (int dr = -1; dr <= 1; dr++) {
                for (int dc = -1; dc <= 1; dc++) {
                    if (dr == 0 && dc == 0)
                        continue;
                    int nr = row + dr, nc = col + dc;
                    if (nr >= 0 && nr < dim_r && nc >= 0 && nc < dim_c) {
                        int nloc = nr * dim_c + nc;
                        if (mineSet.count(nloc))
                            count_mines++;
                    }
                }
            }
            board[loc] = '0' + count_mines;
        }
    }
    return board;
}

// This function recursively generates all combinations (as indices) for choosing k items out of total.
void combineMineLayouts(int start, int k, int total, vector<int> &current, vector<vector<int>> &result) {
    if (k == 0) {
        result.push_back(current);
        return;
    }
    for (int i = start; i <= total - k; i++) {
        current.push_back(i);
        combineMineLayouts(i + 1, k - 1, total, current, result);
        current.pop_back();
    }
}

// Given board dimensions and a mine count, generate all possible mine boards.
// The mine positions are generated as combinations over all cell indices.
Position makeBlankPosition(pair<int, int> dimensions, int mines) {
    int dim_r = dimensions.first, dim_c = dimensions.second;
    int total = dim_r * dim_c;
    vector<vector<int>> combinations;
    vector<int> current;
    combineMineLayouts(0, mines, total, current, combinations);
    vector<string> boards;
    for (const auto &comb : combinations) {
        vector<pair<int, int>> mine_layout;
        for (int loc : comb) {
            int row = loc / dim_c;
            int col = loc % dim_c;
            // In the Python code mine_layout uses the tuple (col, row)
            mine_layout.push_back({col, row});
        }
        boards.push_back(makeBoardFromMines(dimensions, mine_layout));
    }
    string unrevealed(total, '_');
    return Position(dim_r, dim_c, unrevealed, boards);
}

// This function builds a Position based on a partially revealed board.
// Only boards that agree with the revealed digits (or '_' where not revealed) are kept.
Position makePosition(pair<int, int> dimensions, int mines, const string &revealed) {
    Position blank_pos = makeBlankPosition(dimensions, mines);
    int total = dimensions.first * dimensions.second;
    vector<string> boards_subset;
    for (const auto &board : blank_pos.boards) {
        bool valid = true;
        for (int cell_num = 0; cell_num < total; cell_num++) {
            if (revealed[cell_num] != '_' && revealed[cell_num] != board[cell_num]) {
                valid = false;
                break;
            }
        }
        if (valid)
            boards_subset.push_back(board);
    }
    return Position(dimensions.first, dimensions.second, revealed, boards_subset);
}

// Returns a tuple of win info: wins, total boards, best moves, and duration.
pair<int, tuple<int, vector<int>, int, double>> winRate(pair<int, int> dimensions, int mines, const string &revealed) {
    Position pos = makePosition(dimensions, mines, revealed);
    memo.clear();
    memo_counter = 0;
    auto start = chrono::high_resolution_clock::now();
    auto wins_moves = pos.memoBestClick();
    auto end = chrono::high_resolution_clock::now();
    double duration = chrono::duration<double>(end - start).count();
    int wins = wins_moves.first;
    int total_boards = pos.boards.size();
    return {wins, make_tuple(total_boards, wins_moves.second, (int)memo.size(), duration)};
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // The Python code uses eval(input()) to obtain a tuple of (dimensions, mines, revealed).
    // For C++, we assume the input is given as:
    //   rows cols mines revealed_string
    // For example: "2 2 1 ____" indicates a 2x2 board, 1 mine, and all cells unrevealed.
    int rows, cols, mines;
    string revealed;
    cin >> rows >> cols >> mines >> revealed;
    pair<int, int> dimensions = {rows, cols};

    // Calculate win rate and best moves.
    auto result = winRate(dimensions, mines, revealed);
    int wins = result.first;
    auto tup = result.second;
    int total_boards = std::get<0>(tup);
    vector<int> moves = std::get<1>(tup);
    int memo_size = std::get<2>(tup);
    double time_taken = std::get<3>(tup);

    // Convert linear position indices to (row, col) points.
    vector<pair<int, int>> move_points;
    for (int move : moves) {
        int r = move / cols;
        int c = move % cols;
        move_points.push_back({r, c});
    }

    cout << "Best moves are ";
    cout << "[";
    bool first = true;
    for (auto &p : move_points) {
        if (!first)
            cout << ", ";
        cout << "(" << p.first << ", " << p.second << ")";
        first = false;
    }
    cout << "].\n";
    cout << wins << " wins out of " << total_boards << " boards. Ratio of " 
         << (double)wins / total_boards << ". " << memo_size 
         << " positions searched.\n";
    cout << time_taken << " seconds taken.\n";

    return 0;
}

// 4 4 4 ________________

Rust

Rust port of @isaacg's Python answer.

Run it on Rust Playground!

use std::collections::{HashMap, HashSet};
use std::io;
use itertools::Itertools;

#[derive(Debug, Clone)]
struct Position {
    dim_r: usize,
    dim_c: usize,
    rev: String,       // Revealed cells string
    boards: Vec<String>,
}

#[derive(Default)]
struct Solver {
    /// Memo keyed by the revealed string, stores a tuple (wins, Vec<click_locations>)
    memo: HashMap<String, (u64, Vec<usize>)>,
    /// Another memo used when the number of revealed cells is within a certain threshold
    restart_memo: HashMap<String, (u64, Vec<usize>)>,
    /// Count how many times we've called memoBestClick
    memo_counter: usize,
    /// Count how many times we've restarted the memo
    restart_counter: usize,
    /// Maximum number of revealed cells difference to check for restarts
    restart_max: usize,
}

impl Solver {
    /// Create a new Solver with defaults pre-initialized
    fn new() -> Self {
        let mut solver = Solver::default();
        solver.restart_max = 6;
        solver
    }

    /// Main "memoBestClick" logic
    fn memo_best_click(&mut self, pos: &Position) -> (u64, Vec<usize>) {
        self.memo_counter += 1;
        if !self.memo.contains_key(&pos.rev) {
            // ... same mirror checks as before ...

            let unrevealed_count = pos.rev.matches('_').count();
            let already_revealed = pos.rev.len() - unrevealed_count;
            if already_revealed <= self.restart_max {
                // Fix #1 for move error: clone the result before storing
                let best = pos.some_best_click(self);
                self.restart_memo.insert(pos.rev.clone(), best.clone());
                self.memo.insert(pos.rev.clone(), best.clone());
                return best;
            }

            // If the memo grows too large, we "restart" it
            if self.memo.len() > 5 * 10_usize.pow(6) {
                self.memo = self.restart_memo.clone();
                self.restart_counter += 1;
            }

            // Fix #2 for move error: clone the result before storing
            let best = pos.some_best_click(self);
            self.memo.insert(pos.rev.clone(), best.clone());
            return best;
        }
        // Return from memo
        self.memo[&pos.rev].clone()
    }
}

/// Reverse the board vertically
fn vertical_reverse(s: &str, rows: usize, cols: usize) -> String {
    let mut lines: Vec<&str> = Vec::new();
    for r in 0..rows {
        let start = r * cols;
        let end = start + cols;
        lines.push(&s[start..end]);
    }
    lines.reverse();
    lines.into_iter().collect()
}

/// Reverse the board horizontally
fn horizontal_reverse(s: &str, rows: usize, cols: usize) -> String {
    let mut reversed = String::new();
    for r in 0..rows {
        let start = r * cols;
        let end = start + cols;
        let row_str: String = s[start..end].chars().rev().collect();
        reversed.push_str(&row_str);
    }
    reversed
}

impl Position {
    fn new(dimensions: (usize, usize), revealed: String, boards: Vec<String>) -> Self {
        let (dim_r, dim_c) = dimensions;
        assert_eq!(revealed.len(), dim_r * dim_c);
        Position {
            dim_r,
            dim_c,
            rev: revealed,
            boards,
        }
    }

    /// Equivalent to the Python "click" method
    fn click(&self, loc: usize) -> Vec<Position> {
        // Must be an unrevealed cell ('_') to click
        assert_eq!(self.rev.chars().nth(loc).unwrap(), '_');

        // Separate boards according to what's at the clicked location
        let mut board_dict: HashMap<char, Vec<String>> = HashMap::new();
        for board in &self.boards {
            let clicked_cell = board.chars().nth(loc).unwrap();
            board_dict.entry(clicked_cell).or_default().push(board.clone());
        }

        // Build new positions by revealing the clicked cell with the char from each board set
        let mut new_positions = Vec::new();
        for (ch, boards_for_ch) in board_dict {
            let mut new_rev = self.rev.clone();
            // replace the single character
            unsafe {
                new_rev.as_mut_vec()[loc] = ch as u8;
            }
            let pos = Position::new((self.dim_r, self.dim_c), new_rev, boards_for_ch);
            new_positions.push(pos);
        }
        new_positions
    }

    /// Equivalent to Python's "someBestClick" method
    ///
    /// Returns:
    ///   (best_wins, best_click_list)
    fn some_best_click(&self, solver: &mut Solver) -> (u64, Vec<usize>) {
        // If we've already got a revealed bomb, there's no winning scenario
        if self.rev.contains('*') {
            return (0, Vec::new());
        }

        let unrevealed: Vec<usize> = self
            .rev
            .chars()
            .enumerate()
            .filter_map(|(i, c)| if c == '_' { Some(i) } else { None })
            .collect();

        // If only one board is possible, reveal all non-bomb squares
        if self.boards.len() == 1 {
            let board = &self.boards[0];
            let safe_squares = unrevealed
                .into_iter()
                .filter(|&loc| board.chars().nth(loc).unwrap() != '*')
                .collect::<Vec<_>>();
            return (1, safe_squares);
        }

        // If there's a cell that's safe in ALL boards, click it
        for &loc in &unrevealed {
            if self.boards.iter().all(|b| b.chars().nth(loc).unwrap() != '*') {
                // Summation of wins after we click “loc”
                let mut sum_wins = 0;
                for new_pos in self.click(loc) {
                    // Only count if the revealed cell is not '*'
                    if new_pos.rev.chars().nth(loc).unwrap() != '*' {
                        let (wins, _) = solver.memo_best_click(&new_pos);
                        sum_wins += wins;
                    }
                }
                return (sum_wins, vec![loc]);
            }
        }

        // Otherwise, try all possible unrevealed locations
        let mut click_list = Vec::new();
        let mut most_wins = 0u64;

        for &loc in &unrevealed {
            let mut sum_wins = 0;
            for new_pos in self.click(loc) {
                // Only count if the revealed cell is not '*'
                if new_pos.rev.chars().nth(loc).unwrap() != '*' {
                    let (wins, _) = solver.memo_best_click(&new_pos);
                    sum_wins += wins;
                }
            }

            if sum_wins > most_wins {
                most_wins = sum_wins;
                click_list.clear();
                click_list.push(loc);
            } else if sum_wins == most_wins {
                click_list.push(loc);
            }
        }

        (most_wins, click_list)
    }
}

/// Equivalent to Python's "makeBlankPosition"
fn make_blank_position(dimensions: (usize, usize), mines: usize) -> Position {
    let (dim_r, dim_c) = dimensions;
    let mut boards = Vec::new();

    // All possible mine placements (combinations of loc)
    // Note: loc is used as a single index. We'll convert to (x, y) by (loc % dim_c, loc / dim_c).
    let all_locs = (0..dim_r * dim_c).collect::<Vec<_>>();
    for combo in all_locs.into_iter().combinations(mines) {
        let mine_set: HashSet<usize> = combo.into_iter().collect();
        let board = make_board_from_mines(dimensions, &mine_set);
        boards.push(board);
    }

    let revealed = "_".repeat(dim_r * dim_c);
    Position::new(dimensions, revealed, boards)
}

/// Equivalent to Python's "makeBoardFromMines"
fn make_board_from_mines(dimensions: (usize, usize), mine_layout: &HashSet<usize>) -> String {
    let (dim_r, dim_c) = dimensions;

    let mut board = String::new();
    for loc in 0..(dim_r * dim_c) {
        if mine_layout.contains(&loc) {
            board.push('*');
        } else {
            // Count adjacent mines
            let r = loc / dim_c;
            let c = loc % dim_c;
            let mut count = 0;
            for (dr, dc) in [
                (-1, -1),
                (-1, 0),
                (-1, 1),
                (0, -1),
                (0, 1),
                (1, -1),
                (1, 0),
                (1, 1),
            ] {
                let nr = r as isize + dr;
                let nc = c as isize + dc;
                if nr >= 0
                    && nr < dim_r as isize
                    && nc >= 0
                    && nc < dim_c as isize
                {
                    let adj_loc = (nr as usize) * dim_c + (nc as usize);
                    if mine_layout.contains(&adj_loc) {
                        count += 1;
                    }
                }
            }
            board.push(std::char::from_digit(count, 10).unwrap());
        }
    }
    board
}

/// Equivalent to Python's "makePosition"
fn make_position(dimensions: (usize, usize), mines: usize, revealed: &str) -> Position {
    let blank = make_blank_position(dimensions, mines);
    let mut boards_subset = Vec::new();

    'outer: for board in &blank.boards {
        for (i, ch) in revealed.chars().enumerate() {
            if ch != '_' && ch != board.chars().nth(i).unwrap() {
                // This board doesn't match the "revealed" pattern
                continue 'outer;
            }
        }
        boards_subset.push(board.clone());
    }
    Position::new(dimensions, revealed.to_string(), boards_subset)
}

/// Note the added lifetime parameter 'a
fn win_rate<'a>(
    solver: &'a mut Solver,
    dimensions: (usize, usize),
    mines: usize,
    revealed: &'a str,
) -> (u64, usize, Vec<usize>, &'a HashMap<String, (u64, Vec<usize>)>) {
    let pos = make_position(dimensions, mines, revealed);
    solver.memo.clear();
    let (wins, moves) = solver.memo_best_click(&pos);
    (wins, pos.boards.len(), moves, &solver.memo)
}


fn main() {
    let dim_r: usize = 4;
    let dim_c: usize = 4;
    let mines_count: usize = 4;
    let revealed_str_clean= "________________";

    // Now we run the solver
    let mut solver = Solver::new();
    let start_time = std::time::Instant::now();
    let (wins, total_boards, moves, memo_map) =
        win_rate(&mut solver, (dim_r, dim_c), mines_count, revealed_str_clean);
    let duration = start_time.elapsed().as_secs_f64();

    // Convert move indexes into (row, col)
    let move_points: Vec<(usize, usize)> =
        moves.iter().map(|&m| (m / dim_c, m % dim_c)).collect();

    println!(
"Best moves are {:?}.
{} wins out of {} boards. Ratio of {}.
{} positions searched.
{} seconds taken.",
        move_points,
        wins,
        total_boards,
        wins as f64 / total_boards as f64,
        memo_map.len(),
        duration
    );
}