Python Generate All Possible Configurations Of Numbers On A "board"

I am trying to take an input number of 'filled squares' and generate all possible configurations of those squares on an n by n board (list of lists). Empty squares are denoted 0, f

Solution 1:

You can use combinations to generate the positions of the 0s

>>>from itertools import combinations>>>list(combinations(range(4), 1))
[(0,), (1,), (2,), (3,)]

Just map the numbers 0,1,2,3 onto your 2x2 grid.

A larger example is probably more convincing

>>>list(combinations(range(9), 2))
[(0, 1), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (2, 3), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 4), (3, 5), (3, 6), (3, 7), (3, 8), (4, 5), (4, 6), (4, 7), (4, 8), (5, 6), (5, 7), (5, 8), (6, 7), (6, 8), (7, 8)]

Here's an example mapping to a 2D list

>>> from itertools import product, combinations
>>> n = 3 # 3x3
>>> m = 2 # 2 tents
>>> for i in combinations(range(n*n), m):
...    print[[0 if x*n+y in i else 1 for x in range(n)] for y in range(n)]
... 
[[0, 1, 1], [0, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [0, 1, 1]]
[[0, 0, 1], [1, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 0, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [1, 0, 1]]
[[0, 1, 0], [1, 1, 1], [1, 1, 1]]
[[0, 1, 1], [1, 1, 0], [1, 1, 1]]
[[0, 1, 1], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [0, 1, 1], [0, 1, 1]]
[[1, 0, 1], [0, 1, 1], [1, 1, 1]]
[[1, 1, 1], [0, 0, 1], [1, 1, 1]]
[[1, 1, 1], [0, 1, 1], [1, 0, 1]]
[[1, 1, 0], [0, 1, 1], [1, 1, 1]]
[[1, 1, 1], [0, 1, 0], [1, 1, 1]]
[[1, 1, 1], [0, 1, 1], [1, 1, 0]]
[[1, 0, 1], [1, 1, 1], [0, 1, 1]]
[[1, 1, 1], [1, 0, 1], [0, 1, 1]]
[[1, 1, 1], [1, 1, 1], [0, 0, 1]]
[[1, 1, 0], [1, 1, 1], [0, 1, 1]]
[[1, 1, 1], [1, 1, 0], [0, 1, 1]]
[[1, 1, 1], [1, 1, 1], [0, 1, 0]]
[[1, 0, 1], [1, 0, 1], [1, 1, 1]]
[[1, 0, 1], [1, 1, 1], [1, 0, 1]]
[[1, 0, 0], [1, 1, 1], [1, 1, 1]]
[[1, 0, 1], [1, 1, 0], [1, 1, 1]]
[[1, 0, 1], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [1, 0, 1], [1, 0, 1]]
[[1, 1, 0], [1, 0, 1], [1, 1, 1]]
[[1, 1, 1], [1, 0, 0], [1, 1, 1]]
[[1, 1, 1], [1, 0, 1], [1, 1, 0]]
[[1, 1, 0], [1, 1, 1], [1, 0, 1]]
[[1, 1, 1], [1, 1, 0], [1, 0, 1]]
[[1, 1, 1], [1, 1, 1], [1, 0, 0]]
[[1, 1, 0], [1, 1, 0], [1, 1, 1]]
[[1, 1, 0], [1, 1, 1], [1, 1, 0]]
[[1, 1, 1], [1, 1, 0], [1, 1, 0]]

Solution 2:

So I take it you are not taking into account rotations or reflections. You could take another approach to the problem... how many empty spaces do I have? Lets say we have n. Well, can't we achieve all possible board configurations by finding all possible places we can 'insert' these n empty squares into an entirely filled board? For this we can use the itertools import, and arrange all possible configurations, specifically, as gnibbler has pointed out, combinations.