Randomly generate a 9 × 9 list where the entries are integers between 1 and 9 with no repeat entries in any row or in any column

Question

I wrote a code for :Randomly generate a 9 × 9 list where the entries are integers between 1 and 9 with no repeat entries in any row or in any column.

but my code does not solve the no repeat entry part.

matr=[    ] 
#print(matr)

for i in range(9):
    entry=[ ]
    for j in range(9):
        while len(entry)<9:
            draw=randint(1,9)
            while draw not in entry:    
                entry.append(draw  )
    matr.append(entry   )   
    #print(matr   )
    #print(entry)


for i in matr:
    print(i)

or this code:

print('--------list 1 to 9--------------------------------------')
list=[ i for i in range(1,10) ]
print(list)


print('---------shuffle list-------------------------------------')
matr=[   ] 

entry=list

for i in range(9):
    entry=entry.copy()    
    shuffle(entry ) 
    print(entry )
    matr.append(entry)

print(matr)

Answer 1

Steps

1. Generate a shuffled list
2. Left rotated by 1 to generate the matrix
3. Shuffle rows in matrix
4. Shuffle cols in matrix (optional)

from random import shuffle

a = list(range(10))
shuffle(a)

# Use slicing to left rotate
m = [a[i:] + a[:i] for i in range(10)]

# Shuffle rows in matrix
shuffle(m)

# Shuffle cols in matrix (optional)
m = list(map(list, zip(*m)))  # Transpose the matrix
shuffle(m)

print('\n'.join(map(str, m)))

Answer 2

You're looking to produce a random (valid) sudoku board. This is not trivial and a trial/error approach with random numbers will take forever to produce a valid result. Here's a sudoku generator that will do it using dynamic programming:

import random
groups  = [ p//27*3+p%9//3   for p in range(81) ] 
colNums = [ set(range(1,10)) for _ in range(9)  ] 
rowNums = [ set(range(1,10)) for _ in range(9)  ]
grpNums = [ set(range(1,10)) for _ in range(9)  ]
sudoku  = [ [0]*9 for _ in range(9) ]
pos     = 0
tried   = [ set() for _ in range(81)]
while pos < 81:
    row,col,group  = pos//9,pos%9,groups[pos]
    previousNumber = sudoku[row][col]
    if previousNumber != 0:      # make backtracked number available again
        sudoku[row][col] = 0
        colNums[col].add(previousNumber)
        rowNums[row].add(previousNumber)
        grpNums[group].add(previousNumber)
    available  = colNums[col] & rowNums[row] & grpNums[group]
    available -= tried[pos]
    if available:                # select an available number at random
        number = random.choice(list(available))
        sudoku[row][col] = number
        colNums[col].discard(number)
        rowNums[row].discard(number)
        grpNums[group].discard(number)
        tried[pos].add(number)
        pos += 1
    else:
        tried[pos] = set() # no available number, backtrack to previous position
        pos -= 1

for line in sudoku:
        print(line)

The algorithm attempts to place a number at each of the 81 positions sequentially. If there is a conflict it will try the next available number for that position. If there are no numbers that will fit at that position, then it backtracks to the previous position and tries the next available number there. It will move back and forth through the 81 positions until it manages to place a valid number at the last position.

In order to quickly check if a number is valid at a given position, the algorithm maintains 3 lists of sets. One for the rows, one for the columns and one for the nine 3x3 blocks. These sets contain the unused numbers for a given row, column or block. Each time a number is placed on the board, it is removed from the corresponding row/column/block sets. This makes it unavailable for all subsequent positions that are on the same row, column or block.

When the algorithm needs to backtrack, it returns the number at the previous position to its 3 availability sets. The position to which the algorithm is backtracking will move on to another number so the previously attempted number must become available for subsequent positions.

The positions are numbered from 0 to 80 to facilitate tracking and comparisons in sets. These position numbers can easily be converted to row and column using simple division and modulo operators. The conversion to group numbers is a little bit more complicates but it is also just a matter of division and modulo.

Variables used:

• groups: conversion from a position number to a group number
• colNums: sets of available positions for the 9 columns
• rowNums: sets of available positions for the 9 rows
• grpNums: sets of available positions for the 9 groups (3x3 blocks)
• sudoku: the final board (9 rows of 9 numbers)
• pos: current position where an attempt to place a number is being made
• tried: set of numbers that have already been tried at each position so far. When backtracking the current set is cleared because the availability of positions will be different once the previous position is changed.
• row,col,group are indexes corresponding to the current position (pos)

If you don't want the 3x3 blocks restriction, you can easily remove it by deleting the parts of the code that use/assign the group, groups and grpNums variables.

In that case, there is a much simpler (and faster) technique to produce a random matrix that meets the row/column unicity constraint:

import random
numbers = random.sample(range(1,10),9)
cols    = random.sample(range(9),9)
rows    = random.sample(range(9),9)
square  = [[numbers[(r+c)%9] for c in cols] for r in rows]
for line in square: 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]

Note that this may not produces all of the valid random matrices

To explain this one, it is best to start with a simple matrix of sequential indexes where each row is offset by one more than the preceding row:

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

[0, 1, 2, 3, 4, 5, 6, 7, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 0]
[2, 3, 4, 5, 6, 7, 8, 0, 1]
[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]

As you can see each row has indexes 0 to 8 (so no repetitions) and each column also has indexes 0 to 8 with no repetition because of offsetting.

Now if we create a list of numbers from 1 to 9 and shuffle it, we can replace the indexes in the matrix by the corresponding number in the shuffled list. Since each index maps to a different number, the resulting matrix will not have any repetitions on lines or columns.

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]

Finally we can shuffle the rows to get a more random organization of the matrix

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]

and columns:

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]

The solution (above) combines these steps into a single list comprehension but uses exactly the same approach.

Using the same approach, it is also possible to produce a random sudoku board (with the 3x3 block constraint). The formula for the offsets is a bit more complex and the shuffling of rows and columns can only be done within and between block groups.

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]

Answer 3

If you just need 1 matrix and no variation is expected, then you can keep shifting array to either right or left. Here is an example:

def cyclic_rotate(input):
    return [input[-1]] + input[0:-1]

if __name__ == "__main__":
    result = []
    input = [i for i in range(9)]
    prev = input
    for i in range(9):
        shifted_arr = cyclic_rotate(prev)
        result.append(shifted_arr)
        prev = shifted_arr
    # Does only pretty print of 2-D matrix
    print('\n'.join(['\t'.join([str(cell) for cell in row]) for row in result]))

Answer 4

Try this and you will get what you want:

>>> matrix = []
>>> for i in range(1,10):
...     temp = []
...     for j  in range(i,i+9):
...         if j >= 10:
...             temp.append(int(j%10)+1)
...         else:
...             temp.append(j)
...     matrix.append(temp)
...
>>> matrix
[[1, 2, 3, 4, 5, 6, 7, 8, 9], [2, 3, 4, 5, 6, 7, 8, 9, 1], [3, 4, 5, 6, 7, 8, 9, 1, 2], [4, 5, 6, 7, 8, 9, 1, 2, 3], [5, 6, 7, 8, 9, 1, 2, 3, 4], [6, 7, 8, 9, 1, 2, 3, 4, 5], [7, 8, 9, 1, 2, 3, 4, 5, 6], [8, 9, 1, 2, 3, 4, 5, 6, 7], [9, 1, 2, 3, 4, 5, 6, 7, 8]]

Hope this helps you.