1

I am trying to enumerate the number of valid sudokus of a given size. I have a function that takes a sudoku transformed into a list as input and checks to see if it is a valid sudoku or not. My original method was just to write nested for loops to check every single combination of a list. For a 2 x 2 sudoku, my code looks something like this:

def enumerate2x2():

cnt = 0

for i1 in range(1,3):
    for i2 in range(1,3):
        for i3 in range(1,3):
            for i4 in range(1,3):
                if checkValidSudoku([i1, i2, i3, i4]):
                    cnt += 1

print(cnt)

This code just generates every possible combination of a 4-element list (that's how many squares are in a 2x2 sudoku) with each element in the list being either a 1 or a 2. It then checks each combination.

However, when trying this on a 5x5 sudoku i ran into a problem as python only allows you to have 20 nested loops, so I want to generalize this ugly method into something that will work with any size sudoku. Any help would be appreciated.

andreagalle
  • 620
  • 6
  • 17
wavepapi
  • 13
  • 3
  • This sounds like a code golf problem – Strawberry Jun 30 '20 at 09:23
  • Does this answer your question? [Combinations with repetition in python, where order MATTERS](https://stackoverflow.com/questions/35822627/combinations-with-repetition-in-python-where-order-matters) – andreagalle Jun 30 '20 at 10:28

1 Answers1

0

The Python product intrinsic function, just importing the itertools module, is what you need:

import itertools

sudoku = list(itertools.product(range(1,3), repeat=4))

for x in range(len(sudoku)):
     print sudoku[x]

that simply calculate all the cartesian products, you were looking for, here below the output:

(1, 1, 1, 1)
(1, 1, 1, 2)
(1, 1, 2, 1)
(1, 1, 2, 2)
(1, 2, 1, 1)
(1, 2, 1, 2)
(1, 2, 2, 1)
(1, 2, 2, 2)
(2, 1, 1, 1)
(2, 1, 1, 2)
(2, 1, 2, 1)
(2, 1, 2, 2)
(2, 2, 1, 1)
(2, 2, 1, 2)
(2, 2, 2, 1)
(2, 2, 2, 2)

it seems no combination is now missing, isn't it? Have a look at this other question Combinations with repetition in python, where order MATTERS for more details on alternative implementation too.

andreagalle
  • 620
  • 6
  • 17
  • 1
    The "combinations" function omits many combinations. For example, for a 2x2 sudoku, it returned [1,1,1,1]; [1,1,1,2]; [1,1,2,2]; [1,2,2,2]; and [2,2,2,2], but failed to return such combinations as [1,1,2,1] and [2,2,1,1], for example. – wavepapi Jun 30 '20 at 09:46
  • You are right, thus it seems you need then the [`permutations`](https://docs.python.org/3.1/library/itertools.html?highlight=combinations#itertools.permutations) function, but discarding those results that are then repeated. Actually there is the [`product`](https://docs.python.org/3.1/library/itertools.html?highlight=combinations#itertools.product) function that does it for you, all at once. That is the *cartesian product*. – andreagalle Jun 30 '20 at 09:56
  • I just updated the answer, that now works for me, look if you can **accept** this answer to solve your problem...I also added an additional tag (`itertools`) to your question ;) – andreagalle Jun 30 '20 at 10:26
  • Wonderful @wavepapi, thus, could you **upvote** my answer **and accept** it? (green tick ✅ below upvote button). Many thanks and enjoy SO! – andreagalle Jun 30 '20 at 11:01
  • I upvoted it, but apparently I have to have 15 reputation for it to appear on the post. – wavepapi Jun 30 '20 at 11:10
  • Oh right...you will very soon @wavepapi! Anyway you can even earn couple points reputation now, by submitting any (even small/typographical) edit to my answer. Have a great day/sudoku! – andreagalle Jun 30 '20 at 11:18