I've noticed while playing Minesweeper that when I have too few bombs, I get very easy to play games. In other words, I get games that can be solved with very simple algorithms. When I play games with too many bombs, I get unsolvable games or games that can't be solved without guessing.
There seems to be a region in the middle(not too few, not too many), where some games are solvable but require increasingly complex algorithms. I've also read that Minesweeper is NP-complete, which I take to mean that there is no upper bound to how complex these algorithms can be as n, in an n-by-n game of Minesweeper, is allowed to grow. This seems relevant to information processing(halting problem?) but not exactly sure how.
First, is my phrasing correct? And second, where can I search for clarification in my thinking?
"Increasingly complex algorithms" isn't quite right. There's a simple algorithm to solve any board: Enumerate all possible mine configurations and identify the configuration(s) consistent with all the known clues.
This brute force algorithm is not polynomial-time, though. (It's exponential-time, because the number of mine configurations grows exponentially with the size of the board.) NP-completeness is about polynomial-time algorithms.
"Minesweeper is NP-complete" means the decision problem of determining whether a given Minesweeper puzzle has a solution is NP-complete. The proof (that this problem is NP-hard) includes a way to build Minesweeper puzzles that act like digital logic circuits, so that a hypothetical Minesweeper solver could be used to solve arbitrary boolean satisfiability problems of comparable size. In this sense, Minesweeper puzzles can encode arbitrarily complex logic.