END OF AN ERA, FRACTALFORUMS.COM IS CONTINUED ON FRACTALFORUMS.ORG

Hi

I wrote a BBC BASIC program to generate UK style 90 number bingo tickets.

For those of you who don't know what these look like, here's a description.

On one page are 6 grids, one above the next with a gap between.  Each grid is 9 cells wide by 3 cells deep.

The numbers 1 to 90 are used once only.  In the first column are the numbers 1 to 9, the second column has numbers 10 to 19, etc, all the way to the 9th column which has numbers 80 to 90 in it.

Now there are some constraints, and these are the bit where it becomes almost impossible to fill the grid in one pass without having to swap some cells or starting again.

I've tried to draw up some grids with a pen and paper and fill them manually but it gets quite difficult near the end.

The constraints are:

1) Every row must have exactly 5 numbers in it.
2) The 3 cell high column in each ticket must have between 1-3 numbers in it but never zero numbers.
3) In each 3 cell high column, the numbers are sorted with lower numbers higher than larger numbers.
4) All the numbers 1 to 90 are used only once in each set of 6 tickets.

The method I have tried is as follows:

1) Loop 9 times through:
2) Pick a column randomly that hasn't been completed already.
3) Fill random positions in the whole set of 6 tickets within that column with the numbers that are in that column, checking that there are not already 5 numbers in that row.
4) After placing all numbers, check there are no tickets with zero numbers in that column.
5) A few other space checks
6) If there are any errors we delete the numbers placed and go back to step 3.
7) Mark column as completed.
Until all columns are completed.

This is quite quick, but is using a brute force approach to achieve the goal. I'd like to re-think the algorithm to make sure it is guaranteed that it completes first time every time without having to erase numbers and try again, but I just can't think how this would be achieved.

Anyone fancy a non-fractal related challenge of trying to do better.  It doesn't need to be written in BASIC, essentially any language is fair game.

I have a suspicion that even APL would have been able to do this, but I have only ever scratched the surface of examining this language.

Simon

Wound up working on this same problem and didn't see any decent solutions online.  Posting the one I came up with for posterity:

the algorithm is split into 2 parts.

First, generate 6 valid sets of 15 numbers
Second, distribute a set of 15 numbers into a card.


for the first part:

1) assign one number from each of the 9 columns into each of the 6 cards.
after that, you'll have 3 numbers left in the first column, 5 in the last column, and 4 in every other column.

2) assign one of the numbers in the last column to a random card.

3) now make 4 passes over the remaining columns.  In each pass, assign 1 of the remaining numbers for that column to a random card, skipping cards that are already full or have 3 numbers from that column.
  In the first three passes, I'm maxing out at 2 numbers per column instead of 3.  This prevents it from running into a corner case where it can't finish successfully, but reduces the chance of having a full column.

This satisfies the below requirements:
1) at least 1 number in each column on each card
2) at most 3 numbers in each column on each card
3) 15 numbers per card
4) all 90 numbers are used


part two of the algorithm is to distribute a valid set of 15 numbers to a card.

I do this in three passes.  on each pass, I construct one row.
First I check for a column that has to fit (3 numbers left on 1st row, 2 left on 2nd row, 1 left on last row).
Then I just fill the card randomly from the remaining numbers (checking to make sure I'm not repeating a column)