Wednesday, November 24, 2010

Sudoku Validation

In one of the interviews I gave recently, there was a question about sudoku validation (9x9). The logic to check itself is quiet simple -
  1. Check for existing value in row
  2. Check for existing value in column
  3. Check for existing value in block

Solution
Two dimensional array is a good data structure to use for it. My first solution involved using three loops but on refinement I was able to use only one loop for the validation. I find the start of block location first. In the loop checking row and column is quite straight forward. It is checking for value in a block that is a bit tricky and I had to play with LinqPad and Excel before I came up with correct statements.

public static bool Validate(int number, int row, int col)
{
    Console.WriteLine("Writing at pos {0},{1} - value {2}", row - 1, col - 1, number);

    var startBlockX = ((row - 1) / 3) * 3;
    var startBlockY = ((col - 1) / 3) * 3;

    for (int i = 0; i < 9; i++)
    {
        if (arr[i, col - 1] == number)
        {
            Console.WriteLine("found in col value {0}", arr[i, col - 1]);
            return false;
        }

        if (arr[row - 1, i] == number)
        {
            Console.WriteLine("found in row value {0}", arr[row - 1, i]);
            return false;
        }

        var mx = (i / 3) + startBlockX;
        var my = startBlockY + (i % 3);
        Console.WriteLine("block pos {0},{1}", mx, my);

        if (arr[mx, my] == number)
        {
            Console.WriteLine("found in block");
            return false;
        }
    }

    return true;
}

Checking
Using the following array and checking for highlighted spots in figure above for value of 9.

var arr = new int[9, 9];

arr[3, 6] = 9;
arr[3, 8] = 7;
arr[0, 8] = 9;
arr[1, 2] = 2;
arr[7, 7] = 9;
Validate(9, 3, 3);
Checking for pos 2,2 - value 9
found in block

Validate(9, 1, 5);
Checking for pos 0,4 - value 9
found in row

Validate(9, 3, 9);
Checking for pos 2,8 - value 9
found in col

No comments: