import Data.Array
import Data.List

--問題、空欄は0
q:: Array (Int,Int)Int
q=array((1,1),(9,9))[((x,y),0)|x<-[1..9],y<-[1..9]]
q1=q//[((1,3),5),((1,4),3),
       ((2,1),8),((2,8),2),
       ((3,2),7),((3,5),1),((3,7),5),
       ((4,1),4),((4,6),5),((4,7),3),
       ((5,2),1),((5,5),7),((5,9),6),
       ((6,3),3),((6,4),2),((6,8),8),
       ((7,2),6),((7,4),5),((7,9),9),
       ((8,3),4),((8,8),3),
       ((9,6),9),((9,7),7)
      ]

t=[(x,y)|x<-indexX,y<-indexY]

indexX,indexY,numbers::[Int]
indexX=[1..9]
indexY=[1..9]
numbers=[1..9]

-- (x,y)に値が入っていればそれを返す（問題の値）
-- そうでなければ、その時点で可能性のある数字を列挙
candidate ary x y ns
   | ary!(x,y)/=0 = [ary!(x,y)]
   | otherwise    = deleteFirstsBy (==) ns ([ary!(x,yy)|yy<-indexY]++
                                            [ary!(xx,y)|xx<-indexX]++
                                            [ary!(xx,yy)|xx<-[x1..x1+2],yy<-[y1..y1+2]]
                                           )
                  where
                    x1=(x-1)`div`3 * 3 + 1
                    y1=(y-1)`div`3 * 3 + 1

f []=[]
f ((ary,[]):xs)             = ary : f xs
f ((ary,lss@((x,y):ls)):xs) = f(g ary lss (candidate ary x y numbers)) ++ f xs 

g ary lss@((x,y):ls)(n:ns)=(ary//[((x,y),n)] ,ls):g ary lss ns
g _ _ []=[]

main = do print$ f[(q1,t)]