{"id":5304,"date":"2014-01-12T00:23:38","date_gmt":"2014-01-11T06:23:38","guid":{"rendered":"http:\/\/www.moonmile.net\/blog\/?p=5304"},"modified":"2014-01-12T10:28:55","modified_gmt":"2014-01-12T01:28:55","slug":"f-%e6%95%b0%e7%8b%ac%e3%82%92f%e3%81%a7%e8%a7%a3%e3%81%8f","status":"publish","type":"post","link":"http:\/\/www.moonmile.net\/blog\/archives\/5304","title":{"rendered":"[F#] \u6570\u72ec\u3092F#\u3067\u89e3\u304f"},"content":{"rendered":"

\n\u3075\u3068\u3001\u6570\u72ec\uff08sudoku\uff09\u3092F#\u3067\u89e3\u304f…\u3067\u691c\u7d22\u3059\u308b\u3068\u3001\n<\/p>\n

\nSudoku solver in F#
\nhttp:\/\/www.ffconsultancy.com\/dotnet\/fsharp\/sudoku\/<\/a>\n<\/p>\n

\n\u304c\u3042\u3063\u3066\u3001\u30b3\u30fc\u30c9\u304c\u3048\u3048\u3068\u3088\u304f\u308f\u304b\u3089\u306a\u3044\u306e\u3067\u3001\u81ea\u4f5c\u3057\u307e\u3057\u305f\u3002
\n\u6700\u521d\u306f\u7d20\u6734\u306a\u65b9\u6cd5\u3092\u4f7f\u3063\u3066\u3044\u3066\u3001\u5de6\u4e0a\u304b\u3089\u9806\u756a\u306b\u6570\u3092\u5165\u308c\u3066\u8a08\u7b97\u3057\u3066\u3001\u6570\u3092\u5165\u308c\u3066\u8a08\u7b97\u3057\u3066\u3068\u3044\u3046\u65b9\u6cd5\u3092\u3084\u3063\u3066\u3044\u305f\u306e\u3067\u3059\u304c\u3044\u3063\u3053\u3046\u306b\u7d42\u308f\u3089\u306a\u3044\u3067\u3001\u3061\u3087\u3063\u3068\u8003\u3048\u76f4\u3057\u3002\u5143\u30bd\u30fc\u30b9\u3092\u3088\u304f\u898b\u308b\u3068\u3001\u5de6\u4e0a\u304b\u3089\u30c1\u30a7\u30c3\u30af\u3057\u3066\u5165\u308c\u305f\u5f8c\u306f\u3001\u53f3\u306b\u9032\u3080\u3068\u3044\u3046\u65b9\u6cd5\u3092\u3068\u3063\u3066\u3044\u308b\u306e\u3067\u3001\u3042\u3042\u3001\u3053\u308c\u3067\u5341\u5206\u304b\u3068\u3044\u3046\u3053\u3068\u3067\u3002\n<\/p>\n

\n\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3068\u3057\u3066\u3001\n<\/p>\n

    \n
  1. \u5de6\u4e0a\uff080,0\uff09\u304b\u3089\u59cb\u3081\u308b\u3002<\/li>\n
  2. 0\u4ee5\u5916\u3060\u3063\u305f\u3089\u3001\u53f3\u3078\u9032\u3080\u3002<\/li>\n
  3. 1 \u53f3\u7aef\u306b\u9054\u3057\u305f\u3089\u6b21\u306e\u884c\u306e\u306f\u3058\u3081\u3078<\/li>\n
  4. 0\u3060\u3063\u305f\u3089\u3001<\/li>\n
  5. \u6a2a\u4e00\u5217\u3092\u8abf\u3079\u308b<\/li>\n
  6. \u7e26\u4e00\u5217\u3092\u8abf\u3079\u308b<\/li>\n
  7. 3×3\u306e\u30dc\u30c3\u30af\u30b9\u3092\u8abf\u3079\u308b<\/li>\n
  8. \u6570\u304c\u57cb\u307e\u308c\u3070\u3001\u57cb\u3081\u3066\u53f3\u306b\u9032\u3093\u3067\u518d\u5e30<\/li>\n<\/ol>\n

    \n\u306a\u611f\u3058\u3067\u9032\u3081\u308c\u3070OK\u3002\u305d\u3046\u3044\u3048\u3070\u3001\u884c\u5217\u8a08\u7b97\u3092\u3061\u307e\u3061\u307e\u81ea\u4f5c\u3057\u3066\u3044\u305f\u3068\u304d\u306b\u601d\u3063\u305f\u306e\u3067\u3059\u304c\u3001\u3053\u306e\u3042\u305f\u308a\u300c\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u300d\u2252\u8a08\u7b97\u6a5f\u304c\u5f97\u610f\u3068\u3059\u308b\u624b\u9806\u306f\u3001\u304c\u305c\u3093\u751f\u304d\u3066\u3044\u307e\u3059\u306d\u3002\u666e\u6bb5\u3001\u30ea\u30b9\u30c8\u69cb\u9020\u3068\u304b\u30c4\u30ea\u30fc\u69cb\u9020\u3068\u304b\u30aa\u30d6\u30b8\u30a7\u30af\u30c8\u306e\u69cb\u9020\u3068\u304b\u3001\u65e2\u5b58\u306e.NET\u30e9\u30a4\u30d6\u30e9\u30ea\u3067\u8cc4\u3048\u308b\u3082\u306e\u304c\u591a\u304b\u3063\u305f\u306e\u3067\u3059\u304c\u3001\u884c\u5217\u8a08\u7b97\u3001\u7dda\u5f62\u4ee3\u6570\u306e\u5206\u91ce\u306b\u306a\u308b\u3068\u3001\u9ad8\u901f\u5316\u3068\u304b\u8aa4\u5dee\u3082\u542b\u3081\u3066\u6570\u5b66\u7684\u306a\u89e3\u6cd5\u3068\u306f\u9055\u3063\u305f\u53e4\u5f0f\u3086\u304b\u3057\u304d\u300c\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u300d\u304c\u751f\u304d\u3066\u3044\u308b\u5206\u91ce\u306a\u306e\u3060\u306a\u3001\u3068\u518d\u78ba\u8a8d\u3057\u3066\u3044\u307e\u3059\u3002\n<\/p>\n

    \n\u3055\u3066\u3001\u3053\u306e\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u3092\u76f4\u306b\u5b9f\u88c5\u3057\u305f\u306e\u304c\u4ee5\u4e0b\u3067\u3059\u3002\n<\/p>\n

    \r\nlet rec solve (m:int[,]) x y = \r\n    printfn &quot;%d %d&quot; x y\r\n    if x = 9 && y = 8 then\r\n        \/\/ \u5b8c\u6210\r\n        printfn &quot;%A&quot; m\r\n        exit 0\r\n    elif x = 9 then\r\n        solve m 0 (y+1)\r\n    elif m.[x,y] <> 0 then\r\n        solve m (x+1) y \r\n    else \r\n        \/\/ \u7e26\/\u6a2a\/box\u3092\u30c1\u30a7\u30c3\u30af\r\n        let mutable v = [|0..9|]\r\n        for i in 0..8 do v.[m.[i,y]] <- 0\r\n        for i in 0..8 do v.[m.[x,i]] <- 0\r\n        let x0 = x\/3*3\r\n        let y0 = y\/3*3\r\n        for i in 0..2 do\r\n            for j in 0..2 do\r\n                v.[m.[x0+i,y0+j]] <- 0\r\n\r\n        let m' = Array2D.copy m\r\n        for i in 0..9 do\r\n            if v.[i] <> 0 then\r\n                m'.[x,y] <- v.[i]\r\n                solve m' (x+1) y\r\n<\/pre>\n
    \nfor \u30eb\u30fc\u30d7\u306e\u90e8\u5206\u304c\u300c\u3048\u30fc\u300d\u3068\u304b\u3001match \u3092\u4f7f\u3063\u305f\u307b\u3046\u304c\u3044\u3044\u3088\u3068\u304b\u3001fold \u306e\u4f7f\u3044\u65b9\u3092\u77e5\u3089\u306a\u3044\u3068\u304b\u8272\u3005\u3042\u308b\u308f\u3051\u3067\u3059\u304c\u3001\u7d20\u76f4\u306b\u66f8\u3044\u305f\u306e\u3067\u3053\u3093\u306a\u611f\u3058\u3002
    \n\u305f\u3060\u3057\u3001\u3053\u306e\u518d\u5e30\u95a2\u6570 solve \u306f\u5143\u306b\u5e30\u3063\u3066\u3053\u306a\u304f\u3066\u3001\u5b8c\u6210\u3057\u305f\u3068\u304d\uff089,8 \u306e\u3068\u304d\uff09\u306b\u306f\u3001\u7121\u7406\u77e2\u7406 exit \u3057\u3066\u30d7\u30ed\u30b0\u30e9\u30e0\u3092\u6b62\u3081\u3066\u3044\u307e\u3059\u3002\u3053\u308c\u304c\u518d\u5e30\u95a2\u6570\u3092\u623b\u3059\u3068\u518d\u3073\u5225\u306e\u89e3\u3092\u63a2\u3057\u51fa\u3059\u306e\u3067\u7121\u99c4\u306a\u3093\u3067\u3059\u3088\u306d\u3002\u5143\u30cd\u30bf\u3092\u307f\u308b\u3068\u3001\u4f8b\u5916\u3092\u767a\u751f\u3055\u305b\u3066\u3044\u308b\u306e\u3067\u3001\u305d\u308c\u3067\u3082\u3044\u3044\u306e\u3067\u3059\u304c\u3002\u672b\u5c3e\u518d\u5e30\u3092\u3057\u3066\u3044\u308b\u308f\u3051\u3067\u306f\u306a\u3044\u306e\u3067\u3001\u30b9\u30bf\u30c3\u30af\u3092\u98df\u3046\u306e\u306f\u4ed5\u65b9\u304c\u306a\u304f\uff08\u30d0\u30c3\u30af\u30c8\u30e9\u30c3\u30af\u6cd5\u3060\u3057\uff09\u3001\u305f\u3060\u3057\u3001\u30c4\u30ea\u30fc\u69cb\u9020\u3092\u63a2\u7d22\u3057\u3066\u3044\u304f\u4e2d\u3067\u5404\u30ce\u30fc\u30c9\u306f\u30d1\u30e9\u30ec\u30eb\u306b\u52d5\u304b\u305b\u308b\u306e\u3067\u63a2\u7d22\u81ea\u4f53\u306f\u6df1\u304f\u306a\u308a\u305d\u3046\u306a\u3068\u304d\u306f\u9069\u5f53\u306b\u30b9\u30ec\u30c3\u30c9\u5316\u3059\u308b\u3053\u3068\u3082\u53ef\u80fd\u306a\u306e\u304b\u306a\u3068\u3002\u3053\u306e\u3042\u305f\u308a\u306f\u3001\u5de8\u5927\u306a\u884c\u5217\u8a08\u7b97\u3068\u4f3c\u305f\u611f\u3058\u306b\u306a\u308b\u3068\u601d\u3063\u3066\u3044\u307e\u3059\u3002\n<\/p>\n
    \n\u307e\u3042\u30019×9\u306e\u6570\u72ec\u306a\u3089\u30701\u79d2\u3082\u7d4c\u305f\u306a\u3044\u3067\u89e3\u3051\u3066\u3057\u307e\u3046\u306e\u3067\u30b9\u30ec\u30c3\u30c9\u5316\u3059\u308b\u610f\u5473\u306f\u3042\u308a\u307e\u305b\u3093\u3002\u304c\u300110\u500d\u3050\u3089\u3044\u306e\u3001100×100\uff08\u6570\u5b57\u306f1\u304b\u3089100\u307e\u3067\uff09\u306e\u6570\u72ec\u306a\u3089\u3070\u3069\u3046\u306a\u3093\u3060\u308d\u3046\u3068\u3044\u3046\u306e\u304c\u3042\u308a\u307e\u3059\u3002\u30a6\u30a3\u30ad\u30da\u30c7\u30a3\u30a2\u3092\u898b\u308b\u3068\u3001\n<\/p>\n
    \nMathematics of Sudoku – Wikipedia, the free encyclopedia
    \n    http:\/\/en.wikipedia.org\/wiki\/Mathematics_of_Sudoku<\/a>\n<\/p>\n
    \n\u30dc\u30c3\u30af\u30b9\uff08bands\uff09\u304c5×5\u306e\u5834\u5408\u306e\u8a08\u7b97\u306f\u3042\u308b\u306e\u3067\u3059\u304c\u3001\u305d\u308c\u4ee5\u4e0a\u306f\u3069\u3046\u306a\u308b\u304b\u308f\u304b\u3089\u3093\u3068\u3044\u3046\u72b6\u614b\u307f\u305f\u3044\u3067\u3059\u3002\u307e\u3042\u3001\u30d1\u30ba\u30eb\u3068\u3057\u3066\u4eba\u9593\u304c\u89e3\u3051\u308b\u9650\u754c\u3092\u8d85\u3048\u3066\u3044\u308b\u3057\u3001\u30d1\u30ba\u30eb\u3068\u3057\u3066\u306e\u9762\u767d\u5473\u3082\u306a\u3044\u306e\u3067\u89e3\u304f\u610f\u5473\u306f\u306a\u3044\u306e\u3067\u3059\u304c\u3001\u30b3\u30f3\u30d4\u30e5\u30fc\u30bf\u306b\u89e3\u304b\u305b\u308b\u3068\u304d\u306e\u6700\u9069\u5316\u5177\u5408\u3092\u898b\u308b\u306e\u306b\u306f\u3044\u3044\u304b\u3082\u3001\u3068\u3002\n<\/p>\n
    \n\u6570\u72ec\u3092\u89e3\u304b\u305b\u308b\u305f\u3081\u306b\u306f\u3001\u914d\u5217\u306e\u914d\u5217\u3092\u6e21\u3057\u3066\u3084\u3063\u3066\u3001Array2D \u306b\u76f4\u3057\u307e\u3059\u3002\n<\/p>\n
    \r\n\/\/ Input puzzle\r\nlet example = [|[|0;0;0;0;6;0;4;0;0|];\r\n                [|0;5;0;0;0;3;6;0;0|];\r\n                [|1;0;0;0;0;5;0;0;0|];\r\n                [|0;4;1;0;0;0;0;0;0|];\r\n                [|0;9;0;0;0;0;0;2;0|];\r\n                [|5;0;2;0;0;0;3;4;0|];\r\n                [|3;0;0;7;0;0;0;0;0|];\r\n                [|0;0;6;5;0;0;0;9;0|];\r\n                [|0;0;4;0;1;0;0;0;0|]|]\r\n\r\nlet pazzle = Array2D.init 9 9 (fun i j -> example.[i].[j])\r\n\r\nsolve pazzle 0 0 \r\n<\/pre>\n
    \n\u7b54\u3048\u306f\u3053\u3093\u306a\u611f\u3058\n<\/p>\n
    \r\n[[2; 3; 7; 1; 6; 8; 4; 5; 9]\r\n [4; 5; 8; 9; 7; 3; 6; 1; 2]\r\n [1; 6; 9; 2; 4; 5; 7; 8; 3]\r\n [6; 4; 1; 3; 5; 2; 9; 7; 8]\r\n [7; 9; 3; 4; 8; 1; 5; 2; 6]\r\n [5; 8; 2; 6; 9; 7; 3; 4; 1]\r\n [3; 1; 5; 7; 2; 9; 8; 6; 4]\r\n [8; 2; 6; 5; 3; 4; 1; 9; 7]\r\n [9; 7; 4; 8; 1; 6; 2; 3; 5]]\r\n<\/pre>\n
    \n\u5b9f\u306f\u3001\u5143\u30cd\u30bf\u306e\u6570\u72ec\u306f\u8907\u6570\u56de\u7b54\u3042\u3063\u3066\u3001\u554f\u984c\u3068\u3057\u3066\u3088\u308d\u3057\u304f\u306a\u3044\u3093\u3067\u3059\u3088\u306d\u3002
    \n\u305d\u308c\u306f\u3055\u3066\u304a\u304d\u3001\u691c\u7b97\u3092\u3059\u308b\u30b3\u30fc\u30c9\u304c\u4ee5\u4e0b\n<\/p>\n
    \r\nlet ans = \r\n    [[2; 3; 7; 1; 6; 8; 4; 5; 9]\r\n     [4; 5; 8; 9; 7; 3; 6; 1; 2]\r\n     [1; 6; 9; 2; 4; 5; 7; 8; 3]\r\n     [6; 4; 1; 3; 5; 2; 9; 7; 8]\r\n     [7; 9; 3; 4; 8; 1; 5; 2; 6]\r\n     [5; 8; 2; 6; 9; 7; 3; 4; 1]\r\n     [3; 1; 5; 7; 2; 9; 8; 6; 4]\r\n     [8; 2; 6; 5; 3; 4; 1; 9; 7]\r\n     [9; 7; 4; 8; 1; 6; 2; 3; 5]]\r\n\r\nlet A = Array2D.init 9 9 (fun i j -> ans.[i].[j])\r\n\r\nlet check (m:int[,]) =\r\n    \r\n    for y in 0..8 do\r\n        let mutable v = [|0..9|]\r\n        for i in 0..8 do\r\n            v.[m.[i,y]] <- 0\r\n        if Array.sum v <> 0 then\r\n            printfn &quot;error y=%d&quot; y\r\n\r\n    for x in 0..8 do\r\n        let mutable v = [|0..9|]\r\n        for i in 0..8 do\r\n            v.[m.[x,i]] <- 0\r\n        if Array.sum v <> 0 then\r\n            printfn &quot;error x=%d&quot; x\r\n\r\n    for x in 0..3..8 do\r\n        for y in 0..3..8 do\r\n            let mutable v = [|0..9|]\r\n            for i in 0..2 do\r\n                for j in 0..2 do\r\n                    v.[m.[x+i,y+j]] <- 0\r\n            if Array.sum v <> 0 then\r\n                printfn &quot;error x=%d y=%d&quot; x y\r\n            \r\n    printfn &quot;OK&quot;\r\n<\/pre>\n
    \n# \u3042\u3042\u3001\u305d\u3046\u304b\u3002MSTest \u3092\u4f7f\u3063\u3066\u3082\u3044\u3044\u3093\u3060\u3063\u3051\u3002\u3069\u3063\u304b\u306b\u30b5\u30f3\u30d7\u30eb\u30da\u30fc\u30b8\u304c\u3042\u3063\u305f\u306f\u305a\u306a\u306e\u3067\u5f8c\u307b\u3069\u3002\n<\/p>\n
    \n\u3067\u3001bounds \u304c 10×10\u306e\u6570\u72ec\uff08\u5168\u4f53\u304c100×100\uff09\u306f\u3001\u3069\u3046\u306a\u308b\u306e\u304b\u306a\u3068\u8003\u3048\u3066\u307f\u305f\u3082\u306e\u306e…\u305d\u3093\u306a\u6570\u72ec\u306e\u554f\u984c\u306f\u3069\u3053\u306b\u3082\u306a\u3044\u308f\u3051\u3067\u3001\u3068\u3044\u3046\u3053\u3068\u306f\u81ea\u5206\u3067\u554f\u984c\u3092\u4f5c\u3089\u306a\u3044\u3068\u30c0\u30e1\u306a\u306e\u3067\u3059\u3088\u3002\u3069\u3046\u305b\u306a\u3089\u3070\u3001\u89e3\u304c\u3072\u3068\u3064\u3057\u304b\u306a\u3044\u30d1\u30bf\u30fc\u30f3\u306e\u81ea\u52d5\u4f5c\u6210\u3092\u3057\u305f\u3044\u308f\u3051\u3067\u3001\u3053\u3053\u306f\u601d\u6848\u306e\u3057\u3069\u3053\u308d\u3002\u3056\u3063\u3068\u3001\u554f\u984c\u4f5c\u6210\u306e\u624b\u9806\u3092\u66f8\u304d\u4e0b\u3059\u3068\u3001\n<\/p>\n
      \n
    1.  \u77db\u76fe\u306a\u304fNxN\u3092\u6577\u304d\u8a70\u3081\u308b\u3002<\/li>\n
    2.  \u30e9\u30f3\u30c0\u30e0\u306b1\u500b\u7a7a\u767d\u306b\u3059\u308b\u3002<\/li>\n
    3.  \u89e3\u304c1\u3064\u3057\u304b\u306a\u3044\u3053\u3068\u3092\u78ba\u8a8d\u3059\u308b\u3002\u518d\u30732\u3078<\/li>\n<\/ol>\n
      \n\u306a\u611f\u3058\u304b\u306a\u30023\u306e\u90e8\u5206\u3092\u6700\u9069\u5316\u3057\u305f\u3044\u3068\u3053\u308d\u3067\u3059\u304c\u3001\u57fa\u672c\u306f\u5148\u306e\u89e3\u6cd5\u30b3\u30fc\u30c9\u3092\u62e1\u5f35\u3059\u308b\u3060\u3051\u306a\u306e\u3067\u3001\u5f8c\u306f\u8a08\u7b97\u6642\u9593\u306e\u554f\u984c\u304b\u306a\u3002<\/p>\n","protected":false},"excerpt":{"rendered":"
      \u3075\u3068\u3001\u6570\u72ec\uff08sudoku\uff09\u3092F#\u3067\u89e3\u304f…\u3067\u691c\u7d22\u3059\u308b\u3068\u3001 Sudoku solver in F# http:\/\/www.ffconsultancy.com\/dotnet\/fsharp\/sudoku\/ \u304c\u3042\u3063\u3066\u3001 … \u7d9a\u304d\u3092\u8aad\u3080 →<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[59],"tags":[],"class_list":["post-5304","post","type-post","status-publish","format-standard","hentry","category-f"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/posts\/5304","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/comments?post=5304"}],"version-history":[{"count":3,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/posts\/5304\/revisions"}],"predecessor-version":[{"id":5306,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/posts\/5304\/revisions\/5306"}],"wp:attachment":[{"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/media?parent=5304"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/categories?post=5304"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.moonmile.net\/blog\/wp-json\/wp\/v2\/tags?post=5304"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}