Best iterating through all values for all elements in array

If you have questions about any aspect of QBasic programming, or would like to help fellow programmers solve their problems, check out this board!

Moderators: Pete, Mods

Post Reply
ThemePark
Coder
Posts: 17
Joined: Wed Aug 22, 2007 6:37 pm

Best iterating through all values for all elements in array

Post by ThemePark » Sat Aug 25, 2007 7:38 pm

Ya, quite a long title. It's a hard problem to cut down to a mere line of description.

Let's say that I have an array of 5x5 elements, i.e. a total of 25. Each of these elements can have a value from 1 to 4. And what I want to do is to check for all possible combinations of these values.

I'm aware that this will give me 4^25 different combinations, and I'm not quite sure it would even be possible in QuickBasic, which is why I turn to the experts here.

Or as another example, say I wanted to write a Sudoku program that would solve a Sudoku through brute force only.

Both examples would of course have some rules to limit the possible combinations, but I'd still have to iterate through them all first.

I have often come across places in my programming where I would want to do something like this, and have always solved it through the same kind of spaghetti code. Basically make the necessary For loops, make my calculations, and as long as I wasn't at the last element in the array, I'd go back to the first line inside the For loop and calculate again for the next element, or I'd call the function I was using again, i.e. make it recursive. I'll admit that those approaches fail horribly, especially in the time it takes to run the program through so many programs, but I don't have enough knowledge to know how it would best be done so.

As an example, I'd set each of the 25 elements to the value 1. Then no. 25 to 2, 3 and 4. Then I'd go back to element 24, add 1 to it so it becomes 2 and then begin from 1 with element 25. Then element 24 becomes 3 and 4, and then the same procedure with 23. All of this all the way back to element 1.

Is it even plausible to do something like that with QuickBasic (which I really hope it is) and if so, what is the best (read: fastest) way of doing it?

User avatar
Mentat
Veteran
Posts: 409
Joined: Tue Aug 07, 2007 3:39 pm
Location: NC, US

Post by Mentat » Mon Aug 27, 2007 8:40 pm

For the soduko, just use for loops and do it how you would personally.

Of course there is ASM:
The fastest way to do it. :)
The slowest way to write it. :D

What's the application? There might be a way around.

Let's see:

log 4^25 = 25 log 4 = 50 log 2 = 15 digits = 10^15
Around a quadrillion. :shock:
For any grievances posted above, I blame whoever is in charge . . .

ThemePark
Coder
Posts: 17
Joined: Wed Aug 22, 2007 6:37 pm

Post by ThemePark » Mon Aug 27, 2007 9:42 pm

Actually there's not a specific application. I have made many applications where I have had to do the basics of what I described above, but just with different values and I have never known a good way of doing it. The sudoku and my own example are just a couple of examples to show what I mean. Simply running through a 2 dimensional array and trying all possible combinations of the values. It's just like saying "Choose a value from 1 to X for all N cells, until you have tried every single combination."

I'm surprised at that number though. I did 4^25 without the log and got a few billions.

User avatar
Mentat
Veteran
Posts: 409
Joined: Tue Aug 07, 2007 3:39 pm
Location: NC, US

Post by Mentat » Tue Aug 28, 2007 6:00 am

I got 1.13 E 15 which is the calculator's short hand for saying 1.13 * (10^15), which is also 1,124,899,901,000,000.
For any grievances posted above, I blame whoever is in charge . . .

ThemePark
Coder
Posts: 17
Joined: Wed Aug 22, 2007 6:37 pm

Post by ThemePark » Tue Aug 28, 2007 7:20 am

Yeah you're right, sorry about that, the number I posted was from another project I had been working on.

But alright, let's boil it down to something a little smaller. It's the principle in it that I want to try out anyway.

For instance a 4x4 array where you have to choose between between the numbers 1, 2 and 3. What would be the best approach with that?

What I'm having trouble comprehending as well, is that there's a very high number of combinations for Sudokus, yet I've seen QuickBasic programs that solve them in a matter of seconds. It's that kind of speed and programming I would like to learn.

Mac
Veteran
Posts: 151
Joined: Mon Aug 06, 2007 2:00 pm

Post by Mac » Tue Aug 28, 2007 9:04 am

ThemePark wrote:What I'm having trouble comprehending as well, is that there's a very high number of combinations for Sudokus, yet I've seen QuickBasic programs that solve them in a matter of seconds. It's that kind of speed and programming I would like to learn.
Well, I read all your words several times and slept on them and read them again and still cannot figure out what you want to know.

Never mind saying a bunch of words again. It won't help.

Instead, write a simple application, such as the 4x4 array, in the only way you know how and post that code and we'll see what can be done to improve it.

But consider this problem, which may be what you are driving at:

----------------------------------------------
I have A(4,4) AS INTEGER. I want to fill the array with all 1's. Then I want to fill the array with all 1's except A(1,1)=2. Continue until finally the array contains all 3's. So that at some point, the array contains 1211/1132/3221/2212. Now as each case is produced, I want to perform tests on the array. I will continue until either reaching all 3's or finding a successful test.
----------------------------------------------

If this is what you want, then I for one cannot think of any good way. My advice would be "Don't do it that way", whatever it is you are doing.

I, for example, have written a fast SuDoku solver program.
http://www.network54.com/Forum/178387/m ... 1132625620

It uses the recursive technique you are familiar with. If you give it this puzzle
-----------36-21--9-----42-3-9-----25--7-1--46-----7-92-5-----8--68-35-----------
you will see that it reasonable quickly finds the 102 solutions to that puzzle and puts them in "Dump.txt".

BUT, I didn't simply take the cases 1-9 in r1c1 and then use recursion and do 1-9 in r1c2, etc. That would take forever.

Instead, I use a lot of known Sudoku solving techniques to solve as far as I can before finally resorting to recursion. As a result, I wind up only using 8 levels deep in recursion. The simple brute force method would put me about 70 levels deep.

To sum up: Figure out a way to avoid having the kind of problem you named. Unfortunately, there is no general advice on how to do that. Each problem requires it's own solution.

Mac

User avatar
Mentat
Veteran
Posts: 409
Joined: Tue Aug 07, 2007 3:39 pm
Location: NC, US

Post by Mentat » Tue Aug 28, 2007 4:20 pm

They're fast because they use fairly simple algorithms to solve Soduko. Sudoku is easy to program because humans have more or less the same mentality of solving sudoku; do lots of tedious repetitive work to get some done, and then high end logic to get those few Key spots normall strategies don't cover.
For any grievances posted above, I blame whoever is in charge . . .

Mac
Veteran
Posts: 151
Joined: Mon Aug 06, 2007 2:00 pm

Post by Mac » Fri Aug 31, 2007 8:29 am

ThemePark wrote:It's that kind of speed and programming I would like to learn.
So, did you get your answer above? It reduces to "Don't exhaustively do all possible cases but instead, figure out a way to do only some cases".

It was shown how to do that with a SuDoku solver. Do you have other applications that you would like to discuss?

Mac

ThemePark
Coder
Posts: 17
Joined: Wed Aug 22, 2007 6:37 pm

Post by ThemePark » Sat Sep 01, 2007 6:51 pm

Yep, I got it, but Mac, since you didn't understand what I was trying to explain, I made a small program to demonstrate it. Yes, I know it's horribly coded but it shows my purpose, which is all I intended for it to do.

Code: Select all

DECLARE SUB Method1 ()
DIM SHARED Grid(1 TO 5, 1 TO 5) AS INTEGER
DIM SHARED RowCounter AS INTEGER
DIM SHARED ColumnCounter AS INTEGER

RowCounter = 1
ColumnCounter = 1
Method1

SUB Method1
        DO UNTIL Grid(RowCounter, ColumnCounter) = 4
                Grid(RowCounter, ColumnCounter) = Grid(RowCounter, ColumnCounter) + 1
                IF ColumnCounter = 5 THEN
                        IF RowCounter = 5 THEN
                                CLS
                                FOR RC = 1 TO 5
                                        FOR CC = 1 TO 5
                                                PRINT Grid(RC, CC);
                                        NEXT
                                        PRINT
                                NEXT
                                SLEEP 0
                        ELSE
                                RowCounter = RowCounter + 1
                                ColumnCounter = 1
                                Method1
                        END IF
                ELSE
                        ColumnCounter = ColumnCounter + 1
                        Method1
                END IF
        LOOP
        Grid(RowCounter, ColumnCounter) = 0
        ColumnCounter = ColumnCounter - 1
        IF ColumnCounter = 0 THEN
                RowCounter = RowCounter - 1
                ColumnCounter = 5
        END IF
END SUB
Hence I would get the following printouts after each press of a key:

Code: Select all

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

Code: Select all

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 2

Code: Select all

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 3

Code: Select all

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 4

Code: Select all

1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
etc. etc. etc.

I hope you see what my point is. To iterate through all possible combinations in an AxB grid (in this case A=5 and B=5) where I have C (in this case C=4) possible values to choose from.

To go back to the Sudoku example, the difference with that is that you automatically assume that the start grid you have, only has one solution, so you're just looking for the first solution that matches the start grid and the rules you've set up.

In my case I always have a set of rules, but I need to run through each combination in order to find THE best one, not just the first one that matches the rules.

For instance, in this case, instead of the printout (which I wouldn't need in my real program, just added it for example), I would add all 25 values, and try to find the biggest sum. However, there are some rules as to how the 4 values can be placed, so it's not as easy as saying that the combination with 25 4's is the best one.

Now, I don't expect to get a different answer. But I have tried to clear up some of the confusion that apparently has been about my intentions. I hope this clears it up, and if this should change anything as for the advice for me, please let me know.

Btw, keep in mind that I'm speaking of programs like this in general. I'm not looking for a way to make this program, but for a good way of coding in which I can go through any not-too-big size grid with a small number of possible values, and find the best combination according to some rules I set up myself, upon having each combination.

Mac
Veteran
Posts: 151
Joined: Mon Aug 06, 2007 2:00 pm

Post by Mac » Sun Sep 02, 2007 2:22 pm

ThemePark wrote:To go back to the Sudoku example, the difference with that is that you automatically assume that the start grid you have, only has one solution, so you're just looking for the first solution that matches the start grid and the rules you've set up.
You missed something there. If you run my program with the puzzle supplied, you get ALL POSSIBLE SOLUTIONS not just one. In this case there are over a hundred such solutions. Even if there were only one, I would proceed to show there are no others. I don't know how many solutions there are until every case is tested. For most puzzles found in the newspaper this process takes less than one second!
ThemePark wrote:Btw, keep in mind that I'm speaking of programs like this in general. I'm not looking for a way to make this program, but for a good way of coding in which I can go through any not-too-big size grid with a small number of possible values, and find the best combination according to some rules I set up myself
I am trying to say that there is no way on earth to speed up the process of generating all possible combinations and testing them beyond minor optimization that is totally unacceptable for big problems. All problems will take lots, even years, of processing time. Instead, you have to figure out a way to avoid doing that.

But considering your not-too-big rule, maybe you have a chance. I'll try to come up with something.

Mac

User avatar
Mentat
Veteran
Posts: 409
Joined: Tue Aug 07, 2007 3:39 pm
Location: NC, US

Post by Mentat » Sun Sep 02, 2007 2:50 pm

Somtimes, the best way is for the computer to recreate the best matrix by using the rules.
For any grievances posted above, I blame whoever is in charge . . .

Mac
Veteran
Posts: 151
Joined: Mon Aug 06, 2007 2:00 pm

Here

Post by Mac » Sun Sep 02, 2007 3:44 pm

Here is the best generate-array/test-array algorithm I can do

Code: Select all

'DEFSTR A-Z ' Remove after ensuring all variables are defined
DIM a(3, 3) AS INTEGER, v AS INTEGER
DIM i AS INTEGER, j AS INTEGER
FOR i = 1 TO 3: FOR j = 1 TO 3: a(i, j) = 1: NEXT j: NEXT i
DIM Cases AS INTEGER
DO
  GOSUB TestArray
  Cases = Cases + 1
  IF Cases = 19683 THEN EXIT DO
  DO
    FOR i = 1 TO 3: FOR j = 1 TO 3
      v = a(i, j) + 1
      IF v > 3 THEN a(i, j) = 1 ELSE a(i, j) = v: EXIT DO
    NEXT j: NEXT i
  LOOP
LOOP
PRINT "End of run"
END

TestArray:
FOR i = 3 TO 1 STEP -1
  FOR j = 3 TO 1 STEP -1
    PRINT a(i, j);
  NEXT j
NEXT i
PRINT
IF INKEY$ <> "" THEN STOP
RETURN
Simply substitute for TestArray, your criteria. It is set up now to run so you can convince yourself you indeed get all cases.

Good luck. As I said, if I had a problem along that line to solve, especially if it were 4x4x4 (or 9x9x9 in Sudoku) I would figure out some other way. Unfortunately, each way is unique to the specific application.

For a stupid example, suppose my problem above was to find all arrays which have all cells the same, namely
111 111 111, 222 222 222, 333 333 333.
Then I would not generate all 3^9 cases and test

Code: Select all

Good=-1
do
  for i=1 to 3: for j=1 to 3
    if a(i,j)<>a(1,1) then Good=0: exit do
  next j: next i
loop while 1=2
if Good then .... Wow! I found 111 111 111 or 222 222 222 or 333 333 333
Instead, I would just generate those 3 cases. You might say "Duhh!" but I've seen cases where the dumb method was used. With the tool I posted above, you can possibly do the dumb way.

(Ignore me. Maybe that is the only way to solve your problem)

Mac

Mac
Veteran
Posts: 151
Joined: Mon Aug 06, 2007 2:00 pm

So 4x4x4 is 4,294,967,000 cases?

Post by Mac » Sun Sep 02, 2007 6:00 pm

LOL!

I stopped the program after a while and got

Code: Select all

 1  1  2  1  2  4  3  1  4  2  4  1  2  4  2  3
 1  1  2  1  2  4  3  1  4  2  4  1  2  4  2  4
 1  1  2  1  2  4  3  1  4  2  4  1  2  4  3  1
 1  1  2  1  2  4  3  1  4  2  4  1  2  4  3  2
 1  1  2  1  2  4  3  1  4  2  4  1  2  4  3  3
 75029626 out of 4294967296 took 6929.242
Not much progress after nearly 2 hours. Would probably finish in 110 hours!

Mac

Code: Select all

'DEFSTR A-Z ' Remove after ensuring all variables are defined
DIM StartTime AS SINGLE: StartTime = TIMER
DIM a(4, 4) AS INTEGER, v AS INTEGER
DIM i AS INTEGER, j AS INTEGER
FOR i = 1 TO 4: FOR j = 1 TO 4: a(i, j) = 1: NEXT j: NEXT i
DIM Cases AS DOUBLE, MaxCases AS DOUBLE: MaxCases = 4 ^ 16
DO
  GOSUB TestArray
  Cases = Cases + 1
  IF Cases = MaxCases THEN EXIT DO
  DO
    FOR i = 1 TO 4: FOR j = 1 TO 4
      v = a(i, j) + 1
      IF v > 4 THEN a(i, j) = 1 ELSE a(i, j) = v: EXIT DO
    NEXT j: NEXT i
  LOOP
LOOP
PRINT "End of run"
END

TestArray:
FOR i = 4 TO 1 STEP -1
  FOR j = 4 TO 1 STEP -1
    PRINT a(i, j);
  NEXT j
NEXT i
PRINT
IF INKEY$ <> "" THEN PRINT Cases; "out of"; MaxCases; "took"; TIMER - StartTime: SYSTEM
RETURN

User avatar
Mentat
Veteran
Posts: 409
Joined: Tue Aug 07, 2007 3:39 pm
Location: NC, US

Post by Mentat » Sun Sep 02, 2007 8:51 pm

Do you have nothing better to do than torture your poor computer?
I guess I'm guilty of it too :) .
For any grievances posted above, I blame whoever is in charge . . .

ThemePark
Coder
Posts: 17
Joined: Wed Aug 22, 2007 6:37 pm

Post by ThemePark » Mon Sep 10, 2007 6:17 pm

Sorry for the delay, but I've spent the last 4 days trying to get my computer back up and running. :(

You make a good point with those programs, Mac, with that long a run time, I think I'm just going to go with Mentat's suggestion and somehow try and recreate the matrix from the rules. Thank you both for your help.

Post Reply