Visual C# 2005 (Windows) Guide
Sudoku: Basic Solving

Now that we have done the preliminary work on the application, we are ready to add some real value to the work. The aim of the application is to be able to solve the next step in a puzzle. It should solve only one step at a time, picking out the easiest items first.

Setting Up For Solving

We need to make a few changes to the application in order to be ready to build our solving methods. We need to do is make space on the form for a log of computer moves. Stretch the form so that there is space to the right of the grid. Add a multiline text box in this space. Call the text box, txtLog. Everytime the computer makes a change to the puzzle, we will record it here.

Solving: Single Candidates

Look carefully at the image of a grid that you saw on the first page of the Sudoku section.

sudoku grid

Cell 6,9 can only be the value 6. This is the only valid value for this cell. We need to think how we can detect this situation in our code.

You may remember that the GridSquare class has a method called NumCandidates(). We can examine each cell in the grid in turn. If the cell has only one candidate, that must be the value we need to place in that cell.

The FindSingleCandidate() method reads as follows,

public string FindSingleCandidates()
{
   string returnMessage = "0";
   for (int i = 1; i <= 9; i++)
   {
      for (int j = 1; j <= 9; j++)
      {
         if (GridCell[i, j].Value == 0 && GridCell[i, j].NumCandidates() == 1)
         {
            int numToEnter = int.Parse(GridCell[i, j].DisplayCandidates());
            returnMessage = i + "," + j + " can only be " + numToEnter;
            EnterItem(i, j, numToEnter);
            return returnMessage;
         }
      }
   }
   return returnMessage;
}

The procedure loops through each cell starting in the top left corner and reading a column at a time checking for a cell that has only one candidate. When that is found, the number is entered into the grid.

The SolveNextStep() method will ultimately try out each of the solving functions we develop until a move is found or cannot be found.

public string SolveNextStep()
{
   string result = "";
   result = FindSingleCandidates();
   if (result != "0")
   {
      return result;
   }
   return result;
}

Our form will always call the SolveNextStep() method. It will return "0" if no solution is found or an explanation of the changes made to the grid.

Add a new menu item to the right of the File menu that you created on the form. This item should be &Solve. The first item in the menu should be Solve Next Step. Make the shortcut for this the F8 key and double click on the menuitem to load the click event handler. Add the code,

private void solveNextStepToolStripMenuItem_Click(object sender, EventArgs e)
{
   string s = grid.SolveNextStep();
   if (s == "0")
   {
      txtLog.Text += "Could not solve the next step." + Environment.NewLine;
   }
   else
   {
      txtLog.Text += s + Environment.NewLine;
      UpdateDisplay();
   }
}

Test out this method on the puzzle file you were given. It should find that lonely 6.

Solving: Single Instances Of A Candidate In A Row

Now that you have your first solving method, you might be a little disappointed that it only found one step to solve. The next step is to look for numbers that appear only once as a candidate in a row. Look at the second row of the puzzle. 7 only appears once in row 2.

One thing we will need to do easily is to see how many times an item appears as a candidate in a row. The following method can be addded to the SudokuGrid class to do that for us,

public int NumberInRow(int row, int itemToCheck)
{
   int numInstances = 0;
   for (int i = 1; i <= 9; i++)
   {
      if (GridCell[row, i].Value == 0 && GridCell[row, i][itemToCheck] == 0)
      {
         numInstances += 1;
      }
   }
   return numInstances;
}

The solving method will use the NumberInRow helper method to make our code easier for us to read.

public string FindSingleInstanceInRow()
{
   string returnMessage = "0";
   for (int itemToCheck = 1; itemToCheck <= 9; itemToCheck++)
   {
      for (int rows = 1; rows <= 9; rows++)
      {
         if (NumberInRow(rows, itemToCheck) == 1)
         {
            //found value and row - now locate column
            int cols = 1;
            while (cols <= 9)
            {
               if (GridCell[rows, cols].Value == 0 && GridCell[rows, cols][itemToCheck] == 0)
               {
                  returnMessage = rows + "," + cols + " only instance of " + itemToCheck + " in row";
                  EnterItem(rows, cols, itemToCheck);
                  return returnMessage;
               }
               cols++;
            }
         }
      }
   }
   return returnMessage;
}

In order to implement this method, all we need to do is make a small amendment to the SolveNextStep() method. We do this by adding the following code after the if statement and before the final return statement.

result = FindSingleInstanceInRow();
if (result != "0")
{
return result;
}

Solving: Single Instances Of A Candidate In A Column

This method is understandably similar to the previous. Instead of checking the number of instances of a number in a row, we do that in a column. There are lots of row and column based strategies for solving sudoku - programming one correctly will usually provide the route to the solution for the other.

Like before, we start with a method to count the number of instances in a particular column,

public int NumberInCol(int col, int itemToCheck)
{
   int numInstances = 0;
   for (int i = 1; i <= 9; i++)
   {
      if (GridCell[i, col].Value == 0 && GridCell[i, col][itemToCheck] == 0)
      {
         numInstances += 1;
      }
   }
   return numInstances;
}

Then we make the method for finding the single instance.

public string FindSingleInstanceInColumn()
{
   string returnMessage = "0";
   for (int itemToCheck = 1; itemToCheck <= 9; itemToCheck++)
   {
      for (int cols = 1; cols <= 9; cols++)
      {
         if (NumberInCol(cols, itemToCheck) == 1)
         {
            //found value and col - now locate row
            int rows = 1;
            while (rows <= 9)
            {
               if (GridCell[rows, cols].Value == 0 && GridCell[rows, cols][itemToCheck] == 0)
               {
                  returnMessage = rows + "," + cols + " only instance of " + itemToCheck + " in column";
                  EnterItem(rows, cols, itemToCheck);
                  return returnMessage;
               }
               rows++;
            }
         }
      }
   }
   return returnMessage;
}

Now you need to add some lines of code to the SolveNextStep() method so that the solving function is called.

Solving: Single Instances Of A Candidate In A Minisquare

Examining minisquares involves slightly more kerfuffle than looking at a row or column. We still use a pair of functions to do this, the first of which counts the instances in the minisquare.

public int NumberInSquare(int square, int itemToCheck)
{
   int numInstances = 0;
   for (int i = GridRefs[square, 0]; i <= GridRefs[square, 0] + 2; i++)
   {
      for (int j = GridRefs[square, 1]; j <= GridRefs[square, 1] + 2; j++)
      {
         if (GridCell[i, j].Value == 0 && GridCell[i, j][itemToCheck] == 0)
         {
            numInstances += 1;
         }
      }
   }
   return numInstances;
}

The solving function is as follows,

public string FindSingleInstanceInSquare()
{
   string returnMessage = "0";
   for (int itemToCheck = 1; itemToCheck <= 9; itemToCheck++)
   {
      for (int miniSquare = 0; miniSquare <= 8; miniSquare++)
      {
         if (NumberInSquare(miniSquare, itemToCheck) == 1)
         {
            //found value and square - locate cell
            for (int i = GridRefs[miniSquare, 0]; i <= GridRefs[miniSquare, 0] + 2; i++)
            {
               for (int j = GridRefs[miniSquare, 1]; j <= GridRefs[miniSquare, 1] + 2; j++)
               {
                  if (GridCell[i, j][itemToCheck] == 0)
                  {
                     returnMessage = i + "," + j + " only instance of " + itemToCheck + " in minisquare";
                     EnterItem(i, j, itemToCheck);
                     return returnMessage;
                  }
               }
            }
         }
      }
   }
   return returnMessage;
}

Now you need to add some lines of code to the SolveNextStep() method so that the solving function is called.

Testing The Program

You need to test that all 4 of the solving functions detailed on this page work as they should. It can be quite tricky finding a puzzle that allows that. One thing you can do is comment out all but one of the solving methods in the SolveNextStep() method and test them one-at-a-time. You must make sure that these work before attempting to add any more features.