from random import *

class Sudoku_Topology_Generate(
    ):
    
    ##!
    ##! Generates randomized sudoku.
    ##!
    
    def Topology_Generate(self,iteration):
        self.Topology_Generate_Full(iteration)
        
        removed=True
        while (removed):
            iteration+=1
            removed=self.Topology_Unique_Remove_One(topology)
            
            print self.XML_Print([
                self.H(3,"Remove "+str(iteration)),           
                self.Topology_Form(
                    self.Topology_Initial(),
                    iteration
                ),
                "Consistency:"+str(self.Consistency())
            ])
    ##!
    ##! Generates randomized sudoku.
    ##!
    
    def Topology_Generate_Full(self,iteration):
        box=[
            [1,2,3,],
            [4,5,6,],
            [7,8,9],
        ]

        self.S=[]
        self.Given=[]
        for r in range(self.M):
            self.S.append([])
            self.Given.append([])
            for s in range(self.M):
                self.S[r].append(0)
                self.Given[r].append([])

        r0=0
        self.Topology_Put_Rows(r0,box)

        rbox=self.Matrix_Rotate_Columns(box)
        r0+=len(box)
        self.Topology_Put_Rows(r0,rbox)
       
        rbox=self.Matrix_Rotate_Columns(rbox)
        r0+=len(box)
        self.Topology_Put_Rows(r0,rbox)

        topology=self.Topology_Initial()
        print self.XML_Print([
            self.H(3,"Generate"),           
            self.Topology_Form(
                self.Topology_Initial(),
                iteration
            ),
            "Consistency:"+str(self.Consistency())
        ])
        
        iteration+=1
        perm=self.Permutation_Randoms(self.N)
        self.S=self.Matrix_Permute_Elements(self.S,perm)

        print self.XML_Print([
            self.H(3,"Elements Permuted"+str(perm)),           
            self.Topology_Form(
                self.Topology_Initial(),
                iteration
            ),
            "Consistency:"+str(self.Consistency())
        ])
        
        iteration+=1
        perm=self.Permutation_Randoms(self.N)
        self.S=self.Matrix_Permute_Rows(self.S,perm)

        print self.XML_Print([
            self.H(3,"Rows Permuted: "+str(perm)),           
            self.Topology_Form(
                self.Topology_Initial(),
                iteration
            ),
            "Consistency:"+str(self.Consistency())
        ])
        
        iteration+=1
        perm=self.Permutation_Randoms(self.N)

        self.S=self.Matrix_Permute_Columns(self.S,perm)

        print self.XML_Print([
            self.H(3,"Columns Permuted: "+str(perm)),           
            self.Topology_Form(
                self.Topology_Initial(),
                iteration
            ),
            "Consistency:"+str(self.Consistency())
        ])

        
    def Topology_Put_Rows(self,r0,box):
        s0=0
        self.Topology_Put(r0,s0,box)

        rbox=self.Matrix_Rotate_Rows(box)
        s0+=len(box)
        self.Topology_Put(r0,s0,rbox)
        
        rbox=self.Matrix_Rotate_Rows(rbox)
        s0+=len(box)
        self.Topology_Put(r0,s0,rbox)

        
    def Permutation_Randoms(self,n):
        start=0
        end=n

        perm=[]
        for m in range(n):
            perm=perm+self.Permutation_Random(start,end)
            start+=n
            end+=n

        return perm
            
    def Permutation_Random(self,start,end):
        pset=set()
        perm=[]
        for i in range(start,end):
            rand=randrange(start,end)
            while (rand in pset):
                rand=randrange(start,end)

            if (not rand in pset):
                perm.append(rand)
                pset.add(rand)

        return perm

        
        
    def Topology_Put(self,r0,s0,box):
        for r in range(len(box)):
            for s in  range(len(box[r])):
                 self.S[r0+r][s0+s]=box[r][s]
                 self.Given[r0+r][s0+s]=box[r][s]

    def Matrix_Permute_Elements(self,box,perm):
        rbox=self.Matrix_Zero(box)
        
        for r in range(len(box)):
            for s in range(len(box)):
                value=perm[box[r][s]-1]
                rbox[r][s]=value+1

        return rbox
                
    def Matrix_Zero(self,box):
        rbox=[]
        for r in range(len(box)):
            rbox.append([]);
            for s in range(len(box[0])):
                rbox[r].append(0);

        return rbox
                
    def Matrix_Permute_Rows(self,box,perm):
        rbox=self.Matrix_Zero(box)
        
        for r in range(len(box)):
            rr=perm[r]
            for s in range(len(box[0])):
                tmp=rbox[rr][s]
                rbox[rr][s]=box[r][s]
                box[r][s]=tmp
                
        return rbox
    
    def Matrix_Permute_Columns(self,box,perm):
        rbox=self.Matrix_Zero(box)

        for s in range(len(box[0])):
            ss=perm[s]
            for r in range(len(box)):
                tmp=rbox[r][ss]
                rbox[r][ss]=box[r][s]
                box[r][s]=tmp
                
        return rbox
    
        
    def Matrix_Rotate_Rows(self,box):
        rbox=[box[ len(box)-1 ]]
        for n in range(len(box)-1):
            rbox.append(box[n])

        return rbox
    
    def Matrix_Transpose(self,box):
        rbox=[]
        for n in range(len(box[0])):
            rbox.append([])

        for n in range(len(box[0])):
            for m in range(len(box[0])):
                rbox[m].append(box[n][m])

        
        return rbox
        
    def Matrix_Rotate_Columns(self,box):
        rbox=self.Matrix_Transpose(box)
        rbox=self.Matrix_Rotate_Rows(rbox)
        rbox=self.Matrix_Transpose(rbox)

        return rbox