Battleships: Adding undo, autosolve, and a toolbar

I’ve been thinking lately of making my Battleships program more robust by having a complete autosolver and a random puzzle creator. The first step was programming a step that would do the simple stuff:

  • If a row has n remaining water cells and n remaining empty cells, all the remaining cells have to be water. Ditto for columns, ditto for ships.
  • If a cell has a ship segment, then the neighboring four corners have to be water.
  • Certain neighboring cells can be filled in based on clued ship segments.

These generally solve the easiest “Seaman” Battleships puzzles, and go a long way to solving the harder ones. The harder ones require an additional bit of programming through trial-and-error placement, which I’m still mulling around in my mind. The simplest bits, though, are rote enough that I added a command to the program to process it.

Since I was tooling around in the program, I decided to make a few other tweaks as well. One was adding an undo. It occurred to me that, because the data was of a different sort, undo and save weren’t interrelated in the same way as with Canfield. With Canfield, undo required recording the entire state of the card deck, including which piles everything was located on, so saving was a variation on that theme.

However, with Battleships, undo only requires recording the state of the grid; so long as I didn’t need to undo across loading a puzzle, the clues themselves don’t need recording. Save would require recording the state of the grid, the clues, and the source of the puzzle (so that if the saved file is later loaded and finished, that fact can be recorded). Since undo was simpler, I decided to allow for multiple undo steps.

First I created a list of arrays:

List<int[,]> alSnapshots = new List<int[,]>();

I had intended to simply assign a new list to the current grid status before making any changes to the grid:

alSnapshots.Add(iCellStatus);

One thing I was reminded of quickly was that equating arrays results in a reference assignment, not a value assignment. That is, the code above results in a list populated with pointers to iCellStatus, so when it changes, each member of the list changes as well. That obviously wasn’t what I desired, so I had to get a bit more explicit:

private void TakeSnapshot()
{
    int[,] iSnapShot = new int[GridSize, GridSize];
    for (int x = 0; x < GridSize; x++)
    {
        for (int y = 0; y < GridSize; y++)
        {
             iSnapShot[x, y] = iCellStatus[x, y];
        }
    }
    alSnapshots.Add(iSnapShot);
    if (alSnapshots.Count > 20) // Only save 20 steps
    {
        alSnapshots.RemoveAt(0);
    }
}

I arbitrarily chose 20 as the max number of undoes; each snapshot doesn’t take up that much memory.

This illustrates how to create and use a List consisting of arrays (in this case, a two-dimensional integer array). I have an additional method to clear the array, when a new puzzle is loaded:

private void ClearSnapshots()
{
    alSnapshots.Clear();
}

Allowing for redo would require a small modification to TakeSnapshot.

I also added a toolbar, using some free icons; the revised program is available on my website.

Advertisements
Posted in Battleships, C#, Grid-based | Tagged , , , | Leave a comment

English modals and negation

English modals are a strange enough beast among themselves, but adding in negation leads to especially treacherous waters. This post will restrict itself to the four most common, and possibly most confusing: May, can, must, and have to.

May

“May” as a modal is ambiguous between permission and possibility:

1. You may have some dessert if you finish your meal.
2. It may rain tomorrow.

It’s easy enough to conceptualize how this ambiguity started. Both senses are actually forms of permissibility: In (1), the speaker is granting permission; in (2), the universe is granting permission. However, pragmatically, the second sense has a feeling of conjecture, implying that the speaker believes that there’s a decent likelihood of the event happening (it would be strange, for instance, to hear [2] in Juneau in January, since the likelihood of rain instead of snow would be very low, even though the sentence would be semantically true).

More curiously, the scope of “not” is different based on the sense. In the case where permission is being granted, “not” has greater scope than “may” (unless the context is forced):

3. You may not have any pie because ....
-> NOT (ALLOWED (you have pie))...

while the probabilistic version of “may” has greater scope than “not”:

4. He may not call tonight.
-> COULD BE (NOT (he calls tonight))

In (3), what is negated is the permission to do something, as opposed to having permission to not do something, which is a possible but fairly forced use of “may”:

3a. Child: What if I don't want to eat my spinach?
Parent: Well, you may not eat your spinach, but if you don't,
you won't get any dessert.
-> ALLOWED (NOT (you eat your spinach))

In this case, the scope is the same as the probabilistic “may.” Note that the probabilistic “may” cannot combine with “not” such that the latter has scope, that is, there is no way to parse (4) in such a way that it is not possible that he could call.

Can

“Can” as a modal is ambiguous between ability and permissibility. In the latter sense, it’s roughly synonymous with the first sense of “may”:

5. I can lift half my own weight.
2a. You can have some dessert if you finish your meal.

In the case of “can,” the normal scope of negation is the same as with the first sense of “may,” that is:

5'. I can't lift half my own weight.
-> NOT (ABLE (I lift half my own weight.))
2a'. You can't have any dessert.
-> NOT (ALLOWED (You have dessert.))

However, a potential for confusion is in the use of “cannot” vs “can not.” “Cannot” is unambiguous with regards to scope, as is “can’t”; “can not” is ambiguous between this scope and the opposite one, which requires a context, as with “may,” but is more common in the forced context:

6. Child: Well, what can I do when all my friends are smoking?
Parent: You can not join them, simple as that.

In (6), the parent is not telling the child what they cannot do, but rather offering a suggestion of what they can do, specifically, they can fail to join their friends in smoking. Without the space (and the corresponding emphatic breath in the spoken version), the parent would indeed be denying permission:

6'. Child: Well, what can I do when all my friends are smoking?
Parent: You cannot join them, simple as that.

Must

“Must” is also ambiguous. Its two main senses, parallel to those of “may,” are those of obligation and likelihood:

7. You must finish your dinner.
8. He must see me, because he waved.

However, “not” does not behave as we would predict from “may.” In the case of obligation, the scope is the opposite:

7'. You must not finish your dinner.
-> REQUIRED (NOT (You finish your dinner.))

Effectively, that means “must not” and “may not” are synonymous, inasmuch “you are required not to…” means the same as “you are not allowed to….”

With the probabilistic sense of “must,” it’s not definitive what the scope is, because “it’s not likely that it’s the case that…” and “it’s likely that it’s not the case that…” mean generally the same thing, particularly to the sort of binary likelihoods normally referred to in this context (such as in [8]).

Have to

In the positive sense, “have to” and “must” are interchangeable:

7". You have to finish your dinner.
8'. He has to see me, because he waved.

Pragmatically, “have to” is generally more colloquial than “must,” and hence is more likely to appear in casual frames (as in “I have to go now” vs the stiffer-sounding “I must go now”).

More interestingly (and consternating, no doubt, for the second language learner), “must not” is not interchangeable with “don’t have to.” In the obligatory sense, each is unambiguous, and they have opposite scopes, and therefore different meanings:

7"'. You don't have to finish your dinner.
-> NOT (REQUIRED (You finish your dinner.))

That is, while 7′ forbids the audience (“you”) from finishing dinner, 7″‘ merely removes obligation from the audience to finish dinner.

Another interesting point is that, while “haven’t” is acceptable English, “not” cannot be inserted in “have to,” hence the use of “don’t.” Alternatively, “not” could be placed after “have to,” although this is awkward and usually works best in the context where someone is responding to a positive use of “have to”:

9. Child: What do I have to do to get you off my back?
Parent: You have to not watch TV when you're supposed
to be doing your homework.

This is a pragmatically tricky case, though, because while it semantically means about the same as “you must not watch TV…,” the focus is on the obligation to avoid doing something as opposed to an overt prohibition.

Meanwhile, the probabilistic sense of “have to” in the negative form is non-standard:

10. He must not see me, because he didn't wave.
10'. *He doesn't have to see me, because he didn't wave.

However, “have to” can be used if the scope is explicit, and with a minor change to tense:

10". He has to have not seen me, because he didn't wave.
-> LIKELIHOOD (NOT (he saw me)) ...

This is particularly interesting given the note under discussion of “must” that the scope between likelihood and negation is semantically trivial.

Posted in English | Tagged , , , , | Leave a comment

It’s the little things…

Doing some code clean-up on Battleships this morning, I was reminded of a detail of C# logic precedence that I’ve used to my benefit elsewhere (including within the program), but which caused a brief hiccup in one instance. Specifically, while the logical and and or operators are transitive, that’s not strictly true of && and ||.

In this case, I had broken my large and increasingly complex ResetGrid method into several smaller ones. I have a boolean variable, blnAllDone, which indicates whether the current puzzle has been solved. I created the subroutines which count the remaining cells and the remaining ships to return a boolean value, which would be true if the remaining cells or ships is zero,  false otherwise. This was the original code:

bool blnAllDone = CalcRemainVals();
blnAllDone = blnAllDone && CalcRemainShips();

However, the CalcRemainShips method only ran if the puzzle was complete. As soon as I looked again at the code, I realized why: C# stops assessing x && y if x is false (since x && y can’t be true if x is false), and returns false. Likewise, c# stops assessing x || y if x is true, and returns true. This is a useful feature if you want to shortcut situations where a variable might not be set, for instance, but in this case it led to unexpected results.

I made a minor change, and all was well with the world again:

bool blnAllDone = CalcRemainVals();
blnAllDone = CalcRemainShips() && blnAllDone;
Posted in C# | Tagged | Leave a comment

Programmatically adding XAML elements in C#

I had originally hard-coded the grid in my Battleships program. This resulted in very repetitive code, since there were 100 cells that contained the same basic information, but I didn’t want to get too bogged down in UI programming matters until I was satisfied with the program overall.

Since I was happy with the Battleships program, but in anticipation of working on a Paint-by-Numbers program, I wanted to make sure I had an understanding of how to create the WPF cells through the C# code. Here is the XAML code (repeated 100 times, where the name is gridxy:

<Grid Name="grid99" Grid.Row="9" Grid.Column="9"
  MouseLeftButtonUp="Cell_LeftClick"
  MouseRightButtonUp="Cell_RightClick">
  <Rectangle Style="{StaticResource BlueBorder}">
  <Path Name="cell99" Style="{StaticResource Ship}"
    Data="{StaticResource Empty}">
</Grid>

Here is the corresponding C# code (note that Ocean is the name of the 10×10 puzzle grid):

Grid aGrid = new Grid();
Rectangle aRectangle = new Rectangle();
aRectangle.Style=(Style)FindResource("BlueBorder");
aGrid.Children.Add(aRectangle);

Path aPath = new Path();
aPath.Name = string.Format("cell{0}{1}", iRow, iCol);
aPath.Style = (Style)FindResource("Ship");
aPath.Data = (GeometryGroup)FindResource("Empty");
aGrid.Children.Add(aPath);
pthCells[iRow, iCol] = aPath;

aGrid.Name = string.Format("grid{0}{1}", iRow, iCol);
Grid.SetRow(aGrid, iRow);
Grid.SetColumn(aGrid, iCol);
aGrid.MouseLeftButtonUp += Cell_LeftClick;
aGrid.MouseRightButtonUp += Cell_RightClick;
Ocean.Children.Add(aGrid);

This is embedded in two for loops (iRow and iCol). It’s obvious when comparing these two snippets why the XAML is normally preferable, for several reasons. The code is shorter (even repetitive code can be cut-and-pasted fairly simply), and different variable types are treated the same way by XAML: Always the field/value structure.

An additional obstacle that I found is that the name of components created programmatically don’t appear to show up in FindName. The workaround is straightforward enough, though. By defining arrays of the appropriate type (e.g.,

Path[,] pthCells = new Path[GridSize, GridSize];

I could then refer to the appropriate array element, which was object-linked to the grid element.

Another hurdle was creating the row and column definitions with specific heights and widths (respectively). Intuitively, I thought that a single column/row definition, once created, could be reused; that isn’t true. Also, the width/height specification is not in fact a numeric value, but rather it’s of type GridLength. Hence, this was the needed code:

GridLengthConverter aGLConv = new GridLengthConverter();
GridLength aGL = (GridLength)aGLConv.ConvertFrom(34);
int iRow, iCol;
for (iRow = 0; iRow < GridSize; iRow++)
{
    ColumnDefinition aColDef = new ColumnDefinition();
    aColDef.Width = aGL;
    Ocean.ColumnDefinitions.Add(aColDef);
    RowDefinition aRowDef = new RowDefinition();
    aRowDef.Height = aGL;
    Ocean.RowDefinitions.Add(aRowDef);

    ColumnDefinition aColClueDef = new ColumnDefinition();
    aColClueDef.Width = aGL;
    ColClueBox.ColumnDefinitions.Add(aColClueDef);
    RowDefinition aRowClueDef = new RowDefinition();
    aRowClueDef.Height = aGL;
    RowClueBox.RowDefinitions.Add(aRowClueDef);
...

A little odd, in my opinion, but that’s the way it is.

Posted in Battleships, C#, Grid-based | Tagged , , | Leave a comment

Including external files in a C# ClickOnce deployment

The first version of my Battleships program is done. I’ll be releasing it into the wild today or tomorrow. One hurdle I stumbled over was on how to include XML files as external files in the ClickOnce deployment. My normally strong GoogleFu is weak on matters of C#; I’m not sure if that’s due to a paucity of quality information, or personal lapses.

I designed the Battleships puzzle files to be easy to upgrade, so someone who enjoys using the program can create their own puzzle files, perhaps from a magazine source (I’m not sure if Kappa [Games] is the sole publisher of these puzzles, and at any rate they have been running for them for a while and I’m not going through my entire back catalog). Puzzle files are in XML format, with hopefully superficial tags and structure.

As part of the deployment, I’m including two puzzle files, containing the puzzles from the May 2010 and July 2010 issues of Games Magazine. It turns out there are several settings that need to be changed from the default in order to accomplish this.

External Resource Step 1

The resources tab

First, and perhaps most obviously, the files need to be added as a resource. Do this by going to Project>[Program] Properties…. Select the Resources tab along the left, then Select Files from the first drop down, click Add Resource, and select the files you want (note that the default is to only list text files; for other types of files, change the option). Select the files that you want; if your resources are in a subdirectory (as mine are), VC# will use a relative path and maintain the subdirectory structure.

Added resources

Resources in the Solution Explorer

The resources are now available to the solution, but they won’t be available for either debugging or deployment; they’d have to be manually copied. The next step is to change the properties of each file. Note that you can change the properties of multiple files by ctrl-selecting them. Right-click and select Properties (or press Alt-Enter), then set Build Action to Content and Copy to Output Directory to Copy Always. This will copy the files to the debugging subdirectory at compile time, but they still won’t be available in a ClickOnce deployment.

Deploying external resources

Including external resources in the deployment

Finally, return to the project properties window and select the Publish tab. Select Application Files…. Change the Publish Status to Include. Now, when you publish, the resource files should be included in three places: bin/Debug, bin/Release/.. , and  publish/Application Files/[Program and Version], as well as being including in online ClickOnce deployments.

Posted in Battleships, C#, Grid-based | Tagged , | Leave a comment

Battleships in C#

My current C# project is to create a Battleships program that would allow easy input of grids and on-screen solving.

An unsolved Battleships puzzle

An unsolved Battleships puzzle

I find myself strongly preferring online solving of this sort of puzzle to doing it on paper. Conceptis has an online solver, but I wanted to also be able to solve the puzzles in Games in the same manner.

Battleships is a grid-based logic puzzle based on the popular (and more familiar) two-person peg game. In the puzzle, the solver is presented with a square grid with numbers on the side and bottom, and some number of spaces already filled in. The goal is to place the “ships” (listed at the bottom of the grid) in such a way that the number on the sides of the grids represents the number of segments in that row or column, each ship is used once, and no two ships touch each other, even diagonally. The puzzle shown is from the July 2010 issue of Games.

Solved Battleships puzzle

Solved Battleships puzzle

I started with the UI, which is written in WPF/XAML. I knew that this would be significantly more work than my Canfield program. Each grid, as well as the row and column numbers, would need to be clickable, there would need to be an easy way to specific “ship” or “water” for spaces, and the ship pieces would need to automatically change shape based on their neighbors. On the other hand, while Canfield uses uploaded PNG files for the graphics, Battleships uses path files drawn by the program itself.

For the ship pieces, I am using GeometryGroups specified in the Window.Resources of the XAML file. For instance, this is the right end of a ship:

    <Window.Resources>
        <GeometryGroup x:Key="RightCap">
            <CombinedGeometry GeometryCombineMode="Union">
                <CombinedGeometry.Geometry1>
                    <RectangleGeometry Rect="0,0 15,30" />
                </CombinedGeometry.Geometry1>
                <CombinedGeometry.Geometry2>
                    <EllipseGeometry Center="15,15"
                    RadiusX="15" RadiusY="15" />
                </CombinedGeometry.Geometry2>
            </CombinedGeometry>
        </GeometryGroup>
    </Window.Resources>

When I want to use that group in a particular cell, I update it via the C# code.

for (x = 0; x < 10; x++)
{
    for (y = 0; y < 10; y++)
    {
        Cells[x, y] = (Path)FindName(string.Format("cell{0}{1}", x, y));
     }
}

To begin with, I’m programming Battleships at a set 10×10 size, which is the standard for Games magazine; once I’m done, I may double back and include other sizes, or I may move on to other grid-based logic puzzles.

Initially, each cell in the main grid contained just the path piece. Unfortunately, though, cells were only clickable on the visible portion of the path, meaning that empty cells (which contain an empty GeometryGroup) were unclickable. Also, I wanted an internal visible grid of blue lines. So now each cell of the grid contains a grid of its own (implicitly 1×1), which contains a rectangle (for the fill and border) and a path piece:

<Grid Name="grid00" Grid.Row="0" Grid.Column="0"
    MouseLeftButtonUp="Cell_LeftClick"
    MouseRightButtonUp="Cell_RightClick">
    <Rectangle Style="{StaticResource BlueBorder}" />
        <Path Name="cell00" Style="{StaticResource Ship}"
            Data="{StaticResource Empty}" />
</Grid>

As the code illustrates, a ship piece is selected (or cleared) by clicking the left mouse button and a water piece by clicking the right mouse button. I thought about doing a rotation (a left click puts a ship in an empty spot, water in a ship spot, or clears a water spot), but I decided I preferred this method.

To create the map of sample ships at the bottom, I initially tried to scale the playing pieces to 50%, but that didn’t work; when WPF set the pieces next to each other, space was reserved for the full 100% width, leaving large white spaces. I’m sure there’s some method I could have used to get the results I wanted, but I eventually gave up playing with it and created a second set of GeometryGroup elements, scaled down.

Battleships midgame

Battleships, while solving

I decided to go old school when indicating a cell’s status as either a clue (solid ship, dark blue water) or a guess (gray ship, light blue water). Rather than creating a class with a status attribute, I’m using 1-7 for clue pieces and 11-17 for guess pieces; hence, my code makes liberal use of the % operator. (I also have room in the code for a “commit” status, so that guesses that are firm [11-17] can be visually differentiated from trial-and-error guesses [21-27].)

I’ve programmed the basic UI, although it still needs a little tweaking. To finish up, I also need to program the module that loads in a puzzle (right now, the puzzle is hard-coded, for testing purposes), as well as creating a help file and other minor enhancements.

Posted in Battleships, C#, Grid-based | Tagged , , , , , | Leave a comment

Rubik’s 5x5x5 (Professor) and TouchCube

I’m old enough to have been around during the first release of the Rubik’s Cube, back in the 1970s. I was something of an aficionado at the time, owning a Rubik’s Cube, the 4x4x4 Rubik’s Revenge, and a drawerful of other Rubik inventions and inspirations. Eventually, I moved on to other interests, and the drawer got busy collecting dust.

I recently picked up two additional entries in the Rubik’s universe, the TouchCube and the 5x5x5 Rubik’s Professor.

The TouchCube’s price has dropped considerably from its release last year; its MSRP is $150, but it can be gotten fairly easily (as I did) for a third of that. That’s not surprising to me, because while it’s a pretty little gizmo, it doesn’t add much to the traditional solving experience, and it can be very frustrating.

It contains an accelerometer, so that moves can allegedly only be made on the top side, but its touch sensitivity can be erratic, causing both unintended moves and unregistered intended moves. Indeed, for me, the added challenge of the TouchCube was how long it would take me to solve it, even though I’m reasonably good at solving a traditional cube. Several times, I’d come close only to have the touch sensitivity and the limitation of moves to the top side only conspire to confuse me and cause me to lose my place.

Overall, the TouchCube is far more useful as an objet d’art than as a functional puzzle. The good news at our house is that our one-year-old son is entranced by it, meaning it can act as a decent distraction device.

The Professor is more interesting. Like the Revenge, solving the Professor consists of two major steps: Aligning the cubes so that you have an unsolved 3x3x3 Rubik’s Cube, and then solving the Cube.

The Revenge has a so-called parity issue: Once you solve it to a Cube state, it’s possible that one pair of edge cubes is reversed. This can’t be easily detected until the Cube has been solved. I seem to recall there’s some sort of method for reversing the pair, but I prefer to minimize the number of things I actually have to memorize, so when I ran into the parity issue I’d just scramble the Revenge and start again.

The Professor also has a parity issue, but it’s much easier to detect. Once you have the Professor solved to an embedded scrambled Cube, it can be solved using standard Cube strategy, every time. For this reason, I’m left with the impression that the Professor is actually easier than the Revenge to solve, but that may also have something to do with the decades that have elapsed since I last tried a Revenge.

There are various tutorials online on how to solve the Professor and the Cube. These are my strategies, meant as I said to minimize what I have to actually memorize. I’m not trying to solve as quickly as possible; rather, my goal is relaxation and fun.

The first major step to solving the Professor is to move the cubes around to create a scrambled Cube. At the end of this step, the 9 squares at the center of each side will be a single color, and the 3 non-corner edge pieces on each of the 12 edges will be matched. (There are apparently accepted names for each of these individual cubes, but I’m not one for jargon. Minimal memory and all that.)

To accomplish this first major step, first complete these minor steps, in order:

  1. Pick a color and solve the 3×3 center. This is the easiest step.
  2. Solve the opposite 3×3 center.
  3. Pick one of the remaining four colors and, without disturbing the first two colors, solve its 3×3 center.
  4. Pick one of the remaining three colors and solve.
  5. The preceding steps are fairly easy, albeit increasingly difficult. Finally, solve the 3×3 centers for the remaining two sides. This can be a bit more difficult and frustrating, but through trial and error and practice, you’ll get there.

At this point, you’ll have solid 3×3 centers on all six sides, but the edge pieces will be mixed up. Look for trios and put them together, always being careful to return the 3×3 centers after each trio is grouped. Keep in mind that you don’t have to put the trios in the correct place at this point, just that you want to group all the edge trios together.

What I do is pick opposing sides (orange and red, for instance) and use these to hold the grouped trios. There are twelve trios to group, and this allows me to hold eight of them, leaving the four in the center still messed up.

The Professor can then be solved to the scrambled Cube state using a single memorized algorithm and a bit of patience. Looking down on the cube:

  1. Rotate the two levels closest to your body one rotation to the right (clockwise on the axis).
  2. Rotate the one level closest to your right one rotation toward your body (counterclockwise on the axis).
  3. Rotate the one level closest to your body one rotation to the right (clockwise on the axis).
  4. Rotate the one level closest to your right one rotation away from your body (clockwise on the axis).
  5. Rotate the two levels closest to your body one rotation to the left (counterclockwise on the axis).

This algorithm affects only three trios, leaving the other nine intact. The trios affected are the ones to the left and right of the top level and the one on the left side of the cube closest to your body.

It is possible to solve two of the four remaining trios and have the other two unsolved. This is the parity problem of the Professor, and there’s a shortcut for solving it, but in my own experience (and despite what the tutorials I’ve seen have said), I’ve found that it’s possible to resolve the parity through a little bit of forethought, without having to use the shortcut. By all means, though, memorize the shortcut if you prefer.

Once you’ve grouped all twelve trios, you have a Rubik’s Cube with a fat middle level. It can now be solved according to whatever technique you prefer. (I may post my own technique at a later date, for whatever it’s worth.)

Posted in Rubik | Tagged , , , | 1 Comment