Help with a recursive function

[Opaquer]

Hey guys

I'm still working on my Sudoku app and had a bit of a technical question. I'm trying to make the app solve given sudokus, and the best way is to use a recursive backtracking function. Basically, it'll find an empty square, see what values are legal, put the first choice in, then move to the next empty square and repeats the process. If it gets to a square where there's no legal options, it'll leave it empty and go back to the previous square and put the next legal value in. It then repeats this process, and eventually, solves just about any given sudoku. See this link from Wikipedia on how it works better than I can explain it: https://upload.wikimedia.org/wikipedia/ ... acking.gif

The only problem is that for some reason, I think I've done something wrong. Where every other backtracking algorithm is basically instant, mine hangs for about 30 seconds on my computer before it finally works it out (and by hanging, I mean LC goes non-responsive on me and my cursor changes to a circle instead of being a normal cursor). I think I've made a slight mistake in calling my handler from within the handler, and also with where and how to exit it. This is the code I have for it at the moment:

Code: Select all

on SolveGrid
   repeat with i=1 to 9
      put i into Row
      repeat with j=1 to 9
         put j into Col
         if item Col of TestCellTracker[Row]=0 then
            put WorkOutValues(Row,Col) into Values
            repeat with m=1 to 9
               if Values[m]=0 then
                  put m into item Col of TestCellTracker[Row]
                  SolveGrid
               end if
            end repeat
            if CheckGrid()=False then
               put 0 into item Col of TestCellTracker[Row]
               exit SolveGrid
            end if
         end if
      end repeat
   end repeat
end SolveGrid

So basically I call the SolveGrid handler, it goes through the rows and columns and finds a blank space (the if Item Col of TestCellTracker[Row]=0 line). The WorkOutValues function checked the specific row/cell and returns an 9 digit array showing what numbers are valid (see picture below - a 0 in that key means it's valid, whereas anything else is invalid), and does a check to see if it's valid (if Values[m]=0 then...). If it's a valid number, it puts that value into the grid solution (put m into item Col of TestCellTracker[Row]) and restarts the handler again with the updated test solution.

The process then remains the same, and if it finds another valid number to put into the next grid, it will, and repeat that until there's no valid numbers left. At that point, the repeat for variable m is over, and it does CheckGrid, which basically just returns true/false if there's any empty spaces left. If the repeat is over and there's empty spaces left, the sudoku hasn't been completed and there was a mistake, so it puts a 0 (empty cell) into cell it was working on and exits SolveGrid.

This is where I'm not sure if it does what it should be doing. Ideally, it will exit out of of that entire section to go back to the previous square (which from what I can tell it does), tries the next value of m and so on until it gets a solution.

My issue is that for some reason it hangs like crazy. Not sure exactly why - maybe I'm calling things wrong or exiting out of them wrong, but it takes so long to solve it (not to mention there's also a bug somewhere, but I can fix that up once it's faster). I've tried to put breakpoints into it at a specific place that only takes a single iteration to get through to try and fix the bug, and noticed that as time went on, it would take longer and longer to get to the breakpoint, as if it had to calculate more and more steps each time. Is that just something LC does, or is it because of a leak I have somewhere?

Many thanks, and if you guys want clarification on any of the steps or more code or anything, let me know!

[dunbarx]

Hi.

Hard to know what is going on, especially since you say the routine always finishes successfully. That is, it does not hang, finding itself in an endless loop that will eventually force LC to terminate. Can you step through at all, to see how the handler goes? Maybe if you use one of those nearly done or very easy puzzles you can get through faster.

During the "hanging" phase, does CMD-dot not work?

Craig

[SparkOut]

I haven't had chance to test, or even look properly, but given that it is a recursive function it might just be that it is iterating a helluva lot and taking time in the loop. Perhaps locking messages and locking screen for the duration of processing will help?
If not, it might be possible to optimise in other ways, or as well. But don't hold your breath for me to get chance, sorry, although I will look if I can.

[dunbarx]

Cannot test at all without knowing what the other handlers are. "TestCellTracker", "WorkOutValues", "CheckGrid".

That is why I asked if you can step into "solveGrid", stepping "over" the subroutines, just to speed the process up. It still might give a clue.

But as Sparkout says, there may be nothing wrong basically, just a lot of steps.

Nobody calls them subroutines anymore.

Craig

[Opaquer]

Hey guys

Thanks for the suggestion and advice - I had someone else from the forums have a look over it and we found a few things that could be optimised, but in the end it just comes down to it taking a lot longer than I expected. I was comparing it to some python code I found that did what I wanted, but the sudoku in the python code was a lot easier to solve than the sudoku I was giving my code. I've started looking into other ways to optimise it, so we'll see what happens!

Thanks for the advice and for getting back to me!