MasterMind solver

In July 2003, I wrote a blog post titled “An Excel VBA macro that solves MasterMind”. In that blog post, I presented a program that solved MasterMind. I wrote the program in VBA and it runs inside Excel. It is still in this blog, should you wish to access it. The program behaves as a person that tries to solve MasterMind, meaning that it begins by proposing a permutation. The user has to supply the number of blacks and whites for the proposed permutation, then the program proposes another permutation and so on, until the program finds the correct permutation. It will be easy for me to write that program in C#, should the need arise.

In this blog post, I am going to present another program I just wrote in C#. I call this program “MasterMind solver” and it is made specifically to solve MasterMind puzzles in the form that the puzzles site Brain Teasers provides.

I am a member of the Mathematics community in Google Plus. It is a great community and I find a lot of interesting posts there. Some posts come from the puzzles site “Brain Teasers” I mentioned above and a few of them are about MasterMind. From the Mathematics community in Google Plus I found out about these puzzles and about the puzzles site “Brain Teasers”. Actually, “Brain Teasers” has its own community on Google plus, as well: It is called with the same name as the site: Brain Teasers.

I created a C# Windows form application using Visual Studio 2005, in order to solve the MasterMind puzzles that the puzzles site “Brain Teasers” provides. The application consists of a single exe file called MMsolver.exe. There is no need to install this application. You just copy the exe file to any folder and you are good to go. It is an application with a single form and to run it, the .NET Framework v2.0 or higher is required.

If you visit the following link,  you will be able to get the executable MMsolver.exe, as well as the project/solution with the source code in the form of a zip file named MMsolver.zip.

Get the application MMsolver.exe and the source code MMsolver.zip here.

You only need MMsolver.exe in order to run the application. The zip file is for those who wish to learn how the ‘magic’ happens. Actually, I will provide a screenshot of the single form and the source code here as well.

MMsolver

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Data;
using System.Drawing;
using System.Text;
using System.Windows.Forms;

namespace MMsolver
{
   public partial class Form1 : Form
   {
      public Form1()
      {
         InitializeComponent();
      }

      private void Form1_Load(object sender, EventArgs e)
      {
         generateValidPermutations();
      }

      private void btnInsert_Click(object sender, EventArgs e)
      {
         String myPermutation = txtPermutation.Text;
         String myBlacks = txtBlacks.Text;
         String myWhites = txtWhites.Text;

         if (myPermutation.Length != 4)
         {
            MessageBox.Show("Incorrect permutation. Error 1001.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(0, 1) == "1" ||
             myPermutation.Substring(0, 1) == "2" ||
             myPermutation.Substring(0, 1) == "3" ||
             myPermutation.Substring(0, 1) == "4" ||
             myPermutation.Substring(0, 1) == "5" ||
             myPermutation.Substring(0, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1002.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(1, 1) == "1" ||
             myPermutation.Substring(1, 1) == "2" ||
             myPermutation.Substring(1, 1) == "3" ||
             myPermutation.Substring(1, 1) == "4" ||
             myPermutation.Substring(1, 1) == "5" ||
             myPermutation.Substring(1, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1003.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(2, 1) == "1" ||
             myPermutation.Substring(2, 1) == "2" ||
             myPermutation.Substring(2, 1) == "3" ||
             myPermutation.Substring(2, 1) == "4" ||
             myPermutation.Substring(2, 1) == "5" ||
             myPermutation.Substring(2, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1004.");
            txtPermutation.Focus();
            return;
         }

         if (myPermutation.Substring(3, 1) == "1" ||
             myPermutation.Substring(3, 1) == "2" ||
             myPermutation.Substring(3, 1) == "3" ||
             myPermutation.Substring(3, 1) == "4" ||
             myPermutation.Substring(3, 1) == "5" ||
             myPermutation.Substring(3, 1) == "6")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect permutation. Error 1005.");
            txtPermutation.Focus();
            return;
         }

         if (myBlacks.Length != 1)
         {
            MessageBox.Show("Incorrect number of blacks. Error 1006.");
            txtBlacks.Focus();
            return;
         }

         if (myBlacks == "0" || myBlacks == "1" || myBlacks == "2" || myBlacks == "3" || myBlacks == "4")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect number of blacks. Error 1007.");
            txtBlacks.Focus();
            return;
         }

         if (myWhites.Length != 1)
         {
            MessageBox.Show("Incorrect number of whites. Error 1008.");
            txtWhites.Focus();
            return;
         }

         if (myWhites == "0" || myWhites == "1" || myWhites == "2" || myWhites == "3" || myWhites == "4")
         {
            //Do nothing
         }
         else
         {
            MessageBox.Show("Incorrect number of whites. Error 1009.");
            txtWhites.Focus();
            return;
         }

         int intMyBlacks = Convert.ToInt32(myBlacks);
         int intMyWhites = Convert.ToInt32(myWhites);

         if (intMyBlacks + intMyWhites > 4)
         {
            MessageBox.Show("The sum of black and white circles must not be more that 4. Error 1010.");
            txtBlacks.Focus();
            return;
         }

         if (intMyBlacks == 3 && intMyWhites == 1)
         {
            MessageBox.Show("You cannot have 3 black cricles and 1 white circle. You may have 4 black circles and 0 white circles. Error 1011.");
            txtBlacks.Focus();
            return;
         }

         lsbEntries.Items.Add(txtPermutation.Text + " " + txtBlacks.Text + " " + txtWhites.Text);

         generateValidPermutations();

         txtPermutation.Text = "";
         txtBlacks.Text = "";
         txtWhites.Text = "";

         txtPermutation.Focus();
      }

      private void btnRemove_Click(object sender, EventArgs e)
      {
         if (lsbEntries.SelectedIndex > -1)
         {
            lsbEntries.Items.RemoveAt(lsbEntries.SelectedIndex);

            generateValidPermutations();
         }

         txtPermutation.Focus();
      }

      private void btnDelete_Click(object sender, EventArgs e)
      {
         if (lsbEntries.Items.Count != 0)
         {
            lsbEntries.Items.Clear();

            generateValidPermutations();
         }

         txtPermutation.Focus();
      }

      private void generateValidPermutations()
      {
         System.Collections.Generic.List<String> myInputList = new System.Collections.Generic.List<String>();
         System.Collections.Generic.List<String> myOutputList = new System.Collections.Generic.List<String>();

         lsbPermutations.Items.Clear();
         lblTotal.Text = "Total number of valid permutations = 0";

         for (int i = 1; i <= 6; i++)
            for (int j = 1; j <= 6; j++)
               for (int k = 1; k <= 6; k++)
                  for (int l = 1; l <= 6; l++)
                     myInputList.Add(i.ToString() + j.ToString() + k.ToString() + l.ToString());

         foreach (String myEntry in lsbEntries.Items)
         {
            foreach (String myPermutation in myInputList)
            {
               int a1 = Convert.ToInt32(myPermutation.Substring(0, 1));
               int a2 = Convert.ToInt32(myPermutation.Substring(1, 1));
               int a3 = Convert.ToInt32(myPermutation.Substring(2, 1));
               int a4 = Convert.ToInt32(myPermutation.Substring(3, 1));

               int myBlacksCount = 0;
               int myWhitesCount = 0;

               int b1 = Convert.ToInt32(myEntry.Substring(0, 1));
               int b2 = Convert.ToInt32(myEntry.Substring(1, 1));
               int b3 = Convert.ToInt32(myEntry.Substring(2, 1));
               int b4 = Convert.ToInt32(myEntry.Substring(3, 1));
               int b5 = Convert.ToInt32(myEntry.Substring(5, 1));
               int b6 = Convert.ToInt32(myEntry.Substring(7, 1));

               if (a1 == b1)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a1 = 0;
                  b1 = 0;
               }

               if (a2 == b2)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a2 = 0;
                  b2 = 0;
               }

               if (a3 == b3)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a3 = 0;
                  b3 = 0;
               }

               if (a4 == b4)
               {
                  myBlacksCount = myBlacksCount + 1;
                  a4 = 0;
                  b4 = 0;
               }

               if (a1 != 0)
               {
                  if (a1 == b2)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b2 = 0;
                  }
                  else
                  {
                     if (a1 == b3)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b3 = 0;
                     }
                     else
                     {
                        if (a1 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a2 != 0)
               {
                  if (a2 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a2 == b3)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b3 = 0;
                     }
                     else
                     {
                        if (a2 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a3 != 0)
               {
                  if (a3 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a3 == b2)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b2 = 0;
                     }
                     else
                     {
                        if (a3 == b4)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b4 = 0;
                        }
                     }
                  }
               }

               if (a4 != 0)
               {
                  if (a4 == b1)
                  {
                     myWhitesCount = myWhitesCount + 1;
                     b1 = 0;
                  }
                  else
                  {
                     if (a4 == b2)
                     {
                        myWhitesCount = myWhitesCount + 1;
                        b2 = 0;
                     }
                     else
                     {
                        if (a4 == b3)
                        {
                           myWhitesCount = myWhitesCount + 1;
                           b3 = 0;
                        }
                     }
                  }
               }

               if (myBlacksCount == b5 && myWhitesCount == b6)
               {
                  myOutputList.Add(myPermutation);
               }

            } // end foreach myPermutation

            myInputList.Clear();
            foreach (String myValue in myOutputList)
            {
               myInputList.Add(myValue);
            }
            myOutputList.Clear();

         } // end foreach myEntry

         foreach (String myPermutation in myInputList)
         lsbPermutations.Items.Add(myPermutation);

         lblTotal.Text = "Total number of valid permutations = " + myInputList.Count.ToString();

      } // End of generateValidPermutations procedure
   }
}

The nice thing about MMsolver is that it autoupdates the list with the valid permutations. This way, the user can experience how the number of valid permutations diminishes as she adds entry after entry of restrictions.

I tried to make MMsolver robust. Thus, MMsolver provides rudimentary checks to make sure the entries are valid. But it does not check everything, which may or may not be what the user expects. Let me explain.

The checks that MMsolver performs are the following: It checks that the permutation consists of 4 correct digits (each from 1 to 6). It also checks that the blacks and whites each consist of 1 correct digit (from 0 to 4).  But it also checks that the sum of blacks and whites does not exceed 4. And it also checks that the user does not enter a response of 3 blacks and 1 white, because something like that bears no meaning. So, these checks cover everything that has to do with the permutation alone, with the blacks alone, with the whites alone, and with the blacks and the whites viewed together. These checks do not cover the permutation with the blacks and the whites viewed together.

What this means is that an entry like 1111 1 1 will be accepted. This entry corresponds to a permutation of 1111, number of blacks = 1, and number of whites = 1. If you enter this entry, the number of valid permutations will drop to zero. This is because such an entry is illogical. You cannot have four “colors” that are the same and also have whites greater than zero. If the “colors” (digits) are all the same in a permutation, then only the number of blacks can be nonzero.

And there are other cases of illogical entries as well. For example, the entry 1112 0 3 is invalid. The same goes for the entry 1112 1 3. But MMsolver will accept all these entries as valid.

Not only that, MMsolver will not check to compare between entries. Thus, if the user enters an entry of 1234 1 1 and later enters another entry for 1234 that conflicts with the previous one, MMsolver will accept these two entries as valid, although the number of valid permutations will drop to zero. For example, the entries 1234 1 1 and 1234 1 2, are in conflict. One entry states that for that particular permutation the number of whites is 1 and the other entry states that for that particular permutation the number of whites is 2. Again, MMsolver will not check for this discrepancy.

It would not have been that difficult for MMsolver to check for these and other illogical cases, but it may be nice that it leaves all this experimenting to the user. It is just that the user has to be aware of all those issues.

Closing, I would like to present two examples that show how the program solves the MasterMind puzzles from the puzzles site Brain Teasers. I will present two puzzles from this site, featured at the time I am writing this blog post. The puzzles are their copyright.

We have the following puzzle:

mastermind-1394935204

The solution for this puzzle is:

1394935204

So, we see that this MasterMind puzzle has one valid solution: 3543.

We have the following puzzle:

mastermind-1394503204

The solution for this puzzle is:

1394503204

So, we see that this last MasterMind puzzle has three valid solutions: 4223, 4232, and 4322.

Advertisements

About Dimitrios Kalemis

I am a systems engineer specializing in Microsoft products and technologies. I am also an author. Please visit my blog to see the blog posts I have written, the books I have written and the applications I have created. I definitely recommend my blog posts under the category "Management", all my books and all my applications. I believe that you will find them interesting and useful. I am in the process of writing more blog posts and books, so please visit my blog from time to time to see what I come up with next. I am also active on other sites; links to those you can find in the "About me" page of my blog.
This entry was posted in Development. Bookmark the permalink.