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

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 :)

CodePudding user response：

I think you're looking for something like this –

generate_base returns a "base grid" of rows where numbers 1...N are "shifted" for N rows (so e.g. 1,2,3, 2,3,1, 3,1,2)
generate calls that function and itertools.permutations() to generate the possible "vertical" permutations of the base grid (i.e. it shuffles the rows around)

import itertools


def generate_base(n):
    return [tuple(((i   x) % n)   1 for x in range(n)) for i in range(n)]


def generate(n):
    return itertools.permutations(generate_base(n))


for grid in generate(4):
    print(grid)

The output for 4 is e.g.

((1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3))
((1, 2, 3, 4), (2, 3, 4, 1), (4, 1, 2, 3), (3, 4, 1, 2))
((1, 2, 3, 4), (3, 4, 1, 2), (2, 3, 4, 1), (4, 1, 2, 3))
((1, 2, 3, 4), (3, 4, 1, 2), (4, 1, 2, 3), (2, 3, 4, 1))
((1, 2, 3, 4), (4, 1, 2, 3), (2, 3, 4, 1), (3, 4, 1, 2))
...

CodePudding user response：

I think I found a solution, is this what you're looking for?

def generate(n):
        #combinations :
        liste = list(itertools. product( list(range(1,n 1)), repeat=n)) 
        liste = list(map(list, liste))
        #combinations of the combinations :
        result =  list(itertools. product(liste, repeat=n))
        return (list(map(list, result)))

CodePudding user response：

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.