What can't C#?

Posted by Dillon Reedy on 2016-12-09

A Person with a Presbyopia (I’m not all laughs)

Here’s how to make a BFS in C#

C# is a nicer version of Java in my opinion, and to me it is similar to VB.Net. For this post, I’m gonna walk through the breadth first searches that my version of minesweeper required me to make, in C#. I’m not gonna go through every line of code, but for anyone wanting to look at my application feel free.

My version of minesweeper tells the user where the mines are and also what cells are clickable. Our end result is going to look like this:

NOTE: This will not be able to determine ambiguous situations, therefore this solution will only determine the locations of mines that are not ambiguous.

A Red Green Board

I created a board that I appropriately called a “Red Green Board” that I used to determine what buttons are red and which ones are green. You could imagine this board:

looking like this in a character matrix:
{{‘0’, ‘1’, ‘G’, ‘U’},
{‘0’, ‘2’, ‘R’, ‘U’},
{‘0’, ‘2’, ‘R’, ‘U’},
{‘0’, ‘1’, ‘G’, ‘U’}}

As we can notice, colored locations only surround numbered locations and nowhere else. So why don’t we begin by getting all the numbered locations on the board? I just used the old fashion brute force way of using 2 for loops to get every numbered point.

NOTE: We’re getting these points before the board is colored, therefore we only have to filter out zero and unknown locations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public char[,] GetRedGreenBoard()
{
List<Point> numberedPts = new List<Point>();
for (int i = 0; i < R; i++)
{
for (int j = 0; j < C; j++)
{
if (!board[i, j].Equals('0') && !board[i, j].Equals('U'))
{
numberedPts.Add(new Minesweeper.Point(i, j));
}
}
}
return ColorInBoard(numberedPts);
}

The ColorInBoard function takes in a list of the numbered points and returns back a character matrix with characters ‘R’ and ‘G’. What’s important to note here is when to mark the board red (which is when the number of unknown surrounding cells is equal to the current point’s number) and when to color in the board as green (when the number of surrounding red cells is equal to the current points number).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public char[,] ColorInBoard(List<Point> numberedPts)
{
bool changed = true;
while (changed)
{
changed = false;
foreach (Point p in numberedPts)
{
List<Point> surroundingPts = GetSurroundingPointsInBounds(p);
int numOnBoard = Int32.Parse(board[p.x, p.y] + String.Empty);
int numUnknownPts = CountNumberOfCharOnBoard(surroundingPts, 'U');
int numMinePts = CountNumberOfCharOnBoard(surroundingPts, 'R');
if (numOnBoard == numMinePts && numUnknownPts > 0) MarkAllPointsWithChar(surroundingPts, 'G', ref changed);
if (numOnBoard == (numUnknownPts + numMinePts)) MarkAllPointsWithChar(surroundingPts, 'R', ref changed);
}
}
return board;
}

The way that we go about getting the surrounding points of a given center point. This has to be my favorite part of the program from how well I simplified the math.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public List<Point> GetSurroundingPointsInBounds(Point curPt)
{
List<Point> surroundingPts = new List<Point>();
int[] xs = { 1, 1, 1, 0, 0, -1, -1, -1 };
int[] ys = { 1, 0, -1, 1, -1, 1, 0, -1 };
for (int i = 0; i < xs.Length; i++)
{
Point testPt = new Minesweeper.Point(curPt.x + xs[i], curPt.y + ys[i]);
if (InBounds(testPt)) surroundingPts.Add(testPt);
}
return surroundingPts;
}
public bool InBounds(Point p)
{
return (0 <= p.x && p.x < R && 0 <= p.y && p.y < C);
}

Let’s talk about what’s going on here. We are simply calculating the x and y positions of the points in the up-right, right, down-right, up, down, etc. based upon what the givenPt is in the parameters. Then we check to make sure that the possible point doesn’t go outside the bounds of the matrix.

I’ve seen people try to do what’s going on here recursively, but that often leads to issues of the point going out of bounds. I’ve found that the easiest way to comprehend what’s going on is to use for loops or while loops and to not go the recursive route.

A quick note about the “Zero Breadth First Search”, I had no idea how the actual game implemented when the user clicks on a cell and there are no mines surrounding it, and how it expands as such. I had to completely guess, but I feel like my guess really nailed it.

Anyways, the idea of the Zero Breadth First Search is that if the user clicks on a cell that is a zero, we add all the surrounding points to the search, if any of those points are zero themselves then we add their surrounding points in a like fashion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public void ZeroBFS(Point curLoc)
{
bool[,] beenHere = new bool[NUM_ROWS, NUM_COLS];
beenHere[curLoc.x, curLoc.y] = true;
Queue<Point> q = new Queue<Point>();
q.Enqueue(curLoc);
while (q.Count != 0)
{
Point curSearchPt = q.Dequeue();
List<Point> surroundingPts = GetSurroundingPointsInBounds(curSearchPt);
foreach (Point p in surroundingPts)
{
Button b = ((Button)mineButtonPanel.Controls[p.x.ToString() + p.y.ToString()]);
if (mineCount[p.x, p.y] == 0 && !beenHere[p.x, p.y]) q.Enqueue(p);
else b.Text = mineCount[p.x, p.y].ToString();
b.BackColor = Color.Gray;
b.Enabled = false;
beenHere[p.x, p.y] = true;
userState[p.x, p.y] = mineCount[p.x, p.y].ToString()[0];
}
}
}

Now see this is what I personally love about C#, in Java you have to declare such a weird variable name to get stacks or queues. In C#, it’s just the straight forward Queue object. Love that.

The above code is a culmination of my college schooling and my programming competition experience. Let’s discuss the beenHere[,] boolean matrix, it’s a simple idea all we do is mark a point as true on the board if we’ve already been there.

The queue of points gets gradually filled as we find more and more zero points, and gradually empties as we find less and less zero points.

We only enqueue points into the queue if the number of surrounding mines is zero and also if we had not already been there. This part is crucial because without the beenHere check, your outer while loop is going to go on forever. That would definitely cause some issues.

After we had determined what needed to be enqueued, we know that the button needed to be colored in gray and enabled, mark the beenHere board off as true, and update the userState board to have the character of how many surrounding mines there are.

Conclusion

I have this feeling that C# is going to be in my life for a long time, so therefore I better get used to it. Although I’m okay with this, because there is plenty about the language that I don’t know! As always contact me if you have any questions at dillon.reedy123@gmail.com