Order independent weighted random selection

Say I have a pool of items to be randomly selected.

And I use a simple weighted selection algorithm to do so:

1. Calculate item weight sum;
2. Pick a random number between 0 and weight sum;
3. Iterate over items, and decrease by item weight, select item when <0

And in the meantime, a constraint propagation algorithm updates the pool of available items.

• For example, say we have a N by N grid, each cell can select a number.
• The selection is done through weighted selection, using algorithm above.
• Once a cell selects its number, it also limits neighbouring cells' available numbers using some rules.

And here is my problem:

• Say cell A and B are neighbours.
• Say initially, both of them can select from a pool of numbers.
• But once A or B is determined, the other cell will have less number to choose from.
• Thus, even for the same random number input, the weighted selection can still yield different result (because weight sum and item probability has changed).
• So the selection process is not order-independent, even if the random number is order-independent.

How can we ensure outcome of A and B are random and independent, while still being able to propagate constraints? (Is it even possible in my case?)