MH-SudokuSolver ver 2 Implementation Issues
Here’s a block of code from the Ruby program:
AllDigits = [1, 2, 3, 4, 5, 6, 7, 8, 9].freeze
def each_unknown
0.upto 8 do |row|
0.upto 8 do |col|
index = row*9+col
next if @grid[index] != 0
box = BoxOfIndex[index]
yield row, col, box
end
end
end
def possible(row, col, box)
AllDigits – (rowdigits(row) + coldigits(col) + boxdigits(box))
end
puzzle.each_unknown do |row, col, box|
p = puzzle.possible(row, col, box)
case p.size
when 0
raise Impossible
when 1
puzzle[row, col] = p[0]
unchanged = false
else
if unchanged && p.size < min
min = p.size
rmin, cmin, pmin = row, col, p
end
end
end
The C# code for this block is:
public IEnumerable<cell> each_unknown()
{
cell lCell;
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
int index = row * 9 + col;
if (grid[index] != 0)
continue;
int box = BoxOfIndex[index];
lCell.row = row;
lCell.col = col;
lCell.box = box;
yield return lCell;
}
}
}
int[] AllDigits = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
public int[] possible(int row, int col, int box)
{
int[] arr1 = rowdigits(row);
int[] arr2 = coldigits(col);
int[] arr3 = boxdigits(box);
int[] tArray = concatIntArrays(arr1, arr2);
tArray = concatIntArrays(tArray, arr3);
tArray = arraySetDiff(AllDigits, tArray);
return tArray;
}
private static int[] concatIntArrays(int[] arr1, int[] arr2)
{
List<int> concatedIntArray = new List<int>(arr1);
foreach (int number in arr2)
{
concatedIntArray.Add(number);
}
return concatedIntArray.ToArray();
}
private int[] arraySetDiff(int[] arr1, int[] arr2)
{
List<int> setDiff = new List<int>(arr1);
foreach (int i in arr2)
{
if (setDiff.Contains(i))
// setDiff.RemoveAll(num => num % i == 0);
setDiff.RemoveAll(num => num == i);
}
return setDiff.ToArray();
}
foreach (cell iter_cell in aPuzzle.each_unknown())
{
int row = iter_cell.row;
int col = iter_cell.col;
int box = iter_cell.box;
int[] p = aPuzzle.possible(row, col, box);
int size = p.Length;
switch (size)
{
case 0:
throw new Impossible();
case 1:
int indexVal = row*9 + col;
aPuzzle[indexVal] = p[0];
unchanged = false;
break;
default:
if (unchanged && (size < min))
{
min = size;
scanCell.row = row;
scanCell.col = col;
scanCell.p = new int[size];
Array.Copy(p, scanCell.p, size);
}
break;
}
}
----------------------------------------------------------
Let’s look at parts of the code block in the Ruby and C# versions to detail the differences. First,
the line
puzzle.each_unknown do |row, col, box|
calls the function each_unknown which is an iterator function that “yields” three values (the row number, column number, and box number) to this calling line. This is done by the line
yield row, col, box
In Ruby, “the yield statement temporarily returns control from the iterator method to the method that invoked the iterator. Specifically, control flow goes from the iterator to the block of code associated with the invocation of the iterator. When the end of the block is reached, the iterator method regains control and execution resumes at the first statement following the yield. In order to implement some kind of looping construct, an iterator method will typically invoke the yield statement multiple times.” [DFYM]
The concept of yield is pretty much the same in C# also: “The yield keyword signals to the compiler that the method in which it appears is an iterator block.”
Where the differences start is: “In the iterator block, the yield keyword is used together with the return keyword to provide a value to the enumerator object. This is the value that is returned, for example, in each loop of a foreach statement.” [MSDN C# Language Reference: http://msdn.microsoft.com/en-us/library/9k7k7cf0.aspx]
So in my C# code, yield is followed by return. In C#, we cannot yield multiple values. Hence we yield a struct and that too as an enumerable object. Hence,
puzzle.each_unknown do |row, col, box|
becomes
foreach (cell iter_cell in aPuzzle.each_unknown())
yield row, col, box
becomes
yield return lCell;
where lCell is of the type struct cell:
public struct cell
{
public int row;
public int col;
public int box;
}
----------------------------------------------------------
Now let’s look at the next line in the Ruby function
0.upto 8 do |row|
C# does not have the keyword upto. So this line is implemented as
for (int row = 0; row < 9; row++)
----------------------------------------------------------
The second line after the call to each_unknown calls the function possible by passing the arguments row, col, box. No big differences here. What is interesting is what happens inside the function possible. In Ruby, it is
AllDigits – (rowdigits(row) + coldigits(col) + boxdigits(box))
Now AllDigits is an array of integers. Similarly the return types of the functions rowdigits, coldigits and boxdigits are all arrays. This line of code is actually using the + operator and – operator on arrays. In Ruby, the usage of the + operator on two arrays is straightforward. It concatenates the two arrays. However the – operator performs set difference on arrays: “The – operator subtracts one array from another. It begins by making a copy of its left hand array, and then removes any elements from the copy if they appear anywhere in the right hand array.
[‘a’, ‘b’, ‘c’, ‘b’, ‘a’] – [‘b’, ‘c’, ‘d’]
results in [‘a’, ‘a’] “ [DFYM]
In C#, we cannot perform concatenation and set difference on arrays (in this case, an array of integers) using the + and – operators. Hence I wrote two methods to perform these operations. They are concatIntArrays and arraySetDiff. Their implementation details are:
private static int[] concatIntArrays(int[] arr1, int[] arr2)
{
List<int> concatedIntArray = new List<int>(arr1);
foreach (int number in arr2)
{
concatedIntArray.Add(number);
}
return concatedIntArray.ToArray();
}
private int[] arraySetDiff(int[] arr1, int[] arr2)
{
List<int> setDiff = new List<int>(arr1);
foreach (int i in arr2)
{
if (setDiff.Contains(i))
// setDiff.RemoveAll(num => num % i == 0);
setDiff.RemoveAll(num => num == i);
}
return setDiff.ToArray();
}
concatIntArrays uses a List of integers to hold the first array, calls the List method Add to add members of the second array and returns an array by calling the List method ToArray.
arraySetDiff, the equivalent of the Ruby – (minus) operator, starts with a List created from the first array. Then it loops through the second array, and for each number in the second array, if the List has that number, it removes all occurences of the number from the List by calling the RemoveAll method. The line is
setDiff.RemoveAll(num => num == i);
----------------------------------------------------------
Now the line in possible
AllDigits – (rowdigits(row) + coldigits(col) + boxdigits(box))
is implemented as follows in C#
int[] arr1 = rowdigits(row);
int[] arr2 = coldigits(col);
int[] arr3 = boxdigits(box);
int[] tArray = concatIntArrays(arr1, arr2);
tArray = concatIntArrays(tArray, arr3);
tArray = arraySetDiff(AllDigits, tArray);
return tArray;
----------------------------------------------------------
Continuing with the code after each_unknown, and the call to possible, we have the following Ruby code:
case p.size
when 0
raise Impossible
when 1
puzzle[row, col] = p[0]
unchanged = false
else
if unchanged && p.size < min
min = p.size
rmin, cmin, pmin = row, col, p
end
end
This is the classic switch-case statement of traditional high-level languages. This block is implemented in C# as:
switch (size)
{
case 0:
throw new Impossible();
case 1:
int indexVal = row*9 + col;
aPuzzle[indexVal] = p[0];
unchanged = false;
break;
default:
if (unchanged && (size < min))
{
min = size;
scanCell.row = row;
scanCell.col = col;
scanCell.p = new int[size];
Array.Copy(p, scanCell.p, size);
}
break;
}
----------------------------------------------------------
In the previous Ruby code there is a line
puzzle[row, col] = p[0]
puzzle is an object of the class Puzzle. The implementation of the array access operator is as follows:
def []= (row, col, newvalue)
@grid[row*9 + col] = newvalue
end
In C#, we take recourse to the indexer. However, since it can take only one value, we first caluculate the index value of the grid and the pass the index value to the indexer.
int indexVal = row*9 + col;
aPuzzle[indexVal] = p[0];
and inside the Puzzle class,
public int this[int i]
{
get
{
return grid[i];
}
set
{
int oldValue = grid[i];
grid[i] = value;
if (has_duplicates())
{
grid[i] = oldValue;
}
}
}
----------------------------------------------------------
In the previous block we see a call to has_duplicates. In the Ruby code, there is a function has_duplicates? that is called from another place. The implementation is:
def has_duplicates?
# uniq! Returns nil if all the elements in an array are unique.
# So if uniq! Returns something then the board has duplicates
0.upto(8) {|row| return true if rowdigits(row).uniq! }
0.upto(8) {|col| return true if coldigits(col).uniq! }
0.upto(8) {|box| return true if boxdigits(box).uniq! }
false
end
The C# implementation is:
public bool has_duplicates()
{
int i;
for (i = 0; i < 9; i++)
{
if (uniq(rowdigits(i)))
return true;
}
for (i = 0; i < 9; i++)
{
if (uniq(coldigits(i)))
return true;
}
for (i = 0; i < 9; i++)
{
if (uniq(boxdigits(i)))
return true;
}
return false; // If all the tests have passed, then the board has no duplicates
}
The first thing to notice here is that in Ruby code, there is no need for an explicit return keyword on the last line of the function. The return value of the last line is the implicit return value of the function, which in this case is false. In C#, we have return false as the last statement.
The second difference is the uniq! built-in method of array. The function rowdigits returns an array of which uniq! is called. In C#, we have to write such a function:
private bool uniq(int[] arr)
{
int size = arr.Length;
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
if (j == i)
continue;
else if (arr[j] == arr[i])
return true;
}
}
return false;
}
----------------------------------------------------------
Let’s look at another block (not contiguous though). In the following lines of Ruby
rmin, cmin, pmin = nil
return rmin, cmin, pmin
rmin and cmin are integers initialized to nil. pmin is an integer array which is also intialized to nil. All three are returned in one line at the end of the function. In C#, we cannot return multiple values from a method. One alternative we have is have the three values in a struct and return the struct. Plus in C#, we cannot initialize an integer to nil. I selected 999 as the initial value because in the sudoku input, the values are all integers between 0 and 9 and hence 999 is a safe value that will never be assigned to the variables.
The previous two lines are implemented in C# as
struct minCell
{
public int row;
public int col;
public int[] p;
public minCell(int aRow, int aCol, int[] aArray)
{
row = aRow;
col = aCol;
p = aArray;
}
}
minCell scanCell = new minCell(999, 999, null);
return scanCell;
----------------------------------------------------------
Similarly, in the following Ruby code, the return values (three) of the function scan are assigned to three variables (objects). If r (an integer) is nil, the puzzle object is returned:
r,c,p = scan(puzzle)
return puzzle if r == nil
The C# implementation of these two lines is
minCell lMinCell = scan(ref lPuzzle);
if (lMinCell.row == 999)
{
return lPuzzle;
}
----------------------------------------------------------
There are other differences. One example is the keyword until, which is not available in C#, for which we have to use while !
References:
[DFYM] The Ruby Programming Language by David Flanagan & Yukhiro Matsumoto, O’Reilly Media Inc. First Indian Reprint: March 2008, Published by Shroff Publishers and Distributors Pvt. Ltd. Mumbai.
[JM] Murach’s C# 2008. Mike Murach & Associates, Inc. First Indian Reprint: May 2008, Published by Shroff Publishers and Distributors Pvt. Ltd. Mumbai.