Latin Squares Generator(Console) Beta 2
Before my teacher's lecture I found enough time to work on my Latin Squares Generator application. As most of my visitors are .NET developers or professional programmers, for them and for myself (When I want to modify it) I changed most of codes with up to date methods in coding. New Beta 2 version is based on .NET 2.0 coding methods and uses .NET objects. I think that it's a good example of implementing data structures in Visual Basic and using System.Collections namespace in it.
Main changes are:
- Code is changed to be familiar for .NET developers and professionals.
- User can save the output file more easily in the similar folder or give another path as the past.
- XML comments are added to codes.
You can download Beta 2 Console version from here.
I try to send a short post and describe the process of coding it.
Update: I wrote short description about this application:
This is a short description about the process I've followed to design my Latin Squares Generator application (At this time it's in Beta 2 Console version) Latin Squares are described here. The goal of this application is to get some objects and generate all possible Latin Squares for them and save them in a text file as output.
Algorithm
First I start with the algorithm I've used to design this application. My algorithm is based on data structures and especially Tree data structure.
To find all possible Latin Squares I defined a tree. In this tree each node has a simple structure and saves a matrix of numbers, a link to its successor node in its current link list and a link to its first child (If it has them).
I start with an empty matrix and put it in root then try to generate the tree on it. At first glance I try to find all possible values for next empty entry in current node's matrix (That I called it Board in my application) then add all of these possible values to different nodes and add them to a link list. Finally I add this link list to their parent node and do this recursively for all nodes.
As I didn't want to traverse my tree and waste my memory found results and add them to output on time. How?! When generating each node checked that whether does it in last entry or not and if answer was true then added it to results.
Application
I won't focus on the process of generating output here because it's very simple but will explain my classes and structures here.
TreeNode class
This class defines the simple structure of my tree nodes. It has three fields:
- Board: An Array of Bytes which saves node's matrix.
- NextNode: Points to next TreeNode in current list.
- Son: Points to first child of current node if it exists.
This class has only one method (New). When creating a new instance of this class, it gets the order as parameter to resize Board.
#Region "Node Structure"
''' <summary>
''' This is a simple structure for our main Tree node
''' Each node has a queue of childs which are all possible matrixes for current entry
''' Board is a matrix to save all values
''' When creating an instance of this object using New keyword
''' give it the order of the Board
''' </summary>
''' <remarks></remarks>
Friend Class TreeNode
Sub New(ByVal intorder As Integer)
ReDim Board(intorder - 1, intorder - 1)
End Sub
Public Board(0, 0) As Byte 'Save Matrixes
Public Son As TreeNode = Nothing 'Point to Child
Public NextNode As TreeNode = Nothing 'Point to Next
End Class
#End Region
TempStruct Structure
I used this structure to save current row and column and possible value for child nodes to simplify my process. This structure is very simple and has three fields:
- intColumn: Saves the index of next column of node.
- intRow: Saves the index of next row of node.
- intValue: Saves the possible value of related row and columns.
#Region "Temp Structure"
''' <summary>
''' This is a temporary structure which saves the possible
''' value and its relative row and column for a node
''' </summary>
''' <remarks></remarks>
Friend Structure TempStruct
Public intValue As Integer
Public intRow As Integer
Public intColumn As Integer
End Structure
#End Region
Tree Class
Most of works is being done here. Tree class has two private fields:
- intOrder: By setting this property, the order of nodes is defined.
- ReturnList: This is an stack that saves all results.
Tree class has also a public property: Order. It's used to set the value of intOrder.
The methods of this class are:
- Calculate: This our public method which calls GenerateTree() method to generate the tree then reads results from ReturnList stack and adds them to an ArrayList and gives it back.
- CheckValues: Gets a matrix and finds the possible values of next entry and returns them as result.
- GenerateNode: Generates the queue of possible values for a node and call itslef recursively for them.
- GenerateTree: Defines the root node and tries to generate main tree on it.
I'm going to describe all these methods in more detail here:
Calculate Method
This is a function that create an instance of ArrayList, Generates main Tree to find the results and finally adds all results to ArrayList as output:
''' <summary>
''' This function tries to generate main tree and add all squares
''' to an ArrayList and returns it as result
''' </summary>
''' <returns>An ArrayList of all Latin Squares of order intOrder</returns>
''' <remarks></remarks>
Public Function Calculate() As ArrayList
Dim List As New ArrayList
GenerateTree()
While ReturnList.Count <> 0
List.Add(ReturnList.Pop)
End While
Return List
End Function
GenerateTree Method
Just defines the root node and call GenerateNode() for it to find other nodes:
''' <summary>
''' This sub routin tries to define root node and generate main tree on root node
''' </summary>
''' <remarks></remarks>
Private Sub GenerateTree()
Dim Root As New TreeNode(intOrder)
For i As Integer = 0 To UBound(Root.Board, 1)
For j As Integer = 0 To UBound(Root.Board, 2)
Root.Board(i, j) = 0
Next
Next
GenerateNode(Root)
End Sub
GenerateNode Method
Gets a node (ByRef), first calls CheckValues() and saves all nodes in ChildsList then creates new node and copies node's matrix to this new one then follows a simple process to add all possible nodes to a link list. Finally adds the Head node as the child of incoming node then calls itself recursively for each node in this link list:
''' <summary>
''' This sub routine tries to generate all possible childs for a node and
''' generate their child recursively by calling
''' itself again on each child
''' </summary>
''' <param name="Node">Currrent node that we want to generate
''' its possible childs</param>
''' <remarks></remarks>
Private Sub GenerateNode(ByRef Node As TreeNode)
Dim ChildsList As ArrayList = CheckValues(Node.Board)
If ChildsList.Count <> 0 Then
Dim Head As New TreeNode(intOrder)
Dim CursorNode As New TreeNode(intOrder)
Array.Copy(Node.Board, CursorNode.Board, intOrder * intOrder)
CursorNode.Board(CType(ChildsList(0), TempStruct).intRow, _
CType(ChildsList(0), TempStruct).intColumn) = _
CType(ChildsList(0), TempStruct).intValue
Head = CursorNode
For Each objItem As TempStruct In ChildsList
If System.Object.Equals(objItem, CType(ChildsList(0), TempStruct)) Then
Continue For
End If
Dim TempNode As New TreeNode(intOrder)
Array.Copy(Node.Board, TempNode.Board, intOrder * intOrder)
TempNode.Board(objItem.intRow, objItem.intColumn) = objItem.intValue
CursorNode.NextNode = TempNode
CursorNode = CursorNode.NextNode
Next
Node.Son = Head
Dim AnotherNode As New TreeNode(intOrder)
AnotherNode = Head
While AnotherNode IsNot Nothing
GenerateNode(AnotherNode)
AnotherNode = AnotherNode.NextNode
End While
End If
End Sub
CheckValues Method
This function gets a matrix and returns an ArrayList. This ArrayList contains some intances of TempStruct. Each instance has a possible value and its row and column indexes for next empty entry for incoming matrix. If it can't find a possible value for a matrix and that matrix doesn't have empty entries then marks it as a result by adding it to ReturnList stack:
''' <summary>
''' This function gets a matrix and checks all possible values for next empty entry in it.
''' </summary>
''' <param name="Board">The matrix of our current node</param>
''' <returns>An ArrayList of TempStruct node that contain the
''' Row and Column of next node with its possible value</returns>
''' <remarks></remarks>
Private Function CheckValues(ByVal Board(,) As Byte) As ArrayList
Dim Row As Integer = -1
Dim Col As Integer = -1
Dim List As New ArrayList
For i As Integer = 0 To UBound(Board, 1)
For j As Integer = 0 To UBound(Board, 2)
If (Board(i, j) = 0) And (Row = -1 And Col = -1) Then
Row = i
Col = j
End If
Next
Next
If Row = -1 And Col = -1 Then
ReturnList.Push(Board)
Else
For Number As Integer = 1 To intOrder
Dim blnCase As Boolean = True
For i As Integer = 0 To Row - 1
If Board(i, Col) = Number Then
blnCase = False
End If
Next
For j As Integer = 0 To Col - 1
If Board(Row, j) = Number Then
blnCase = False
End If
Next
If blnCase = True Then
Dim Temp As TempStruct
Temp.intRow = Row
Temp.intColumn = Col
Temp.intValue = Number
List.Add(Temp)
End If
Next
End If
Return List
End Function
This was the main work. In Module1, I created some instances of these classes then used a simple code snippet to save results in a text file.
[advertisement] Axosoft OnTime 2008 is four developer tools in one: bug tracking, project wiki, feature management, and help desk. It manages your development process so developers can focus on coding. Installed or Hosted – Free Single-user license -- Free 30-day team trial.
1 Comment : 12.28.05
#1
Keyvan Nayyeri
08.14.2007 @ 10:02 AM