Search

Categories

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Send mail to the author(s) E-mail

# Sunday, April 10, 2011
Sudoku
( c# language | Coding Challenge )
keithDave

About a week ago Keith and I went on a ‘tramp’.. thats trekking.  We discussed Sudoku (apologies to Helen, Phil, Nora and others for starting the challenge without you..there was lots of time while walking to discuss strategy).

TDD

A single test project is VS2010.  Everything in one file (!) and static methods to make starting easier.

Coding strategy was to firstly:

    • find a way to check the sudoku was solved
      • Do all horizontal lines have only 1 to 9 used once
      • Do all vertical columns have 1 to 9 used once
      • Do all 3*3 squares have 1 to 9 used once

So I wanted a method to check if Array has only 1 instance of each number.

[TestClass]
public class UnitTest1
{
    // Arrays are [row, col]
    //  0,0     0,1     0,2
    //  1,0     1,1     1,2

    // SECTION 1 - tests are all about testing if the sudoku is solved
    // Single Array
    [TestMethod]
    public void SingleArrayCheckerFailsWhenArrayTooShort()
    {
        int[] numbers = { 1, 2, 3, 4, 5, 6, 7, 8 };
        bool result = DoesArrayHaveOnlyOneInstanceOfEachNumber(numbers);
        Assert.AreEqual(false, result);
    }

and the Method:

public static bool DoesArrayHaveOnlyOneInstanceOfEachNumber(int[] arrayOfNumbers)
{
    if (arrayOfNumbers.Length != 9)
        return false;

    if (arrayOfNumbers.Contains(0))
        throw new Exception("checking of a line array contains a 0");

    int[] howManyInstancesOfEachNumber = new int[9] { 0, 0, 0, 0, 0, 0, 0, 0, 0 };

    for (int i = 0; i < 9; i++)
    {
        int valueOfCurrentNumber = arrayOfNumbers[i];
        howManyInstancesOfEachNumber[valueOfCurrentNumber - 1] += 1;
    }

    foreach (var result in howManyInstancesOfEachNumber)
    {
        if (result != 1)
            return false;
    }

    return true;
}

An array is Enumerable.

then write the tests

[TestMethod]
        public void AllHorizonalLinesPass()
        {
            int[,] sudokuArray = new int[9, 9]{ {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9},
                                                {1,2,3,4,5,6,7,8,9}
                                            };

            bool result = DoAllHorizontalRowsPass(sudokuArray);
            Assert.AreEqual(true, result);
        }

        [TestMethod]
        public void AllVerticalColsPass()
        {
            int[,] sudokuArray = new int[9, 9]{  {1,1,1,1,1,1,1,1,1},
                                                {2,2,2,2,2,2,2,2,2},
                                                {3,3,3,3,3,3,3,3,3},
                                                {4,4,4,4,4,4,4,4,4},
                                                {5,5,5,5,5,5,5,5,5},
                                                {6,6,6,6,6,6,6,6,6},
                                                {7,7,7,7,7,7,7,7,7},
                                                {8,8,8,8,8,8,8,8,8},
                                                {9,9,9,9,9,9,9,9,9}
                                            };

            bool result = DoAllVerticalColsPass(sudokuArray);
            Assert.AreEqual(true, result);
        }

        [TestMethod]
        public void AllSquaresPass()
        {
            int[,] sudokuArray = new int[9, 9]{ {1,2,3,1,2,3,1,2,3},
                                                {4,5,6,4,5,6,4,5,6},
                                                {7,8,9,7,8,9,7,8,9},
                                                {7,8,9,7,8,9,7,8,9},
                                                {4,5,6,4,5,6,4,5,6},
                                                {1,2,3,1,2,3,1,2,3},
                                                {4,5,6,4,5,6,4,5,6},
                                                {1,2,3,1,2,3,1,2,3},
                                                {7,8,9,7,8,9,7,8,9},
                                            };

            bool result = DoAllSquaresPass(sudokuArray);
            Assert.AreEqual(true, result);
        }

then make them pass:

public static bool DoAllHorizontalRowsPass(int[,] sudoku)
{
   for (int row = 0; row < 9; row++) // go over each horizontal line
   {
       int[] horizonalLineArray = new int[9];
       for (int col = 0; col < 9; col++) // get each number in that line and put into a new horizontalLineArray
           horizonalLineArray[col] = sudoku[row, col];

       if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(horizonalLineArray))
           return false;
   }
   return true;
}

public static bool DoAllVerticalColsPass(int[,] sudoku)
{
   for (int col = 0; col < 9; col++) // go over each vertical line
   {
       int[] verticalLineArray = new int[9];

       for (int row = 0; row < 9; row++) // get each number in that vertical line and put into a new verticalLineArray
           verticalLineArray[row] = sudoku[row, col];

       if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(verticalLineArray))
           return false;
   }
   return true;
}

public static bool DoAllSquaresPass(int[,] sudoku)
{
   int rowStart = 0;
   int rowEnd = 2;
   int colStart = 0;
   int colEnd = 2;

   int squareCounter = 1;
   while (squareCounter < 9) // take each 3*3 square and test it
   {
       int[] allNumbersInSquareArray = new int[9];
       // go over first 3*3 square
       int counter = 0;
       for (int row = rowStart; row <= rowEnd; row++)
       {
           for (int col = colStart; col <= colEnd; col++)
           {
               allNumbersInSquareArray[counter] = sudoku[row, col];
               counter++;
           }
       }

       if (!DoesArrayHaveOnlyOneInstanceOfEachNumber(allNumbersInSquareArray))
           return false;

       // increment to the next 3*3 square going along horizontally first
       if (colEnd != 8)
       {
           colStart += 3;
           colEnd += 3;
       }
       else // go down to next 'row' of squares
       {
           colStart = 0;
           colEnd = 2;
           rowStart += 3;
           rowEnd += 3;
       }

       squareCounter++;
   }
   return true;
}

Making a Solver

Strategy was to (For all the elements with 0 in them):

  • Get rid of numbers
    • LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck
    • LookAtOtherNumbersInColumnAndTakeOutOnesWeDontNeedToCheck
    • LookAtOtherNumbersInSquareAndTakeOutOnesWeDontNeed
    • Then select a random number from the ones left
    • check if sudoku is solved

I used TDD on each Method eg

[TestMethod]
public void LookAtOtherNumbersInRowAndTakeThoseOffTheListOfNumbersToTry()
{
    int row = 2;
    List<int> listOfNumbersToTry = new List<int>();
    for (int i = 1; i < 10; i++)
        listOfNumbersToTry.Add(i);

    int[,] trySudokuArray = new int[9, 9]{ {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,0,4,5,6,0,8,0}, // this one
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9},
                                            {1,2,3,4,5,6,7,8,9}
                                    };
    LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, row, listOfNumbersToTry);

    Assert.AreEqual(3, listOfNumbersToTry.Count);
    Assert.IsTrue(listOfNumbersToTry.Contains(3));
    Assert.IsTrue(listOfNumbersToTry.Contains(7));
    Assert.IsTrue(listOfNumbersToTry.Contains(9));
}

//level 1
public static int[,] solve(int[,] inputSudokuArray) {
    
    // fill in numbers which are correct
    //int[,] sudokuArrayAfterB = new int[9, 9];
    //sudokuArrayAfterB = solveB(inputSudokuArray);

    // semi random code
    Random random = new Random();
    bool isSolved = false;
    int numberOfIterations = 0;

    while (!isSolved)
    {
        int[,] trySudokuArray = (int[,])sudokuArrayAfterB.Clone();
        for (int row = 0; row < 9; row++)
        {
            for (int col = 0; col < 9; col++)
            {
                if (trySudokuArray[row,col] == 0) // if it is blank
                {
                    // setup numbers to try, then strategy is to take out of this list
                    List<int> listOfNumbersToTry = new List<int>();
                    for (int i = 1; i < 10; i++)
                        listOfNumbersToTry.Add(i);

                    LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, row, listOfNumbersToTry);

                    LookAtOtherNumbersInColumnAndTakeOutOnesWeDontNeedToCheck(trySudokuArray, col, listOfNumbersToTry);

                    LookAtOtherNumbersInSquareAndTakeOutOnesWeDontNeed(trySudokuArray, row, col, listOfNumbersToTry);
                    
                    // are there any possible numbers?
                    if (listOfNumbersToTry.Count > 0)
                    {
                        // pick a random number from listOfNumbersToTry
                        int indexOfListNumberToGet = random.Next(0, listOfNumbersToTry.Count());
                        trySudokuArray[row,col] = listOfNumbersToTry[indexOfListNumberToGet];
                    }
                    else
                        goto Foo;
                }
            }
        }
        isSolved = checkSudoku(trySudokuArray);

        if (isSolved)
        {
            for (int row = 0; row < 9; row++)
            {
                for (int col = 0; col < 9; col++)
                    Debug.Write(trySudokuArray[row, col] + " ");
                Debug.WriteLine("");
            }
            return trySudokuArray;
        }
    Foo:
        if (numberOfIterations % 1000 == 0)
            Debug.WriteLine("iterations: " + String.Format("{0:0,0}",numberOfIterations));
            //Console.WriteLine("iterations: " + String.Format("{0:0,0}", numberOfIterations));
        numberOfIterations++;
    }
    return null;
}

 

StrategyB – Make numbers definite if we know they are

  • For each 0 square see if there is only 1 possible number
    • ie look at LookAtOtherNumbersInRowAndTakeOutOnesWeDontNeedToCheck etc
    • put that number in the square
    • keep looping the whole board until nothing is changed
Comments [0] | | # 
Related posts:
TekPub C#4 Jon Skeet
IEnumerable Yield Deferred / Lazy
C# Names
Code Reviews, TDD, Kata
Asserting something is in a Collection
Asserting order of a Collection
All comments require the approval of the site owner before being displayed.
Name
E-mail
Home page

Comment (Some html is allowed: a@href@title, strike) where the @ means "attribute." For example, you can use <a href="" title=""> or <blockquote cite="Scott">.  

Enter the code shown (prevents robots):
Live Comment Preview