Генератор судоку методом открытий

# sudoku.py

# Robert Wohleb

# 20051115

import random

class board:

boardlist = []

partialboardlist = []

def generate(self, numFilled=(9*9)):

slots = []

fillOrder = []

random.seed()

# setup board

row = [0,0,0,0,0,0,0,0,0]

for i in range(0, 9):

self.boardlist.append(row[:])

for j in range(0, 9):

for i in range(0, 9):

slots.append((i,j))

self.search(slots, 0)

while len(slots) > 0:

i = random.randint(0, len(slots)-1)

fillOrder.append(slots[i])

del slots[i]

# setup board

for i in range(0, 9):

self.partialboardlist.append(row[:])

for i in range(0, numFilled):

j = fillOrder[i]

self.partialboardlist[j[0]][j[1]] = self.boardlist[j[0]][j[1]]

def search(self, slots, index):

nums = []

fillOrder = []

if len(slots) == index:

return self.check()

for i in range(1, 10):

nums.append(i)

while len(nums) > 0:

i = random.randint(0, len(nums)-1)

fillOrder.append(nums[i])

del nums[i]

for i in fillOrder:

x = slots[index][0]

y = slots[index][1]

self.boardlist[x][y] = i

#print

#print x, y, i

#self.printBoard()

if (self.check()):

if self.search(slots, index+1):

return True

self.boardlist[x][y] = 0

return False

def check(self):

for i in range(0, 9):

if (not self.checkRow(i)) or (not self.checkCol(i)) or (not self.checkSquare(i)):

return False

return True

def checkRow(self, row):

found = []

for i in range(0, 9):

if not self.boardlist[i][row] == 0:

if self.boardlist[i][row] in found:

#print 'checkRow', i, row, self.boardlist[i][row]

return False

found.append(self.boardlist[i][row])

return True

def checkCol(self, col):

found = []

for j in range(0, 9):

if not self.boardlist[col][j] == 0:

if self.boardlist[col][j] in found:

#print 'checkCol', j, col, self.boardlist[col][j]

return False

found.append(self.boardlist[col][j])

return True

def checkSquare(self, square):

found = []

xoffset = (3*(square % 3))

yoffset = int(square / 3) * 3

#print 'checkSquare(', xoffset, yoffset, ')'

for j in range(0, 3):

for i in range(0, 3):

if not self.boardlist[xoffset+i][yoffset+j] == 0:

if self.boardlist[xoffset+i][yoffset+j] in found:

#print 'checkSquare -- ', i, j, self.boardlist[xoffset+i][yoffset+j]

return False

found.append(self.boardlist[xoffset+i][yoffset+j])

return True

def getList(self): # setup board

row = [0,0,0,0,0,0,0,0,0]

for i in range(0, 9):

self.boardlist.append(row[:])

return self.boardlist

def printBoard(self):

for j in range(0, 9):

for i in range(0, 9):

if self.boardlist[i][j] == 0:

print '.',

else:

print self.boardlist[i][j],

print

def printPartialBoard(self):

for j in range(0, 9):

for i in range(0, 9):

if self.partialboardlist[i][j] == 0:

print '.',

else:

print self.partialboardlist[i][j],

print

def getBoard(self):

data = []

for j in range(0, 9):

data.append([])

for i in range(0, 9):

data[j].append(self.boardlist[i][j])

return data

def getPartialBoard(self):

data = []

for j in range(0, 9):

data.append([])

for i in range(0, 9):

data[j].append(self.partialboardlist[i][j])

return data