Python: Finding all 6x6 matrices where each value occurs only once in each column and row

user_13686298 0
Viewed 100

I want to generate all 6x6 matrices in Python where each value (integer 1-6) occurs only once in each column and row (like a sudoku puzzle, except for the subgrids). Generating all possible 6x6 matrices and filtering afterwards is not an option I believe as there are ~1.3*10^17 possibilities.

I found that when picking a permutation of the sequence 1-6 (720 in total), the 2nd row for the matrix will only have 265 possibilities, with 3rd-4th-5th row having even less. 6th row should have only 1 possibility if the previous 5 rows have been picked.

I have tried the code below for a 3x3 matrix and it works, however I feel adding more nested loops with more comparisons is not the best way (if a way at all) to tackle this issue. It sounds like it should be doable with a recursion or list comprehension but I can't lay my finger on it. 

import itertools


input_list = []

for f in itertools.permutations([1,2,3],3):
  input_list.append(f)




for i in input_list:

  input_listcopy = input_list.copy()
  result = []
  result.append(i)
  input_listcopy.remove(i)

  for j in input_listcopy:
    if (i[0] != j[0] and i[1] != j[1] and i[2] != j[2]):
      result.append(j)



 print(result)

Just to be clear, the output I expect is a 2D list where each element is one row of the matrix, starting from the top:

[[1,2,3],[2,3,1],[3,1,2]]

Thanks in advance!

matrix python
1 Answers

What about this?

from itertools import permutations

# Define the permutations
length = 6
elements = range(1, length+1)

result = []

for perm in permutations(elements, length):
  if not result:  #  The first permutation is added
    result.append(perm)
    continue 

  is_valid_list = []
  for row in result:
    is_valid = all(perm[idx] != row[idx] for idx in range(length))
    is_valid_list.append(is_valid)

  if all(is_valid_list):
    result.append(perm)

print(result)
user_106687690
Related