sandyd Posted October 4, 2006 Share Posted October 4, 2006 Hi all, I've been given a problem and am haiving a hell of approblem trying to figure it out.In the following grid:I need to get all permetations of 4 moves. I can only move left,right,up or down, NOT diagonally. I have already stored all possible moves from each square in an array numbered 1 to 36.So, say 1 start at square 1:Available moves are 2,7Loop through available moves Get next moves (if 2 then 3,8 since 1 has already been used; if 7 then 8,13 since 1 has already been used) Loop through available moves ... ...EndloopI would like to, and reckon this should be done with recursion.Can anyone give me any pointers how to get going? ----[ SandyD ]--- Link to comment Share on other sites More sharing options...
BitRot Posted October 4, 2006 Share Posted October 4, 2006 I need to get all permetations of 4 moves.Is that exactly 4 moves, or 4 moves or less ? Notice that if you mean exactly that, when you start at square 1 you can't reach, for example, the squares 2 and 7.And what do you mean with "permutations" ? Do you need a list of all "roads", or do you only want to know which numbers are reachable ?I would like to, and reckon this should be done with recursion.Depending on what you actually want a four simple "for" loops (inside each other) might do the trick too. Link to comment Share on other sites More sharing options...
sandyd Posted October 4, 2006 Author Share Posted October 4, 2006 No not exactly, I can have 3 or 4 moves. I need to know the path taken In fact its actually up to 10 moves, so recursion is probably needed ----[ SandyD ]--- Link to comment Share on other sites More sharing options...
jvanegmond Posted October 4, 2006 Share Posted October 4, 2006 Yes, you will probably need something like a $CurrentGrid[2] = [x,y] variable to start with. Then you need a list of all the values that you have already been through. Check the value of the currentgrid against the list. If it's not in the list, then add that grid to a array called $GridsToCheck or something. Then $CurrentGrid is read from $GridsToCheck, and the cycle starts again. Note: This is very much doable, so don't tell me you don't understand or can't make this on your own, cause I'm not going to do it for you. (I've had bad experiences with this) github.com/jvanegmond Link to comment Share on other sites More sharing options...
BitRot Posted October 4, 2006 Share Posted October 4, 2006 No not exactly, I can have 3 or 4 moves.Thats, together with your last line ("actually up to 10 moves") a bit vague : why not 1 or 2 steps too ? And if 10 steps is your goal, how many steps are than valid ? 9 and 10 ? Or anything from 3 to 10 steps ? In fact its actually up to 10 moves, so recursion is probably neededNope. To proove that I included something that uses a simple X-by-3 array to remember previous X,Y and direction : expandcollapse popup;-- Storage for the steps & max path-length dim $path[4][3] ;-- The 4 here is the number of steps. change if you like ;-- Width & height of field $w=10 $h=10 $i=0 ;-- Starting-point $path[$i][0]=8 $path[$i][1]=9 $path[$i][2]=0 do if $path[$i][2]>=4 Then ;-- All directions done ? $i-=1 ;-- Yep, back to previous step else ;-- Where is the next location next of the current step ? switch $path[$i][2] case 0 $x=$path[$i][0]+1 $y=$path[$i][1] case 1 $x=$path[$i][0] $y=$path[$i][1]+1 case 2 $x=$path[$i][0]-1 $y=$path[$i][1] case 3 $x=$path[$i][0] $y=$path[$i][1]-1 EndSwitch $path[$i][2]+=1 ;-- Increment current direction if $x>=0 and $x<$w and $y>=0 and $y<$h then ;-- Only if the next step is within the field ;-- Did we allready pass that next step ? for $j=0 to $i-1 if $x=$path[$j][0] and $y=$path[$j][1] then ExitLoop Next if $j=$i then ;-- Nope, we did not if $i+1<ubound($path,1) then ;-- More steps to do ! $i+=1 $path[$i][0]=$x $path[$i][1]=$y $path[$i][2]=0 Else ;-- Display the full path, plus the last step ConsoleWrite($path[0][0]&","&$path[0][1]) for $j=1 to ubound($path,1)-1 ConsoleWrite(" - "&$path[$j][0]&","&$path[$j][1]) Next ConsoleWrite(" - "&$x&","&$y&@crlf) Endif EndIf Endif EndIf until $i<0But you are right : a recursive solution that uses a full playing-field array (to mark the allready-passed squares) looks a lot better (but does not show a simple solution-list like the above code does). Yep, I tried that one too. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now