from functools import reduce;

#------------------------------------------------------------------------------#

def printSolutions(solutions):
   print('*'*26);
   for sol in solutions:
       ix=1;
       for cell in sol:
           print(cell[1][0],end='  ');
           if ix==9:
               print('');
               ix=1;
           else: ix+=1;
       # end for
       print('*'*26);
   # end for
# end def

#------------------------------------------------------------------------------#

Range9=range(1,10);
allCells=[(i,k) for i in Range9 for k in Range9];

def getIntialList(inputList): # No test of input data!
   problemList=[(cell,nb)
                for (cell,nb) in zip(allCells,inputList)
                if nb>0];
   initialList=[((i,k),list(Range9))
                for i in Range9
                for k in Range9];
   return [reduce(adjustCell,problemList,sp)
           for sp in initialList];

def adjustCell(sp,pp):
   def areBlocked(a,b): return (a-1)//3==(b-1)//3;
   ((i,k),val)=pp;
   ((m,n),vList)=sp;
   if (i,k)==(m,n): return ((m,n),[val]);
   elif ((i==m) or (k==n) or
         (areBlocked(i,m) and areBlocked(k,n))):
       return ((m,n),[v for v in vList if v!=val]);
   else: return sp;

def adjustCells(sol,pp):
   return [adjustCell(sp,pp) for sp in sol];

def generateAll(solutionsList,cell):
   return [adjustCells(sol,(cell,val))
               for sol in solutionsList
               for val in dict(sol)[cell]];

def solveSudoku(inputList):
   return reduce(generateAll,allCells,
                 [getIntialList(inputList)]);

#------------------------------------------------------------------------------#
#------------------------------------------------------------------------------#
if __name__ == '__main__':
   print('\n# Beginning Test ...\n');
#------------------------------------------------------------------------------#
   
   #           1  2  3  4  5  6  7  8  9
   inputList =[0, 5, 0, 0, 6, 0, 0, 0, 1]; # 1
   inputList+=[0, 0, 4, 8, 0, 0, 0, 7, 0]; # 2
   inputList+=[8, 0, 0, 0, 0, 0, 0, 5, 2]; # 3
   inputList+=[2, 0, 0, 0, 5, 7, 0, 3, 0]; # 4
   inputList+=[0, 0, 0, 0, 0, 0, 0, 0, 0]; # 5
   inputList+=[0, 3, 0, 6, 9, 0, 0, 0, 5]; # 6
   inputList+=[7, 9, 0, 0, 0, 0, 0, 0, 8]; # 7
   inputList+=[0, 1, 0, 0, 0, 6, 5, 0, 0]; # 8
   inputList+=[5, 0, 0, 0, 3, 0, 0, 6, 0]; # 9
   
   solutions=solveSudoku(inputList);

   printSolutions(solutions);
   print('\nAnzahl: ',len(solutions));

#------------------------------------------------------------------------------#
#------------------------------------------------------------------------------#
   print('\n# Finished Test.\n');
# end if main