How to generate all possibilities of sudoku-like grids in Python?

I need to generate all the possibilities of sudoku-like grids/matrices. A list of 2D arrays must be returned.

Note: What I am trying to generate is not really a 9x9 sudoku grid but something like the grid below, where the only condition is that there are no repeated numbers in the rows and columns:

1 2 3
2 3 1
3 1 2

So, for example,

>> generate(3)
[[[1,2,3],[2,3,1],[3,1,2]], [[1,2,3],[3,1,2],[2,3,1]], [[1,3,2],[2,1,3],[3,2,1]], [[1,3,2],[3,2,1],[2,1,3]], ...]
>> generate(4)
[[[1,2,3,4],[2,1,4,3],[3,4,1,2],[4,3,2,1]], ...]

Any help would be appreciated :)

Solution

Here is a naive algorithm that finds all the different possible sudoku boards of a given size. It works by iterating through the Cartesian product of the permutations of the digits with as many repetitions as there are rows, and then discarding any that have columns with any repetition of digits.

import itertools

def are_columns_unique(board):
    columns = [set() for _ in range(len(board))]
    for row in board:
        for i, value in enumerate(row):
            column = columns[i]
            if value in column:
                return False
            else:
                column.add(value)
    return True

def generate_boards(n):
    digits = tuple(range(1, n + 1))
    for board in itertools.product(itertools.permutations(digits), repeat=n):
        if are_columns_unique(board):
            yield board

def format_board(board):
    return "\n".join("".join(map(str, row)) for row in board)

for board in generate_boards(3):
    print(format_board(board))
    print()

This outputs the following:

It should be possible to make a more efficient algorithm by detecting duplicate columns while still generating the board, but this is a start.

Edit on 2022-09-10: I wrote a more efficient algorithm. This one can print all sudoku boards of length 5 in a couple of minutes, whereas the naive algorithm above would churn for ages before printing even a single board.

"""
usage: python sudoku.py [-h] n

Print all sudoku-like boards of a given size

positional arguments:
  n           The size of the sudoku-like board

optional arguments:
  -h, --help  show this help message and exit
"""

import argparse
import itertools


def dont_skip(current_result):
    return -1


def product(*args, repeat=1, skip=dont_skip):
    """Find the Cartesian product of the arguments.

    This is the same as itertools.product, with the addition of the skip
    argument.

    The skip argument is a function to specify whether the current result
    should be skipped, and if so, which iterator the next value should come
    from. It should be a function that takes the result of one iteration, and
    returns the index of the iterator to skip, or -1 if the result should not
    be skipped.

    Iterators earlier in the argument list have higher priority than iterators
    later in the argument list; skipping a value from an earlier iterator will
    skip all products of later iterators that would have included that value.
    """
    # Initialize data structures and handle bad input
    if len(args) == 0:
        return []
    gears = [tuple(arg) for arg in args] * repeat
    for gear in gears:
        if len(gear) == 0:
            return []
    tooth_numbers = [0] * len(gears)
    result = [gear[0] for gear in gears]

    # Rotate through all gears
    finished = False
    while not finished:
        current_result = tuple(result)
        gear_to_skip = skip(current_result)
        if gear_to_skip >= 0:
            gear_number = gear_to_skip
        else:
            yield current_result
            gear_number = len(gears) - 1

        # Get next result
        while gear_number >= 0:
            gear = gears[gear_number]
            tooth_number = tooth_numbers[gear_number] + 1
            if tooth_number < len(gear):
                # No gear change is necessary, so exit the loop
                result[gear_number] = gear[tooth_number]
                tooth_numbers[gear_number] = tooth_number
                break
            result[gear_number] = gear[0]
            tooth_numbers[gear_number] = 0
            gear_number -= 1
        else:
            # We changed all the gears, so we are back at the beginning
            finished = True


def skip_duplicate_columns(board):
    columns = [set() for _ in range(len(board))]
    for i, row in enumerate(board):
        for j, value in enumerate(row):
            column = columns[j]
            if value in column:
                return i
            else:
                column.add(value)
    return -1


def generate_boards(n):
    digits = tuple(range(1, n + 1))
    for board in product(
        itertools.permutations(digits), repeat=n, skip=skip_duplicate_columns
    ):
        yield board


def format_board(board):
    return "\n".join("".join(map(str, row)) for row in board)


def parse_args():
    parser = argparse.ArgumentParser(
        description="Print all sudoku-like boards of a given size"
    )
    parser.add_argument("n", type=int, help="The size of the sudoku-like board")
    return parser.parse_args()


def main():
    args = parse_args()
    for board in generate_boards(args.n):
        print(format_board(board))
        print()


if __name__ == "__main__":
    main()

This uses my own code for generating the Cartesian product of the arguments, instead of itertools.product. My code is based on the algorithm from PyPy, which is released under the MIT licence. My adapted code introduces a skip argument, which allows callers to skip unnecessary iterations. This reduces the number of necessary calculations considerably.