Off Topic A place for you CBR junkies to boldly go off topic. Almost anything goes.

Solving Suduko

Thread Tools
 
Search this Thread
 
  #1  
Old 12-19-2008, 01:16 PM
woo545's Avatar
Senior Member
Thread Starter
Join Date: Jun 2007
Location: PA
Posts: 2,680
Likes: 0
Received 1 Like on 1 Post
Default 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.
 
  #2  
Old 12-19-2008, 02:13 PM
rrasco's Avatar
Senior Member
Join Date: Mar 2006
Location: South Texas
Posts: 5,844
Likes: 0
Received 1 Like on 1 Post
Default RE: Solving Suduko

im totally not into my own code atm, which makes me completely not into yours[8D]

looks like it would be a good reference, never hurts to know how to do one more thing
 
  #3  
Old 12-19-2008, 03:02 PM
Join Date: Jun 2006
Location:
Posts: 1,207
Likes: 0
Received 0 Likes on 0 Posts
Default RE: Solving Suduko

I took a class on logic and program design. We used dark basic pro to create a hang-man game. I swear my head swole up when I read your post from memories of that class. Hell, I can't even post pictures!
 
  #4  
Old 12-19-2008, 03:05 PM
rrasco's Avatar
Senior Member
Join Date: Mar 2006
Location: South Texas
Posts: 5,844
Likes: 0
Received 1 Like on 1 Post
Default 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.
 
  #6  
Old 12-19-2008, 04:21 PM
Join Date: Jun 2006
Location:
Posts: 1,207
Likes: 0
Received 0 Likes on 0 Posts
Default RE: Solving Suduko

It wasn't that hard when you got into it, just for people like me who will never use it, or have never used it, you might as well be teaching me algebra in greek.
 
  #7  
Old 12-19-2008, 04:33 PM
VP's Avatar
VP
VP is offline
Senior Member
Join Date: Aug 2006
Location: ATL
Posts: 4,934
Likes: 0
Received 0 Likes on 0 Posts
Default RE: Solving Suduko

wow I actually do them with my brain...

Although to be fair you used yours to figure this out, but I guess that's actually solving another puzzle and a sudoku puzzle at the same time, which is gotta be like twice as hard.
 
  #8  
Old 12-19-2008, 04:56 PM
rrasco's Avatar
Senior Member
Join Date: Mar 2006
Location: South Texas
Posts: 5,844
Likes: 0
Received 1 Like on 1 Post
Default RE: Solving Suduko

^ agreed, i dont even want to begin processing the logic
 
  #9  
Old 12-19-2008, 10:11 PM
woo545's Avatar
Senior Member
Thread Starter
Join Date: Jun 2007
Location: PA
Posts: 2,680
Likes: 0
Received 1 Like on 1 Post
Default 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.
 
  #10  
Old 12-19-2008, 10:22 PM
woo545's Avatar
Senior Member
Thread Starter
Join Date: Jun 2007
Location: PA
Posts: 2,680
Likes: 0
Received 1 Like on 1 Post
Default 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.
 


Quick Reply: Solving Suduko



All times are GMT -5. The time now is 05:00 AM.