Solving Suduko
#1
Solving Suduko
In order to make a program to solve Suduko puzzles, I created 2 arrays.
nUsed ( 0 to 8, 0 to 2)
the 2nd dimension is broken down by Box, Row and Column.
nData ( 0 to 80, 0 to 4)
the 2nd dimension of this array is Box, Row, Col, Value and a IsKnown flag.
Since I this was programmed in Excel, I assumed that cells A1:I9 represented the Suduko range.
[hr]
First you load the known values into the arrays. Loop through the Rows with a nest column loop. (During the loop, I bolded the known values so that I could distinguish them later)
For nCurRowPos = 0 To 8
For nCurColPos = 0 To 8
nCurValue = ActiveSheet.Cells(nCurRowPos + 1, nCurColPos + 1)
ActiveSheet.Cells(nCurRowPos + 1, nCurColPos + 1).Font.Bold = nCurValue > 0
Select Case nCurRowPos
Case Is < 3
nCurYCube = 0
Case Is < 6
nCurYCube = 3
Case Else
nCurYCube = 6
End Select
Select Case nCurColPos
Case Is < 3
nCurCubePos = nCurYCube + 0
Case Is < 6
nCurCubePos = nCurYCube + 1
Case Else
nCurCubePos = nCurYCube + 2
End Select
'* Assign indexes for Future reference
nData(nCurValuePos, enValueCategory.vc_BoxIdx) = nCurCubePos
nData(nCurValuePos, enValueCategory.vc_ColIdx) = nCurColPos
nData(nCurValuePos, enValueCategory.vc_RowIdx) = nCurRowPos
nData(nCurValuePos, enValueCategory.vc_Value) = nCurValue
If nCurValue = 0 Then
Else
nData(nCurValuePos, enValueCategory.vc_IsKnown) = 1
nUsed(nCurCubePos, enUsedType.ut_BoxIdx) = (nUsed(nCurCubePos, enUsedType.ut_BoxIdx) Or (2 ^ nCurValue))
nUsed(nCurColPos, enUsedType.ut_ColIdx) = (nUsed(nCurColPos, enUsedType.ut_ColIdx) Or (2 ^ nCurValue))
nUsed(nCurRowPos, enUsedType.ut_rowIdx) = (nUsed(nCurRowPos, enUsedType.ut_rowIdx) Or (2 ^ nCurValue))
End If
nCurValuePos = nCurValuePos + 1
Next 'x
Next 'y
[hr]
The actually solving subroutine is recursive. The routine is called ufnSolve and takes in the 2 arrays and the current data position.
nBox = nData(nCurDataPos, enValueCategory.vc_BoxIdx)
nRow = nData(nCurDataPos, enValueCategory.vc_RowIdx)
nCol = nData(nCurDataPos, enValueCategory.vc_ColIdx)
If nData(nCurDataPos, enValueCategory.vc_IsKnown) Then
'* Handling here is questionable.
If nCurDataPos >= 80 Then
Else
hr = ufnSolve(nUsed, nData, nCurDataPos + 1)
If hr = 0 Then
Else
ufnSolve = -1
End If
End If
Else
nValue = 1
fEnd = False
Do Until fEnd = True
fUsed = False
If (nUsed(nBox, enUsedType.ut_BoxIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Or (nUsed(nRow, enUsedType.ut_rowIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Or (nUsed(nCol, enUsedType.ut_ColIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Then
fUsed = True
Else
End If
If fUsed = True Then
If nValue >= 9 Then
ufnSolve = -1
fEnd = True
Else
nValue = nValue + 1
End If
Else
nUsed(nBox, enUsedType.ut_BoxIdx) = (nUsed(nBox, enUsedType.ut_BoxIdx) Or (2 ^ nValue))
nUsed(nRow, enUsedType.ut_rowIdx) = (nUsed(nRow, enUsedType.ut_rowIdx) Or (2 ^ nValue))
nUsed(nCol, enUsedType.ut_ColIdx) = (nUsed(nCol, enUsedType.ut_ColIdx) Or (2 ^ nValue))
nData(nCurDataPos, enValueCategory.vc_Value) = nValue
If nCurDataPos >= 80 Then
fEnd = True
Else
hr = ufnSolve(nUsed, nData, nCurDataPos + 1)
If hr = 0 Then
fEnd = True
Else
nUsed(nBox, enUsedType.ut_BoxIdx) = (nUsed(nBox, enUsedType.ut_BoxIdx) And Not (2 ^ nValue))
nUsed(nRow, enUsedType.ut_rowIdx) = (nUsed(nRow, enUsedType.ut_rowIdx) And Not (2 ^ nValue))
nUsed(nCol, enUsedType.ut_ColIdx) = (nUsed(nCol, enUsedType.ut_ColIdx) And Not (2 ^ nValue))
nData(nCurDataPos, enValueCategory.vc_Value) = 0
If nValue >= 9 Then
ufnSolve = -1
fEnd = True
Else
nValue = nValue + 1
End If
End If
End If
End If
Loop 'fEnd = True
End If
[hr]
Ok, got it? Now all you need to do is load the data back into the excel file.
nUsed ( 0 to 8, 0 to 2)
the 2nd dimension is broken down by Box, Row and Column.
nData ( 0 to 80, 0 to 4)
the 2nd dimension of this array is Box, Row, Col, Value and a IsKnown flag.
Since I this was programmed in Excel, I assumed that cells A1:I9 represented the Suduko range.
[hr]
First you load the known values into the arrays. Loop through the Rows with a nest column loop. (During the loop, I bolded the known values so that I could distinguish them later)
For nCurRowPos = 0 To 8
For nCurColPos = 0 To 8
nCurValue = ActiveSheet.Cells(nCurRowPos + 1, nCurColPos + 1)
ActiveSheet.Cells(nCurRowPos + 1, nCurColPos + 1).Font.Bold = nCurValue > 0
Select Case nCurRowPos
Case Is < 3
nCurYCube = 0
Case Is < 6
nCurYCube = 3
Case Else
nCurYCube = 6
End Select
Select Case nCurColPos
Case Is < 3
nCurCubePos = nCurYCube + 0
Case Is < 6
nCurCubePos = nCurYCube + 1
Case Else
nCurCubePos = nCurYCube + 2
End Select
'* Assign indexes for Future reference
nData(nCurValuePos, enValueCategory.vc_BoxIdx) = nCurCubePos
nData(nCurValuePos, enValueCategory.vc_ColIdx) = nCurColPos
nData(nCurValuePos, enValueCategory.vc_RowIdx) = nCurRowPos
nData(nCurValuePos, enValueCategory.vc_Value) = nCurValue
If nCurValue = 0 Then
Else
nData(nCurValuePos, enValueCategory.vc_IsKnown) = 1
nUsed(nCurCubePos, enUsedType.ut_BoxIdx) = (nUsed(nCurCubePos, enUsedType.ut_BoxIdx) Or (2 ^ nCurValue))
nUsed(nCurColPos, enUsedType.ut_ColIdx) = (nUsed(nCurColPos, enUsedType.ut_ColIdx) Or (2 ^ nCurValue))
nUsed(nCurRowPos, enUsedType.ut_rowIdx) = (nUsed(nCurRowPos, enUsedType.ut_rowIdx) Or (2 ^ nCurValue))
End If
nCurValuePos = nCurValuePos + 1
Next 'x
Next 'y
[hr]
The actually solving subroutine is recursive. The routine is called ufnSolve and takes in the 2 arrays and the current data position.
nBox = nData(nCurDataPos, enValueCategory.vc_BoxIdx)
nRow = nData(nCurDataPos, enValueCategory.vc_RowIdx)
nCol = nData(nCurDataPos, enValueCategory.vc_ColIdx)
If nData(nCurDataPos, enValueCategory.vc_IsKnown) Then
'* Handling here is questionable.
If nCurDataPos >= 80 Then
Else
hr = ufnSolve(nUsed, nData, nCurDataPos + 1)
If hr = 0 Then
Else
ufnSolve = -1
End If
End If
Else
nValue = 1
fEnd = False
Do Until fEnd = True
fUsed = False
If (nUsed(nBox, enUsedType.ut_BoxIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Or (nUsed(nRow, enUsedType.ut_rowIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Or (nUsed(nCol, enUsedType.ut_ColIdx) And (2 ^ nValue)) = (2 ^ nValue) _
Then
fUsed = True
Else
End If
If fUsed = True Then
If nValue >= 9 Then
ufnSolve = -1
fEnd = True
Else
nValue = nValue + 1
End If
Else
nUsed(nBox, enUsedType.ut_BoxIdx) = (nUsed(nBox, enUsedType.ut_BoxIdx) Or (2 ^ nValue))
nUsed(nRow, enUsedType.ut_rowIdx) = (nUsed(nRow, enUsedType.ut_rowIdx) Or (2 ^ nValue))
nUsed(nCol, enUsedType.ut_ColIdx) = (nUsed(nCol, enUsedType.ut_ColIdx) Or (2 ^ nValue))
nData(nCurDataPos, enValueCategory.vc_Value) = nValue
If nCurDataPos >= 80 Then
fEnd = True
Else
hr = ufnSolve(nUsed, nData, nCurDataPos + 1)
If hr = 0 Then
fEnd = True
Else
nUsed(nBox, enUsedType.ut_BoxIdx) = (nUsed(nBox, enUsedType.ut_BoxIdx) And Not (2 ^ nValue))
nUsed(nRow, enUsedType.ut_rowIdx) = (nUsed(nRow, enUsedType.ut_rowIdx) And Not (2 ^ nValue))
nUsed(nCol, enUsedType.ut_ColIdx) = (nUsed(nCol, enUsedType.ut_ColIdx) And Not (2 ^ nValue))
nData(nCurDataPos, enValueCategory.vc_Value) = 0
If nValue >= 9 Then
ufnSolve = -1
fEnd = True
Else
nValue = nValue + 1
End If
End If
End If
End If
Loop 'fEnd = True
End If
[hr]
Ok, got it? Now all you need to do is load the data back into the excel file.
#2
#3
#4
RE: Solving Suduko
^ i just finished a java class, i have experience in logic and design, but i normally program in php or javascript. i did fairly well in the class, 88, but there were times when i couldnt figure the language out. i looked and looked through our resources and the stuff just wasnt there, our instructor was useles. my counselor had asked how the class was, it wasnt bad for me, but i felt bad for people who had 0 programming experience, which was all but 2-3 people. i told her idk how people without passed the class and she said they didnt, lol.
#7
#9
RE: Solving Suduko
I was bored at work 2 yrs ago. So I created this. Kind of funny, the whole process of doing this really killed my desire to actually play suduko.
Even now, Unless I flow chart it back out, I have trouble understanding the code. This is actually the fault of the programmer (me) since the code really should be self documenting or appropriately commented.
Which is why programming and appropriate commenting is actually more of an art than technical.
Even now, Unless I flow chart it back out, I have trouble understanding the code. This is actually the fault of the programmer (me) since the code really should be self documenting or appropriately commented.
Which is why programming and appropriate commenting is actually more of an art than technical.
#10
RE: Solving Suduko
After I started working for my current company, I took the following classes at the local community college:
Intro to computers - (funny since I was providing computer support)
Structured Programming and Design - (The only class I feel was worthwhile)
C (this was good give me a little experience, but itĀ“s nothing that I couldĀ“t have learned faster on my own. Spent most of the class making fun of the teacher with the girl next to me).
C++ (This was kindof cool...Good introduction of Polymorphism, Encapsulation and Inheritance.
VB (Complete waste...I was providing support for VB by the time I took this and had been supporting VBA for a good 2 yrs.)
Some business class
Although I maintained a 4.0 avg (how hard can that be with 1 class a semester :P ) I just find it difficult to learn in the class setting, itĀ“s too damn boring and slow. I wish I knew I had such an interest in programming when I was in high school (and knew about Carnegie Mellon), then I might have applied myself back then.
Intro to computers - (funny since I was providing computer support)
Structured Programming and Design - (The only class I feel was worthwhile)
C (this was good give me a little experience, but itĀ“s nothing that I couldĀ“t have learned faster on my own. Spent most of the class making fun of the teacher with the girl next to me).
C++ (This was kindof cool...Good introduction of Polymorphism, Encapsulation and Inheritance.
VB (Complete waste...I was providing support for VB by the time I took this and had been supporting VBA for a good 2 yrs.)
Some business class
Although I maintained a 4.0 avg (how hard can that be with 1 class a semester :P ) I just find it difficult to learn in the class setting, itĀ“s too damn boring and slow. I wish I knew I had such an interest in programming when I was in high school (and knew about Carnegie Mellon), then I might have applied myself back then.