[RESOLVED] [VB] Sudoku Solver

Hi,

I have been experimenting to see how much time part of my programme takes. Taking one puzzle which took me 12 minutes manually, the total time shown by the programme was 10.00144 ms (excluding display). No matter where I split the programme for timing, the first segment always took 10.00144 ms and the remainder took 0 ms ???????

Even when I tried limiting the entire programme to completing 50 slots instead of the 81, it still took 10.00144 ms!!!!

My code for timing is

VB Code:

Dim tTime As DateTime
 
 
        tTime= Now   'Placed before the begining of the loop carrying out the
                           operation
        MessageBox.Show(Now.Subtract(tTime).ToString & "  Iterations  " & x.ToString)     'Placed immediately the loop has finished

Also, I have a reset button which clears all the variables and even if I enter an entirely separate puzzle by hand, the solving of a puzzle after the use of the reset button is regularly (but not always) shown to take 0 ms !!!

Is there anything wrong with this code for this purpose?
If not, can anyone suggest a reason for the apparent time innacuracies?

Probably the timer used isn't accurate enough for the task. Try to find out how you could use QueryPerformanceCounter in .NET.

This is the code of the VB6 class module sTime.cls:

Code:

---

'******* sTime.cls *******
'PROPERTY:
Private in_RetTime As Double

'VARIABLES:
Private tFreq As Currency
Private tStart As Currency
Private tStop As Currency
Private gTC As Boolean

'DECLARATIONS:
Private Declare Function QueryPerformanceFrequency Lib "kernel32" (lpFrequency As Currency) As Long
Private Declare Function QueryPerformanceCounter Lib "kernel32" (lpPerformanceCount As Currency) As Long
Private Declare Function GetTickCount Lib "kernel32" () As Long

Public Property Get RetTime() As Double
    RetTime = in_RetTime 'Returns Seconds
End Property

Public Sub Init()
    QueryPerformanceFrequency tFreq
    If tFreq = 1000 Then
        gTC = True
    Else
        gTC = False
    End If
End Sub

Public Sub StopTime()
    If gTC Then
        tStop = CCur(GetTickCount)
    Else
        QueryPerformanceCounter tStop
    End If
    in_RetTime = (tStop - tStart) / tFreq
End Sub

Public Sub StartTime()
    If gTC Then
        tStart = CCur(GetTickCount)
    Else
        QueryPerformanceCounter tStart
    End If
End Sub

---

Hi Merri,

I don't see how that will make any difference. It still uses the internal timer, which has always been appropriate in the past. I've tried adding large loops to the programme and then deducting the time taken for those loops but get a ridiculous figure - 400 ms!!

Hi,

Using a Timer control with an interval of 1, it appears that my programme completes somewhere between 1 and 2 firing events. i.e. between 1 thousandth and 2 thousandths of a second, but the code I posted still shows 10.00144 milliseconds.

How have you guys managed to obtain timings so low? (I mean how did you calculate the time?)

Quote:

---

Originally Posted by taxes

Hi,

Using a Timer control with an interval of 1, it appears that my programme completes somewhere between 1 and 2 firing events. i.e. between 1 thousandth and 2 thousandths of a second, but the code I posted still shows 10.00144 milliseconds.

How have you guys managed to obtain timings so low? (I mean how did you calculate the time?)

---

Using the sTime.cls class. When you call the Init Sub, put a break point, and step throug the Init sub.
If your not clear, step through this code (using F8):

VB Code:

Public Sub Init()
    QueryPerformanceFrequency tFreq
    If tFreq = 1000 Then
        gTC = True
    Else
        gTC = False
    End If
End Sub

Does the gTC varible gets set to True for False ?

If it's True, your computer cannt support fast timers (i.e. QueryPerformanceFrequency does not work for you), and it's using the GetTickCount instead, wich does not go below 10 Ms...

So, most likely that's the problem in your case. It's a motherboard thing, so there's nothing you can do about it, except to get a new computer.

Hi CVMichael

Right. many thanks. My motherboard is 2.5 years old.

So what that means is that although the Timer Control interval will fire every 1 ms, I can't use timespan etc to accurately measure the speed of the processing. All I know is that it is between 1 and 2 ms. Is that correct please? If so, that means I am going to have to use cumbersum routines to check what alterations to make to speed things up. e.g. What is the effect of declaring variables at codeblock level as compared with giving them formwide scope... Should I combine row and column checks within the same loop or have independent loops ... Should I check rows and columns after or before checking miniblocks .... Should I use multidemsion arrays of 9 * 9 or single dimension ones of 81 elements .... etc. How many months do we have to complete this thing???

Quote:

---

Originally Posted by taxes

Hi CVMichael

Right. many thanks. My motherboard is 2.5 years old.

So what that means is that although the Timer Control interval will fire every 1 ms, I can't use timespan etc to accurately measure the speed of the processing. All I know is that it is between 1 and 2 ms. Is that correct please?

---

Well, I think everything is affected by that, so even your timer control, even if you set it 1 ms, it does not mean that it actually fires at 1 ms, it's probably 10-20 ms for the timer control...
Actually... the timer control fires at 10-20 ms regardless of what computer you have (it's how the timer control was made... and it was not made for such high speeds)

Quote:

---

If so, that means I am going to have to use cumbersum routines to check what alterations to make to speed things up. e.g. What is the effect of declaring variables at codeblock level as compared with giving them formwide scope... Should I combine row and column checks within the same loop or have independent loops ... Should I check rows and columns after or before checking miniblocks .... Should I use multidemsion arrays of 9 * 9 or single dimension ones of 81 elements .... etc.

---

I'm afraid your gonna have to test and see for yourself. I only have speculations/assumptions, I don't know for sure what's faster.

Quote:

---

How many months do we have to complete this thing???

---

The original thread (the contest thread) is here: Contest 6 - Sudoku solver
It says "Final Entry Date 26th August 2005"

Quote:

---

Originally Posted by CVMichael

Well, I think everything is affected by that, so even your timer control, even if you set it 1 ms, it does not mean that it actually fires at 1 ms, it's probably 10-20 ms for the timer control...
Actually... the timer control fires at 10-20 ms regardless of what computer you have (it's how the timer control was made... and it was not made for such high speeds)

---

Hi,

So that means all I know is that my solution is faster than 10ms!!!


[QUOTE=CVMichael]I'm afraid your gonna have to test and see for yourself. I only have speculations/assumptions, I don't know for sure what's faster./QUOTE]


Sorry, I was not asking you those questions. I was just putting my thoughts into print. I have already checked and found out that there is no difference in speed whether variables are declared with form or block scope. Now I'm working on the others.

Thanks for the competition info.

One suggestion I have to calculate the time is: solve the same sudoku 1000 times in a loop, and get the total time, then divide by 1000. I think you will have a more precise result...

FYI
New Puzzle Sets:

http://www.vbforums.com/showpost.php...5&postcount=79

:wave:
-Lou

how i rid of duplicated "9" ?
Public Sub SHOW_ME_SODUKO(ByRef mOutMat(,,,) As Long)

Dim SQ_COL, SQ_ROW, CL_COL, CL_ROW, c_Num As Long
For SQ_COL = 0 To 2
For SQ_ROW = 0 To 2
For CL_COL = 0 To 2
For CL_ROW = 0 To 2
c_Num = mOutMat(SQ_COL, SQ_ROW, CL_COL, CL_ROW)
Debug.WriteLine("cnym :" & c_Num)
MyBoxes(SQ_COL, SQ_ROW, CL_COL, CL_ROW).Text = c_Num
If MyBoxes(SQ_COL, SQ_ROW, CL_COL, CL_ROW).Text = 0 Then MyBoxes(SQ_COL, SQ_ROW, CL_COL, CL_ROW).Text = 9
' If MyBoxes(SQ_COL, SQ_ROW, CL_COL, CL_ROW).Text = -1 Then Exit For
Debug.WriteLine(SQ_COL & " " & SQ_ROW & " " & CL_COL & " " & CL_ROW)
Next
Next
Next
Next
End Sub

Hi supra,

Is that code to show the values, or to work them out? I'm guessing that it is to work them out, but I could be wrong!

At the moment your code only puts the value 9 into the boxes ( If MyBoxes(...).Text = 0 Then MyBoxes(...).Text = 9 )

Instead of doing this you need to work out which numbers are valid at each position, and enter the numbers you know must be in a particular place. For example, if you have the following in one of the 3x3 grids:

123
789
45.

Then the last number must be a 6, as each of the 3x3 grids must contain all of the values 1-9, and 6 is the only number which hasn't been used.


Of course most puzzles are not this simple, but there should always be a way f working out at least one number that needs to be placed (either by checking rows, columns, or 3x3 grids, or some other method).


By the way, only your c_Num variable is defined as a Long, if you want them all to be Long then you should have this:

VB Code:

Dim SQ_COL As Long, SQ_ROW As Long, CL_COL As Long, CL_ROW As Long, c_Num As Long

yes. it show values. if u c zero then i changed to 9 that fine. but after ten click or less or or more i got 2 grids so far testing for bug....u can only see 2 nines in grids t same times. this only comming from Sub SHOW_ME_SODUKO procedure event. but randon started from 0 to 8 instead of 1 to 9. i got 95% efficiency right now.
regards,
supra

si_the_geek
u don't have to do that. in vb.net u can shortcut like this:
Dim SQ_COL, SQ_ROW, CL_COL, CL_ROW, c_Num As Long
instead of Dim SQ_COL As Long, SQ_ROW As Long, CL_COL As Long, CL_ROW As Long, c_Num As Long
that is way i read books.
regards,

si_the_geek
the is answer is NO!

Instead of doing this you need to work out which numbers are valid at each position, and enter the numbers you know must be in a particular place. For example, if you have the following in one of the 3x3 grids:

123
789
45.

cannot be 6 because of of first block and third block in column(top and bottom). i have lloked in each column that alread have 6 in grid. so 6 cannot be it.
i think if i see double 9 then then exist and then do random again. that is best way to do this.
regards,

to taxes,
r u trying to do countdown timer. i still have countdown timer working.
regards

Quote:

---

Originally Posted by supra

to taxes,
r u trying to do countdown timer. i still have countdown timer working.
regards

---

I'm doing nothing about it at the moment. For 3 days Norton NIS 2005 has stopped me using VB.NET!!!!!! They have promised me a correcting patch but it hasn't come yet :sick:

supra: instead of posting five messages in a row, you could consider editing the last post. Would result in one post instead of five and look cleaner.

:wave: (hello) i almost fixed bug for suduko.
does ne 1 wants to test my suduko.exe? :bigyello:
kindly, email me :thumb:
regards,

btw. what contest......it is prize money? :bigyello:

Supra,

First of all, exe's are frowned upon around here.
Second of all, why not join the contest, found here:

http://www.vbforums.com/showthread.php?t=351477

And, Third of all, join in the discussion of the contest HERE:
http://www.vbforums.com/showthread.php?t=351476

:wave:
-Lou

Just to inform you that there were some additions (features) in the rules of the contest. Check here : http://www.vbforums.com/showthread.php?t=351477

Sorry for the inconvenience... :(

:confused: damn!!!!!!! bug again :mad:

Well I have to say that this thread has the most replies of any question I have asked in 5 years! :afrog:

The only problem with everyones solutions is that you can't manually type in your puzzles into the grids.

Perhaps I'll modify Merris code slightly to allow this.

Good job everyone! :thumb:

i almost solved it.
ne body wanting to test my suduko game.
regards,
supra

If you post your code I'll have a look :)

u can get zip file from notlkh

Quote:

---

Originally Posted by supra

u can get zip file from notlkh

---

What should NotLKH put in the zip file?
:confused:

Careful how you answer that Supra. Notlkh is Somethingelse under another name :bigyello:

Quote:

---

Originally Posted by Something Else

What should NotLKH put in the zip file?
http://www.vbforums.com/attachment.p...postid=1797398

---

Sorry. Still http://www.vbforums.com/attachment.p...postid=1797398
What does NotLKH have to do with your app?

http://www.vbforums.com/attachment.p...postid=1797398http://www.vbforums.com/attachment.p...postid=1797398http://www.vbforums.com/attachment.p...postid=1797398

never mind again,fella(s). i still got bug again after clicking more 10 times. i still c duplicated numbers. :sick: