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)]
 

aW1wb3J0IERhdGEuQXJyYXkKaW1wb3J0IERhdGEuTGlzdAoKLS3llY/poYzjgIHnqbrmrITjga8wCnE6OiBBcnJheSAoSW50LEludClJbnQKcT1hcnJheSgoMSwxKSwoOSw5KSlbKCh4LHkpLDApfHg8LVsxLi45XSx5PC1bMS4uOV1dCnExPXEvL1soKDEsMyksNSksKCgxLDQpLDMpLAogICAgICAgKCgyLDEpLDgpLCgoMiw4KSwyKSwKICAgICAgICgoMywyKSw3KSwoKDMsNSksMSksKCgzLDcpLDUpLAogICAgICAgKCg0LDEpLDQpLCgoNCw2KSw1KSwoKDQsNyksMyksCiAgICAgICAoKDUsMiksMSksKCg1LDUpLDcpLCgoNSw5KSw2KSwKICAgICAgICgoNiwzKSwzKSwoKDYsNCksMiksKCg2LDgpLDgpLAogICAgICAgKCg3LDIpLDYpLCgoNyw0KSw1KSwoKDcsOSksOSksCiAgICAgICAoKDgsMyksNCksKCg4LDgpLDMpLAogICAgICAgKCg5LDYpLDkpLCgoOSw3KSw3KQogICAgICBdCgp0PVsoeCx5KXx4PC1pbmRleFgseTwtaW5kZXhZXQoKaW5kZXhYLGluZGV4WSxudW1iZXJzOjpbSW50XQppbmRleFg9WzEuLjldCmluZGV4WT1bMS4uOV0KbnVtYmVycz1bMS4uOV0KCi0tICh4LHkp44Gr5YCk44GM5YWl44Gj44Gm44GE44KM44Gw44Gd44KM44KS6L+U44GZ77yI5ZWP6aGM44Gu5YCk77yJCi0tIOOBneOBhuOBp+OBquOBkeOCjOOBsOOAgeOBneOBruaZgueCueOBp+WPr+iDveaAp+OBruOBguOCi+aVsOWtl+OCkuWIl+aMmQpjYW5kaWRhdGUgYXJ5IHggeSBucwogICB8IGFyeSEoeCx5KS89MCA9IFthcnkhKHgseSldCiAgIHwgb3RoZXJ3aXNlICAgID0gZGVsZXRlRmlyc3RzQnkgKD09KSBucyAoW2FyeSEoeCx5eSl8eXk8LWluZGV4WV0rKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgIFthcnkhKHh4LHkpfHh4PC1pbmRleFhdKysKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBbYXJ5ISh4eCx5eSl8eHg8LVt4MS4ueDErMl0seXk8LVt5MS4ueTErMl1dCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICApCiAgICAgICAgICAgICAgICAgIHdoZXJlCiAgICAgICAgICAgICAgICAgICAgeDE9KHgtMSlgZGl2YDMgKiAzICsgMQogICAgICAgICAgICAgICAgICAgIHkxPSh5LTEpYGRpdmAzICogMyArIDEKCmYgW109W10KZiAoKGFyeSxbXSk6eHMpICAgICAgICAgICAgID0gYXJ5IDogZiB4cwpmICgoYXJ5LGxzc0AoKHgseSk6bHMpKTp4cykgPSBmKGcgYXJ5IGxzcyAoY2FuZGlkYXRlIGFyeSB4IHkgbnVtYmVycykpICsrIGYgeHMgCgpnIGFyeSBsc3NAKCh4LHkpOmxzKShuOm5zKT0oYXJ5Ly9bKCh4LHkpLG4pXSAsbHMpOmcgYXJ5IGxzcyBucwpnIF8gXyBbXT1bXQoKbWFpbiA9IGRvIHByaW50JCBmWyhxMSx0KV0K