[Community Puzzle] Minesweeper level generator

Maybe statements should show more numbers for sample generation. That helps with overflow bugs check.

2 Likes

I’m getting the same values, 4-4, 2-5 then 4-2, 1-4 and so on. Maybe I’m missing something basic but could you explain how 4-4 is occupied?

Hello all,
I’m trying to make this challenge but my mines don’t get same position that example and i don’t know why.
First mines get is number 7 and last is 1, x is for the start of player :
. 7 . . 1 .
. . . . 2 .
. . . . . .
. . . x . 5
. 6 . . . .
. . 4 . 3 .
To generate mines, I reroll this until I have a valid position.
while (minesRemaining > 0) {
int x1 = nextValue(width);
int y1 = nextValue(height); }
My problem is here but how to generate position if it’s not that…
Thank you for helping me in advance :slight_smile:

@Lycast I think I had this result first as well, before I noticed that my calculation of the next 32-bit value of the RNG was not correct. I had an intermediate value that went beyond the 32-bit range. Maybe that helps?

Hello @MarcoT,
Thank you and yes I think that was it.
I am looking in JAVA how to respect this calculation.
Have a good day

unsigned int PRNG(unsigned int s){
return (214013 * s+ 2531011 / 65536);
}
does not give the correct numbers

PRNG(31) = 642077
Something is wrong, anyone has an idea ?

Maybe an overflow, try with unsigned long long.

@Razovsky The right parenthesis is misplaced, it should be (214013*s + 2531011) / 65536 (or equivalently >> 16).

Right, i’m dumb, thanks, i fixed it… I’m ashamed, blocked 2 hours by this, lol

I can’t have the same mine positions as in the testcases. The first mines are correct, but then they’re completely different, except for testcases “corner selection” and “beginner level”.
I generate numbers with this python code : RD = ((214013*RD+2531011)%2**32)//65536

[Community Puzzle] Minesweeper level generator - #21 by Niako may help you

I’m currently successful for all test cases except the expert level.

When placing mine # 77 it tries to place it at (x: 15, y: 7).
Which is wrong according to the example.

Even though I’ve magic-ed up the PRNG for uint32s (and it seems to work for all but the biggest test case), something still fails…

I’m using TypeScript. (Yes, not ideal for floats… I could choose a different language, but where’s the fun in that…)

function prng(seed: number): number {
    return Math.floor(((214013 * seed + 2531011) % 2**32) / 65536);
}

For every time I try to place a mine, the PRNG is called twice (with obviously the ‘previous’ result as seed).
If the result (x, y) is out of bounds, or it falls on a mine and/or starting 3x3, I just continue, ignoring BOTH previous results.

Someone has any ideas where to continue looking?

Hi,

(x: 15, y: 7) are the good values the PRNG should get you when you try to place the #77, it can’t be placed there because the coordinates of the first selected cell is (x: 15, y: 8).

First thought was “no that can’t be, that code works… It’s tested in the other test cases…”
Well, of course there is 4 directions this could ‘fail’ in…

Thanks for pointing me in the right direction!

y >= yStart - 1 && 
y <= yStart + 1 && 
x >= xStart - 1 && 
x <= yStart + 1    // <--
1 Like

Hello,
I made a code that work for the 5 first case but not the expert case.
I can’t seem to find the issue.
I get the error : free(): invalid pointer

Thanks

For the First test : mines = 7
i >= 0
row = R(2 * i + 1) mod Height
col = R(2 * i + 2) mod Width

  1. for i = 0 : row: 0, col : 1

  2. for i = 1 : row: 4, col : 1

  3. for i = 2 : row: 3, col : 5

  4. for i = 3 : row: 4, col : 2
    Rejected (The 3x3 cells square centered on the cell (y,x) is always set free of mines.)

  5. for i = 4 : row: 0, col : 4

  6. for i = 5 : row: 2, col : 2
    Rejected (The 3x3 cells square centered on the cell (y,x) is always set free of mines.)

  7. for i = 6 : row: 4, col : 3
    Rejected (The 3x3 cells square centered on the cell (y,x) is always set free of mines.)

  8. for i = 7 : row: 4, col : 4
    Rejected (The 3x3 cells square centered on the cell (y,x) is always set free of mines.)

  9. for i = 8 : row: 4, col : 1
    Rejected (This sell have already a mine )

  10. for i = 9 : row: 2, col : 2
    Rejected (The 3x3 cells square centered on the cell (y,x) is always set free of mines.)

  11. for i = 10 : row: 2, col : 0

  12. for i = 11 : row: 0, col : 3

  13. for i = 12 : row: 4, col : 0

after collecting 7 Mines we stop generating them

I’m working in C#, and have been struggling with this all day, trying to create a list of random numbers.
Can someone give me a hint, or point me to a good YouTube video that will help me understand.

public static void PopulateRandos(int seed)
{
    Randos.Add(seed);
    for (int i = 1 ; i < 100; i++)
    {
        int prev = Randos[i-1];
        double temp = 214013 * prev + 2531011;
        temp = temp % Math.Pow(2,32);
        temp = temp / 65536;
        temp = Math.Abs(temp);
        Randos.Add((int)temp);
    }
}

I think it’s the part about “All calculations must be in 32-bit unsigned numbers” that is confusing me.

An unsigned integer has a limited range which does not allow big numbers.

I tried your proposition vs an unsigned int working solution. Through the calcul, using the seed from test 1, i see that when my unsigned int seed gets reduced, your double continues to grow.
For example, using R(n) = (214013 * R(n-1) + 2531011) / 65536, R(57855) should be 57896 with R(n-1) and R(n) being unsigned int.

What i suppose is that the variable size limitation can occur at different steps of the calculation:

  • when you multiply the seed by 214013
  • when you add 2531011

I suppose that in most cases, variable type unsigned int limits at the first step of the calcul, which is the multiplication, and not the addition as you seem to consider in your code. However, you can’t be sure of that. Which makes your way of doing more complicated.
And as unsigned int is, well, unsigned, the “abs()” function of a double (signed variable) can’t give you a right answer (supposing you got the right “temp” value until there).

I would suggest you two things:

  • either you use unsigned int variables, which would simplify your problem because you just have to write R(n) = (214013 * R(n-1) + 2531011) / 65536 without adding anything
  • or you keep it your way, however i would suggest some changes :
    First use an unsigned variable type and remove this abs() step, which will not give anything right anyway
    Then try to use the modulus operator % pow(2,32) after the multiplication, then add 2531011 and re-use the modulus, to be sure. But i can’t tell you if this will work.

Hope i helped you, don’t hesitate to ask more questions.
Note: I work in C++ so i don’t know if what i say is similar in C#, specially variable types definition.

1 Like

I guess C# is similar to Java that it has no unsigned int types.

(1)
You can use int or long, but never float or double when you have to deal with integers.
I would use long.

(2)
value of Math.Pow(2,32) can be defined as a constant
Why re-calculate it 100 times in a tight loop?

(3) abs()
unsigned type does not have negative values anyway. Meaningless to abs it

Razovsky and java_coffee_cup —Thanks for the replys.

Leaving some notes for future players:
It turns out I needed to learn more about “unsigned integers”, and that that type is “uint” in C#. (I have some gaps in my knowledge, it seems)

All the suggestions in the forum about “mod 2**32” don’t seem to apply at all to C#, as far as I can tell.

Finally, it works. Great educational puzzle; Minesweeper is complete :slight_smile:

1 Like