File contents

import random
#html# Licence <a href="http://www.gnu.org/licenses/gpl.txt">GPL see http://www.gnu.org/licenses/gpl.txt</a>
#html# K&oslash;r <a href="http://databassen.dk:8005/">program nu</a> 
"""
Copyright Bauer Data ApS.
   +-------+-------+-------+
   |       |       |       |
   |   1   |   2   |   3   |
   |       |       |       |
   +-------+-------+-------+
   |       |       |       |
   |   4   |   5   |   6   |
   |       |       |       |
   +-------+-------+-------+
   |       |       |       |
   |   7   |   8   |   9   |
   |       |       |       |
   +-------+-------+-------+
     En maengde pr square
   +-------+-------+-------+
   | 1 2 3 | 4 5 6 | 7 8 9 | row 1 = [1,2,3,4,5,6,7,8,9] en maengde pr. raekke
   | 5 2 9 | 8 4 1 | 3 6 7 | row 2 = [1,2,3,4,5,6,7,8,9]
   | 4 1 7 | 6 3 9 | 2 5 8 | row 3 = [1,2,3,4,5,6,7,8,9]
   +-------+-------+-------+
   | 8 4 2 | 5 9 7 | 6 1 3 | row 4 = [1,2,3,4,5,6,7,8,9]
   | 7 3 5 | 4 1 6 | 2 9 8 | row 5 = [1,2,3,4,5,6,7,8,9]
   | 9 6 1 | 8 2 3 | 5 4 7 | row 6 = [1,2,3,4,5,6,7,8,9]
   +-------+-------+-------+
   | 3 6 7 | 2 8 9 | 5 1 4 | row 7 = [1,2,3,4,5,6,7,8,9]
   | 4 8 5 | 6 1 7 | 2 3 9 | row 8 = [1,2,3,4,5,6,7,8,9]
   | 2 9 1 | 5 4 3 | 8 6 7 | row 0 = [1,2,3,4,5,6,7,8,9]
   +-------+-------+-------+
    En maengde pr colonne
     1 1 1   1 1 1   1 1 1
     2 2 2   2 2 2   2 2 2
     3 3 3   3 3 3   3 3 3
     4 4 4   4 4 4   4 4 4
     5 5 5   5 5 5   5 5 5
     6 6 6   6 6 6   6 6 6
     7 7 7   7 7 7   7 7 7
     8 8 8   8 8 8   8 8 8
     9 9 9   9 9 9   9 9 9

   All squares must contain the ciffers 1 through 9

 All rows may contain 1 throug 9
 All columns may contain 1 throug 9

 create a "def square():" who produce at legal square.
"""
sqfields=(
( 0, 1, 2,  9,10,11, 18,19,20 ),
( 3, 4, 5, 12,13,14, 21,22,23 ),
( 6, 7, 8, 15,16,17, 24,25,26 ),
(27,28,29, 36,37,38, 45,46,47 ),
(30,31,32, 39,40,41, 48,49,50 ),
(33,34,35, 42,43,44, 51,52,53 ),
(54,55,56, 63,64,65, 72,73,74 ),
(57,58,59, 66,67,68, 75,76,77 ),
(60,61,62, 69,70,71, 78,79,80 ),
)

class sudoku:
    """returns a random generated sudoku square"""
    def __init__(self,size=9,safe=True,debug=True, file="" ):
        self.debug = debug
        self.sqsize = int(pow(size,0.5))
        self.size = size
        self.squ = {}
        self.row = {}
        self.safe = safe
        self.col = {}
        self.file = file
        self.generate_sudoku()
        if self.safe:
            self.f=open(file,"a")

    def init_sets(self):    
        for i in range(self.size):
            self.squ[i]=[1,2,3,4,5,6,7,8,9]
            self.row[i]=[1,2,3,4,5,6,7,8,9]
            self.col[i]=[1,2,3,4,5,6,7,8,9]
        # square hold size*size fields.
        self.fields={}
        for i in range(self.size*self.size):
            rowno=i/self.size
            colno=i%self.size
            squno=i/self.sqsize%self.sqsize+i/27*3
            data=[self.row[rowno],self.col[colno],self.squ[squno]]
            # print i,rowno,colno,squno,data
            self.fields[i]=data
        self.square=["0"]*self.size*self.size        

    def make_square(self,squareno):
        fields=sqfields[squareno]
        # print squareno,fields
        rollback=True
        rbcount=3
        while rollback:
            rollback=False
            for field in fields:
                # Fetch a random number from col and check if it is in squ and col.
                # if so remove number from row, col and squ set
                # and then place it in square[field]
                row,col,squ=self.fields[field]
                trail=0
                while True:
                    trail+=1
                    number=random.choice(squ)
                    if number in row and number in col:
                        row.remove(number)
                        col.remove(number)
                        squ.remove(number)
                        self.square[field]=str(number)
                        break
                    if trail > 10:
                        break
                if trail > 10:
                    rollback=True
                    break
            if rollback:
                self.rollback(squareno)
                rbcount-=1
                if rbcount == 0:
                    return False
        return True

    def rollback(self,squareno):
        fields=sqfields[squareno]
        if self.debug: print "k%s" % squareno,
        for field in fields:
            number=int(self.square[field])
            if self.debug : print number,
            row,col,squ=self.fields[field]
            if number:
                self.square[field]=0
                row.append(number)
                col.append(number)
                squ.append(number)
        if self.debug : print

    def generate_sudoku(self):
        self.init_sets()    
        sqrnumbers =[0,4,8,3,6,7,1,2,5]
        i=0
        while True:
            if self.make_square(sqrnumbers[i]): i+=1
            else:
                i-=1
                self.rollback(sqrnumbers[i])
            if i >= len(sqrnumbers):
                break
    def save(self):
        self.f.write("".join(self.square))
        self.f.write("\n")

        
    def Print(self):
        if self.safe:
            self.save()
            return
        for i in range(self.size*self.size):
            if i % (self.size*3)==0:
                print"\n+-------+-------+-------+\n|",
            else:
                if i % (self.size)==0:
                    print"\n|",
            print "%s" % self.square[i],
            if i%self.sqsize==2:
                print"|",

        print"\n+-------+-------+-------+"


if __name__=="__main__":
    """Usage: python sudoku.py -f [<file>] [-c <count>]
count: number og squares to produce. Default is 1
file : write solutions to <file>.txt in format

 square 1 field 1
/         square 2 field 1
|        /
|        |        |        |        |        |        |        |        |
274591638139684725856372941523948176697135482418267593785413269941826357362759814
192435687684917325375826194539182746261794538847653912453279861716348259928561473

without <file> option
print legal suduko plates on stdout like this.
+-------+-------+-------+
| 4 7 1 | 3 9 8 | 2 5 6 |
| 8 5 6 | 2 7 1 | 4 9 3 |
| 3 9 2 | 4 5 6 | 7 8 1 |
+-------+-------+-------+
| 2 3 5 | 6 8 7 | 1 4 9 |
| 1 8 7 | 9 2 4 | 3 6 5 |
| 6 4 9 | 1 3 5 | 8 7 2 |
+-------+-------+-------+
| 7 2 3 | 8 6 9 | 5 1 4 |
| 5 6 4 | 7 1 3 | 9 2 8 |
| 9 1 8 | 5 4 2 | 6 3 7 |
+-------+-------+-------+
"""
    debug = False
    import getopt, sys
    try:
        options, arguments = getopt.getopt(sys.argv[1:], "f:c:")
    except getopt.GetoptError:
        print "Wrong arguments?"
        print __doc__
        sys.exit(1)

    file = ""
    count = 1
    safe = False
    for option, argument in options:
        if option == "-f":
            file = argument+".txt"
            safe = True
        elif option == "-c":
            count = int( argument )
        else:
            print "Wrong arguments?"
            print __doc__
            sys.exit(1)

    kvadrat=sudoku( safe=safe, debug=debug, file=file )
    while count > 0:
        kvadrat.generate_sudoku()
        kvadrat.Print()
        count -= 1
        print ".",

    count=0