Недостатки и профессионалы smartGWT

Вы можете сохранить список наборов для используемых значений столбцов. Проверка новой «перетасованной» линии может быть проведена более напрямую. То же самое для групп подматриц, хотя вам нужно использовать косвенное направление (или сложный расчет индекса) для сопоставления позиций с наборами групп:

import random

def createMatrix():
    matrix  = []
    numbers = [1,2,3,4,5,6,7,8,9]
    groups  = [ [0,0,0, 1,1,1, 2,2,2] ] * 3
    groups += [ [3,3,3, 4,4,4, 5,5,5] ] * 3
    groups += [ [6,6,6, 7,7,7, 8,8,8] ] * 3
    while len(matrix) < 9:
        matrix    = []
        colSets   = [ set() for _ in range(9) ]
        groupSets = [ set() for _ in range(9) ]
        for row in range(9):
            for _ in range(133496): # try multiple permutations for row (36.79%)
                random.shuffle(numbers)
                if any( n in used for n,used in zip(numbers,colSets) ):
                    continue # column conflict
                if any( n in groupSets[g] for n,g in zip(numbers,groups[row]) ):
                    continue # sub-matrix group conflict
                matrix.append(numbers.copy())
                for n,used in zip(numbers,colSets):     used.add(n)
                for n,g    in zip(numbers,groups[row]): groupSets[g].add(n)
                break
            if len (matrix) == row: break # restart if failed to produce a row
    return matrix

sudoku = createMatrix()
for line in sudoku:
    print(line)

Если вы пытаетесь сгенерировать случайный латинский квадрат, более быстрым методом было бы рандомизировать рабочую базовую линию, а не итеративно проверять достоверность наборов случайных чисел в процессе проб / ошибок:

import random

numbers = random.sample(range(1,10),9)
cols    = random.sample(range(9),9)
rows    = random.sample(range(9),9)
matrix  = [[numbers[(r+c)%9] for c in cols] for r in rows]

for line in matrix: print(line)  

[8, 9, 1, 7, 6, 4, 5, 3, 2]
[5, 2, 9, 6, 4, 3, 1, 8, 7]
[2, 4, 6, 8, 5, 1, 7, 9, 3]
[1, 7, 2, 4, 3, 8, 9, 5, 6]
[7, 3, 4, 5, 1, 9, 6, 2, 8]
[3, 1, 5, 2, 7, 6, 8, 4, 9]
[4, 5, 8, 9, 2, 7, 3, 6, 1]
[9, 6, 7, 3, 8, 5, 2, 1, 4]
[6, 8, 3, 1, 9, 2, 4, 7, 5]

Чтобы объяснить это, лучше начать с простая матрица последовательных индексов, где каждая строка смещена на одну единицу больше, чем предыдущая строка:

matrix = [ [(r+c)%9 for c in range(9)] for r in range(9) ]

[0, 1, 2, 3, 4, 5, 6, 7, 8] # base row
[1, 2, 3, 4, 5, 6, 7, 8, 0] # offset by 1
[2, 3, 4, 5, 6, 7, 8, 0, 1] # offset by 2
[3, 4, 5, 6, 7, 8, 0, 1, 2] # ....
[4, 5, 6, 7, 8, 0, 1, 2, 3]
[5, 6, 7, 8, 0, 1, 2, 3, 4]
[6, 7, 8, 0, 1, 2, 3, 4, 5]
[7, 8, 0, 1, 2, 3, 4, 5, 6]
[8, 0, 1, 2, 3, 4, 5, 6, 7]

Как вы можете видеть, каждая строка имеет индексы от 0 до 8 (поэтому нет повторений), и каждый столбец также имеет индексы 0 до 8 без повторения из-за смещения.

Теперь, если мы создадим список чисел от 1 до 9 и перетасуем его, мы можем заменить индексы в матрице на соответствующие числа в перетасованном списке. Поскольку каждый индекс отображается на другое число, результирующая матрица не будет иметь повторений в строках или столбцах.

numbers = random.sample(range(1,10),9) # [1, 5, 9, 8, 3, 7, 6, 2, 4]
matrix  = [ [numbers[i] for i in row] for row in matrix ]

[1, 5, 9, 8, 3, 7, 6, 2, 4]
[5, 9, 8, 3, 7, 6, 2, 4, 1]
[9, 8, 3, 7, 6, 2, 4, 1, 5]
[8, 3, 7, 6, 2, 4, 1, 5, 9]
[3, 7, 6, 2, 4, 1, 5, 9, 8]
[7, 6, 2, 4, 1, 5, 9, 8, 3]
[6, 2, 4, 1, 5, 9, 8, 3, 7]
[2, 4, 1, 5, 9, 8, 3, 7, 6]
[4, 1, 5, 9, 8, 3, 7, 6, 2]

Наконец, мы можем перетасовать ряды, чтобы получить более случайную организацию матрицы

random.shuffle(matrix)

[5, 9, 8, 3, 7, 6, 2, 4, 1]
[9, 8, 3, 7, 6, 2, 4, 1, 5]
[1, 5, 9, 8, 3, 7, 6, 2, 4]
[7, 6, 2, 4, 1, 5, 9, 8, 3]
[2, 4, 1, 5, 9, 8, 3, 7, 6]
[6, 2, 4, 1, 5, 9, 8, 3, 7]
[4, 1, 5, 9, 8, 3, 7, 6, 2]
[8, 3, 7, 6, 2, 4, 1, 5, 9]
[3, 7, 6, 2, 4, 1, 5, 9, 8]

и столбцов:

cols   = random.sample(range(9),9) # [7, 4, 3, 0, 8, 1, 2, 5, 6]
matrix = [[matrix[r][c] for c in cols] for r in range(9)]

[4, 7, 3, 5, 1, 9, 8, 6, 2]
[1, 6, 7, 9, 5, 8, 3, 2, 4]
[2, 3, 8, 1, 4, 5, 9, 7, 6]
[8, 1, 4, 7, 3, 6, 2, 5, 9]
[7, 9, 5, 2, 6, 4, 1, 8, 3]
[3, 5, 1, 6, 7, 2, 4, 9, 8]
[6, 8, 9, 4, 2, 1, 5, 3, 7]
[5, 2, 6, 8, 9, 3, 7, 4, 1]
[9, 4, 2, 3, 8, 7, 6, 1, 5]

Решение (выше) объединяет эти входит в понимание единого списка, но использует точно такой же подход.

Используя этот подход, также возможно создать случайную доску судоку (с ограничением блока 3х3). Формула для смещений немного сложнее, и перетасовка строк и столбцов может быть выполнена только внутри и между группами блоков, но общий метод остается тем же.

from random import sample
base  = 3  # Will generate any size of random sudoku board instantly
side  = base*base
nums  = sample(range(1,side+1),side) # random numbers
board = [[nums[(base*(r%base)+r//base+c)%side] for c in range(side) ] for r in range(side)]
rowGr = sample(range(base),base) # random rows/horizontal blocks
rows  = [ r for g in rowGr for r in sample(range(g*base,(g+1)*base),base) ] 
colGr = sample(range(base),base) # random column/vertical blocks
cols  = [ c for g in colGr for c in sample(range(g*base,(g+1)*base),base) ]            
board = [[board[r][c] for c in cols] for r in rows]

for line in board:print(line)
[7, 5, 3, 6, 9, 4, 1, 2, 8]
[6, 9, 4, 1, 2, 8, 7, 5, 3]
[1, 2, 8, 7, 5, 3, 6, 9, 4]
[2, 8, 7, 5, 3, 6, 9, 4, 1]
[5, 3, 6, 9, 4, 1, 2, 8, 7]
[9, 4, 1, 2, 8, 7, 5, 3, 6]
[8, 7, 5, 3, 6, 9, 4, 1, 2]
[3, 6, 9, 4, 1, 2, 8, 7, 5]
[4, 1, 2, 8, 7, 5, 3, 6, 9]

Это производит случайное судоку 9x9 за 0,2 миллисекунды по сравнению с методом проб / ошибок, который занимает от 1 до 20 секунд (очень случайное время)

Как и метод латинского квадрата это основано на действительной базовой плате, составленной из индексов с соответствующими ограничениями на строки, столбцы и блоки:

base  = 3
side  = base*base
board = [[(base*(r%base)+r//base+c)%side for c in range(side)] for r in range(side)]

for line in board: print(line)

[0, 1, 2, 3, 4, 5, 6, 7, 8] # base row
[3, 4, 5, 6, 7, 8, 0, 1, 2] # offset by 3
[6, 7, 8, 0, 1, 2, 3, 4, 5] # offset by 6
[1, 2, 3, 4, 5, 6, 7, 8, 0] # offset by 1
[4, 5, 6, 7, 8, 0, 1, 2, 3] # offset by 4
[7, 8, 0, 1, 2, 3, 4, 5, 6] # offset by 7
[2, 3, 4, 5, 6, 7, 8, 0, 1] # offset by 2
[5, 6, 7, 8, 0, 1, 2, 3, 4] # offset by 5
[8, 0, 1, 2, 3, 4, 5, 6, 7] # offset by 8

Остальное - просто замена индексов перемешанными числами и перемешивание столбцов и блоков строк .