I’ve been doing some interviewing for open positions at Microsoft… and one of the portions of any MS interview is usually a coding question to gauge the level of algorithm maturity of the candidate… not necessarily the mastery of syntax or knowledge of the CLR, but simply how you think through solving a problem.
One of my code questions was: “Say you are part of a project for writing a Sudoku game, and your part is to verify if the user has correctly solved the puzzle. Given an array representing the 9×9 grid for the Sudoku possible answer; Write a function that returns a bool to determine if an answer is correct. ” This has resulted in several interesting paths of thought on the part of the candidates, but also sparked some interesting discussions in house as well.
If you don’t know about Sudoku, it is a simple game, consisting of a 9×9 grid where the object is to get numbers 1 through 9 into each square, with no duplicates in a column, or a row, or a 3×3 box.
(picture is from Wikipedia entry)
The problem is interesting because it is simple in verifying columns and rows, but holds a hidden problem when trying to do the same for the ‘boxes’.
In particular, Kevin Johnson and I were coming up with possible multi-threaded approaches to solving the problem. We even expanded this issue to include solving the puzzle rather than just verifying. This is because I’d completed this (to an extent) in Perl some years back. But first… let’s discuss the puzzle verification function.
The most common answers to the verification steps involve two nested for loops to iterate through the cells. On each cell you’d store or check off that number from a global (to the loops) sets of objects, either numbers or Boolean to keep a check list of what you’ve encountered already in that column/row/box. Sometimes people don’t really think about the boxes till they’ve completed the column/row check, and that’s where things get a bit hairy…
One Common Interview Answer:
bool isSudokuSolved(Int[,] solution) { HashSet<Int>[] rows = new HashSet<Int>[9]; // ignoring initializing rows hash... // ignoring test code (verify array size, numbers are 1-9 etc...) for (int x = 0; x < 9; x++) { // initialize cols hash HashSet<Int> cols = new HashSet<Int>(); for (int y = 0; y < 9; y++) { //initialize row hash if (x==0){ rows[y] = new HashSet<Int>(); } //Check rows and cols by add new (which returns bool for !existance) if ( (!cols.Add(solution[x, y])) || (!rows[y].Add(solution[x, y])) ) { return false; //dupe } //check for box duplicates if (x % 3 == 0 && y % 3 == 0) { //It's the top left corner of a box if (!CheckBox(solution, x, y)) { return false; } } } } return true; } bool CheckBox(short[,] solution, int X, int Y) { HashSet<Int> box = new HashSet<Int>(); for (int x = X; x < X+3; x++) { for (int y = Y; y < Y+3; y++) { if (!box.Add(solution[x, y])) { return false; //dupe } } } return true; }
In addition to this, there were concepts of keeping a bit array that will be prepopulated to keep track of all the answers that have already been found, returning false on any that are already set to true. This though is very similar to the above example, though it uses more data (potentially on an early exit example), but may (debatable) use less process time since it is not using a hashset.
Next I’ll try to add on to this as to thoughts of what the “Solver” should look like, possible answers being pursued… etc. If you have your own answer for the above… feel free to post it in the comments.
From the Brain of Herrick 
Oy, too much allocations going on inside of loops.
using System;
namespace SudokoVerify
{
class Program
{
static void Main(string[] args)
{
string[] data = new string[9];
data[0] = “534678912”;
data[1] = “672195348”;
data[2] = “198342567”;
data[3] = “859761423”;
data[4] = “426853791”;
data[5] = “713924856”;
data[6] = “961537284”;
data[7] = “287419635”;
data[8] = “345286179”;
bool fail = false;
for (int i = 0; i < 9 && !fail; i++) // every row (or column)
{
bool[,] slot = new bool[2,9];
for (int j = 0; j < 9 && !fail; j++) // every col in a row (or row in a column)
{
int row_val = data[i][j] – '0' – 1; // char digit – char '0' = value, subtract 1 more for 0 based array
int col_val = data[j][i] – '0' – 1;
fail = slot[0, row_val] || slot[1, col_val];
slot[0, row_val] = slot[1, col_val] = true;
}
}
// check boxes: i = 3 rows / j = 3 columns
for (int i = 0; i < 3 && !fail; i++)
{
for (int j = 0; j < 3 && !fail; j++)
{
// each box is a 3×3 grid.
bool[] slot = new bool[9];
for (int ii = 0; ii < 3 && !fail; ii++)
{
for (int jj = 0; jj < 3 && !fail; jj++)
{
int val = data[i * 3 + ii][j * 3 + jj] – '0' – 1;
fail = slot[val];
slot[val] = true;
}
}
}
}
Console.WriteLine(fail.ToString());
}
}
}
hmmm, wordpress did not respect my identation…
couldn’t sleep…. make date into one long array C style, then calculate the array indices for row-based, column-based, and box-based checks, then do all at once.
static void Main(string[] args)
{
string data = “534678912672195348198342567859761423426853791713924856961537284287419635345286179”;
bool fail = false;
for (int i = 0; i < 9 && !fail; i++)
{
bool[,] slot = new bool[3, 9];
for (int j = 0; j < 9 && !fail; j++)
{
int row_val = data[i*9 + j] – '0' – 1; // value of element J in row I
int col_val = data[j*9 + i] – '0' – 1; // value of element J in column I
int box_val = data[((i / 3) * 27) + ((i % 3) * 3) + (j / 3) * 9 + j % 3] – '0' – 1; // value of element J in "sub-box" I
fail = slot[0, row_val] || slot[1, col_val] || slot[2, box_val];
slot[0, row_val] = slot[1, col_val] = slot[2, box_val] = true;
}
}
Console.WriteLine(fail.ToString());
}
nice examples Jerry! welcome to the stay up late and code club 🙂
does this respect the line breaks and indentation? FYI - you may need to use 4 spaces rather then using a tab.Yes, it did… use an HTML PRE tag to surround your code, and use spaces not tabs (VS should do that for you)
So I started to work on a solver. At first I looked at it from an AI perspective and figured simulated annealing would be a good approach. It comes from metallurgy. You start with a hot object, then you cool it slowly so that the crystals can move around freely. By cooling it slowly, you give the crystals more time to move around at higher energy. In doing this metal scientists discovered that when the metal finally cooled it was metal was stronger as it had less defects and larger crystals.
In computer science the same idea can be used and has been very successful at solving the 8 queens problem (which in many ways is similar to sudoku.)
To do simulated annealing in CS:
Start with a problem and program a way to calculate its “energy” or how close is it to solving the problem.
Select and program a method to randomly modify the existing solution.
The algorithm then goes through a series of rounds. In each round it changes the current solution using your random modification method. At the end of that change, the algorithm uses your energy method to calculate how close the new solution is to solving the problem (e.g. Did the energy go down?) The algorithm then uses this information to make a decision:
1) If the energy went down, the solution is closer to correct, so the algorithm accepts this as the current solution and uses it in the next round.
2) If the energy went up, in other words the solution is farther from solving the problem the algorithm can:
a) Reject the solution outright and continue to the next round with the previous rounds solution.
– or –
b) Randomly select to use the worse solution. The algorithm used for random selection is skewed so that a bad solution is selected more in the first rounds and will occur less and less each round until it never occurs.
Then the algorithm repeats the process for the next round.
The random selection seems strange counter intuitive at first, as we are selecting a worse solution. But the idea is to simulate annealing where crystals move around and generate many worse configurations along the path to better configurations at the end.
Applying this to Sudoku, I created a simple energy method. It calculated how far the board was from a solution by counting duplicate numbers in each row, column and square. When this count is high there are more numbers misplaced, when the count is zero the board is solved.
For a random modification, I swapped two non-stationary squares at random. The only catch was I had to start with a filled in board. To fill in the board, I added numbers making sure each row contained no duplicates.
— The Results
The results were a bit disappointing and very random. Using the same board for many runs I had variations in time from 5 seconds to 2 minutes. The 2 minute runs usually ended in no solution. Only 70% of the time, was a viable solution created. And that 70% was very random. I could run the program over and over with the same information and sometimes a solution was found other times it was not.
I could continue to work on this solution and probably tune it to work better. But in the process a better solution came to mind than random swapping. See my next post for that info.
— A better solver
In the process of doing the Simulated Annealing approach a better idea came to me. What about doing a simple breadth first search for the solution.
I start by filling stationary numbers into a current board.
loop while no solution was found
{
Find the square with no value and the most constraints (least number of potential values).
if (no empty squares exist a solution was found)
{
exit loop
}
else if (empty squares were found but they are so constrained no value works)
{
Throw away the solution, it is not viable.
}
else
{
For each potential value
{
Copy the current board
Fill the square on the board with a value,
Push the board onto a stack.
}
Pop the last one off the stack and save it as the current board
}
}
Because each iteration looks for the most constrained squares to fill in the search tree remains small.
— Results
Through testing many times with many different problems I always got a solution in less than 2 seconds. (WOO HOO!!!)
Interesting notes:
I added threading to the solution figuring I could synchronize the stack and the use of multiple threads would lend itself to a faster solution. Unfortunately that was not the case. When I threw the code inside the loop onto a worker thread the solution slowed down tremendously. This was not actually related to any overhead related to threading, but the fact that the threads added more solutions to the top of my stack and changed the algorithm from a depth first search to some random tree search.
— Code
The goal was to generate a solution finder that executed fast. Some places the code seems more complex as a result. An example would be using the lookup table for the square cells instead of calculating them. This is very rough code, but feel free to expand or use it as you see fit. Any ideas are always appreciated.
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections.Specialized;
namespace ConsoleApplication1
{
class Program
{
private static object lockObject = new object();
private static volatile SudokuBoard solution = null;
public static SudokuBoard Solution
{
get
{
lock (lockObject)
{
return solution;
}
}
set
{
lock (lockObject)
{
solution = value;
}
}
}
static void Main(string[] args)
{
SudokuBoard currentBoard = new SudokuBoard();
currentBoard[1, 3] = 9;
currentBoard[1, 6] = 4;
currentBoard[1, 7] = 5;
currentBoard[2, 5] = 1;
currentBoard[2, 6] = 6;
currentBoard[2, 7] = 7;
currentBoard[3, 1] = 7;
currentBoard[3, 2] = 1;
currentBoard[3, 8] = 6;
currentBoard[4, 1] = 2;
currentBoard[4, 4] = 9;
currentBoard[4, 8] = 7;
currentBoard[4, 9] = 3;
currentBoard[5, 2] = 9;
currentBoard[5, 5] = 3;
currentBoard[5, 8] = 2;
currentBoard[6, 1] = 5;
currentBoard[6, 2] = 7;
currentBoard[6, 6] = 2;
currentBoard[6, 9] = 8;
currentBoard[7, 2] = 8;
currentBoard[7, 8] = 5;
currentBoard[7, 9] = 4;
currentBoard[8, 3] = 7;
currentBoard[8, 4] = 1;
currentBoard[8, 5] = 9;
currentBoard[9, 3] = 5;
currentBoard[9, 4] = 8;
currentBoard[9, 7] = 2;
while (Program.Solution == null)
{
CalculateSolution(currentBoard);
// ThreadPool.QueueUserWorkItem(CalculateSolution, currentBoard);
currentBoard = PendingBoards.Next();
}
Console.Out.WriteLine(“Puzzle solved”);
Program.Solution.Print();
Console.ReadKey();
}
public static void CalculateSolution(Object state)
{
Tuple minPoint;
IEnumerable numbers;
int zeroCount = 0;
SudokuBoard currentBoard = (SudokuBoard)state;
bool found = currentBoard.FindCellWithLeastOptions(ref zeroCount, out minPoint, out numbers);
if (found == false)
{
if (zeroCount == 0)
{
// A solution was found.
Program.Solution = currentBoard;
}
}
else
{
foreach (int value in numbers)
{
SudokuBoard newboard = new SudokuBoard(currentBoard);
newboard[minPoint.Item1, minPoint.Item2] = value;
PendingBoards.Add(newboard);
}
}
}
}
class SudokuBoard
{
private const int Dimension = 9;
private const int BoxDimension = 3;
private static Tuple[,] boxes = {
{null, null, null, null, null, null, null, null, null, null },
{null, Tuple.Create(1,1), Tuple.Create(1,2), Tuple.Create(1,3), Tuple.Create(2,1), Tuple.Create(2,2), Tuple.Create(2,3), Tuple.Create(3,1), Tuple.Create(3,2), Tuple.Create(3,3) },
{null,Tuple.Create(1,4), Tuple.Create(1,5), Tuple.Create(1,6), Tuple.Create(2,4), Tuple.Create(2,5), Tuple.Create(2,6), Tuple.Create(3,4), Tuple.Create(3,5), Tuple.Create(3,6) },
{null,Tuple.Create(1,7), Tuple.Create(1,8), Tuple.Create(1,9), Tuple.Create(2,7), Tuple.Create(2,8), Tuple.Create(2,9), Tuple.Create(3,7), Tuple.Create(3,8), Tuple.Create(3,9) },
{null, Tuple.Create(4,1), Tuple.Create(4,2), Tuple.Create(4,3), Tuple.Create(5,1), Tuple.Create(5,2), Tuple.Create(5,3), Tuple.Create(6,1), Tuple.Create(6,2), Tuple.Create(6,3) },
{null, Tuple.Create(4,4), Tuple.Create(4,5), Tuple.Create(4,6), Tuple.Create(5,4), Tuple.Create(5,5), Tuple.Create(5,6), Tuple.Create(6,4), Tuple.Create(6,5), Tuple.Create(6,6) },
{null, Tuple.Create(4,7), Tuple.Create(4,8), Tuple.Create(4,9), Tuple.Create(5,7), Tuple.Create(5,8), Tuple.Create(5,9), Tuple.Create(6,7), Tuple.Create(6,8), Tuple.Create(6,9) },
{null, Tuple.Create(7,1), Tuple.Create(7,2), Tuple.Create(7,3), Tuple.Create(8,1), Tuple.Create(8,2), Tuple.Create(8,3), Tuple.Create(9,1), Tuple.Create(9,2), Tuple.Create(9,3) },
{null, Tuple.Create(7,4), Tuple.Create(7,5), Tuple.Create(7,6), Tuple.Create(8,4), Tuple.Create(8,5), Tuple.Create(8,6), Tuple.Create(9,4), Tuple.Create(9,5), Tuple.Create(9,6) },
{null, Tuple.Create(7,7), Tuple.Create(7,8), Tuple.Create(7,9), Tuple.Create(8,7), Tuple.Create(8,8), Tuple.Create(8,9), Tuple.Create(9,7), Tuple.Create(9,8), Tuple.Create(9,9) },
};
///
/// The gameboard being played.
///
private Cell[,] gameBoardInfo = new Cell[Dimension + 1, Dimension + 1];
public SudokuBoard()
{
for (int row = 1; row <= Dimension; row++)
{
for (int column = 1; column <= Dimension; column++)
{
gameBoardInfo[row, column] = new Cell(true);
}
}
}
public SudokuBoard(SudokuBoard board)
{
for (int row = 1; row <= Dimension; row++)
{
for (int column = 1; column <= Dimension; column++)
{
this.gameBoardInfo[row, column] = new Cell(board.gameBoardInfo[row, column]);
}
}
}
public int this[int row, int column]
{
get
{
if (row Dimension || column Dimension)
{
throw new IndexOutOfRangeException(String.Format(“indicies must be between 1 and {0}”, Dimension));
}
return gameBoardInfo[row, column].GetCellValue();
}
set
{
if (row Dimension || column Dimension)
{
throw new IndexOutOfRangeException(String.Format(“indicies must be between 1 and {0}”, Dimension));
}
int originalValue = gameBoardInfo[row, column].GetCellValue();
int boxIndex = this.CalculateBoxIndex(row, column);
Tuple boxCell;
for (int i = 1; i <= Dimension; i++)
{
boxCell = boxes[boxIndex, i];
if (originalValue != 0)
{
gameBoardInfo[row, i].SetNumberAsFree(originalValue);
gameBoardInfo[i, column].SetNumberAsFree(originalValue);
gameBoardInfo[boxCell.Item1, boxCell.Item2].SetNumberAsFree(originalValue);
}
gameBoardInfo[row, i].SetNumberAsUsed(value);
gameBoardInfo[i, column].SetNumberAsUsed(value);
gameBoardInfo[boxCell.Item1, boxCell.Item2].SetNumberAsUsed(value);
}
gameBoardInfo[row, column].SetCellValue(value);
}
}
private ushort CalculateBoxIndex(int row, int column)
{
// RowStart ((Value/3) * 3) + 1
// Col Start ((Value%3) -1 )*3 + 1
return (ushort)(((column – 1) / BoxDimension) + (((row – 1) / BoxDimension) * BoxDimension) + 1);
}
public bool FindCellWithLeastOptions(ref int zeroCount, out Tuple minPoint, out IEnumerable numbers)
{
int minRow = 0, minColumn = 0;
int leastCount = Dimension + 1;
bool retVal = false;
Cell currentCell;
Cell minCell = null;
// Walk board looking for cell with least points.
zeroCount = 0;
int currentCount;
for (int i = 1; i <= Dimension; i++)
{
for (int j = 1; j <= Dimension; j++)
{
currentCell = gameBoardInfo[i, j];
if (currentCell.GetCellValue() == 0)
zeroCount++;
currentCount = currentCell.CountOfAvailableNumbers();
if (currentCount 0)
{
minCell = currentCell;
leastCount = currentCount;
minRow = i;
minColumn = j;
}
}
}
// We found a minpoint
if (minCell != null)
{
List availableNumberList = new List(minCell.CountOfAvailableNumbers());
for (int i = 1; i <= 9; i++)
{
if (!minCell.NumberIsInUse(i))
availableNumberList.Add(i);
}
numbers = availableNumberList;
minPoint = Tuple.Create(minRow, minColumn);
retVal = true;
}
else
{
numbers = null;
minPoint = null;
}
// We found a minpoint.
return retVal;
}
public void Print()
{
for (ushort row = 1; row <= Dimension; row++)
{
for (ushort column = 1; column <= Dimension; column++)
{
Console.Write("{0} ", this[row, column]);
}
Console.WriteLine();
}
}
}
class Cell
{
///
/// Internal storage for data.
///
private BitVector32 data;
private sbyte numberAvailableCount;
private sbyte dataValue;
///
/// Establish masks for numbers 1 to 9.
///
private static readonly BitVector32.Section[] numbersAvailableMask;
static Cell()
{
// Establish masks for numbers 1 to 9.
numbersAvailableMask = new BitVector32.Section[10];
numbersAvailableMask[0] = BitVector32.CreateSection(1);
for (int i = 1; i <= 9; i++)
{
numbersAvailableMask[i] = BitVector32.CreateSection(1, numbersAvailableMask[i – 1]);
}
}
public Cell(bool initialize)
{
this.data = new BitVector32();
this.numberAvailableCount = 9;
this.dataValue = 0;
for (int i = 1; i <= 9; i++)
{
this.data[Cell.numbersAvailableMask[i]] = 1;
}
}
public Cell(Cell cell)
{
this.data = cell.data;
this.numberAvailableCount = cell.numberAvailableCount;
this.dataValue = cell.dataValue;
}
public bool NumberIsInUse(int i)
{
return (this.data[Cell.numbersAvailableMask[i]] == 0);
}
public void SetNumberAsUsed(int i)
{
if (this.data[Cell.numbersAvailableMask[i]] == 1)
{
this.data[Cell.numbersAvailableMask[i]] = 0;
this.numberAvailableCount–;
}
}
public void SetNumberAsFree(int i)
{
if (this.data[Cell.numbersAvailableMask[i]] == 0)
{
this.data[Cell.numbersAvailableMask[i]] = 1;
this.numberAvailableCount++;
}
}
public int CountOfAvailableNumbers()
{
int retVal;
if (this.dataValue == 0)
{
// If there is no data, then return the count mask.
retVal = this.numberAvailableCount;
}
else
{
// There's data, so return no available numbers.
retVal = 0;
}
return retVal;
}
public void SetCellValue(int value)
{
this.dataValue = (sbyte)value;
}
public int GetCellValue()
{
return this.dataValue;
}
}
class PendingBoards
{
private static object lockObject = new object();
private static Stack boardStack = new Stack();
public static void Add(SudokuBoard board)
{
lock (lockObject)
{
boardStack.Push(board);
}
}
public static SudokuBoard Next()
{
SudokuBoard returnBoard = null;
while (returnBoard == null)
{
lock (lockObject)
{
if (boardStack.Count != 0)
{
returnBoard = boardStack.Pop();
}
}
if (returnBoard == null)
{
System.Threading.Thread.Sleep(10);
}
}
return returnBoard;
}
}
}
I like Jerry’s answer. Though I did write a solver (http://vantasyworld.com/fun/sudoku/sudokusolver.html) and then realized it breaks when given a puzzle that is impossible to solve.
Some tough Sudoku interview questions may incorporate checking for puzzles that are not solvable, that’s more advance, but fun!