数独（ナンプレ）

R の数独ライブラリはすごい。

ブルートフォースで解くプログラムを書いてみたが，うまくいくときはまあまあだが，同じ問題でも，転置行列を入力すると数倍遅くなるなんてこともある。

solve = function(arg) {
  if (length(arg) == 1) arg = scan(arg, what = "")
  m = t(sapply(strsplit(arg, ""), function(s) as.integer(gsub("-", "0", unlist(s)))))
  m = array(c(m[1:3, 1:3], m[4:6, 1:3], m[7:9, 1:3],
              m[1:3, 4:6], m[4:6, 4:6], m[7:9, 4:6],
              m[1:3, 7:9], m[4:6, 7:9], m[7:9, 7:9]), dim = rep(3, 4))
  func = function(k, l) {
    a = which(m[, , k, l] != 0, arr.ind = TRUE)
    ok = colSums(t(pos[, (a[, 1] - 1) + (a[, 2] - 1) * 3 + 1, drop = FALSE]) == m[, , k, l][a]) == nrow(a)
    pos2 = pos[ok, ]
    for (j in (1:3)[-l]) {
      a = which(m[, , k, j] != 0, arr.ind = TRUE)
      num = m[, , k, j][a]
      for (i in 1:nrow(a)) {
        for (i2 in 0:2 * 3) {
          pos2 = pos2[pos2[, a[i, 1] + i2, drop = FALSE] != num[i], , drop = FALSE]
        }
      }
    }
    for (j in (1:3)[-k]) {
      a = which(m[, , j, l] != 0, arr.ind = TRUE)
      num = m[, , j, l][a]
      for (i in 1:nrow(a)) {
        for (i2 in 1:3) {
          pos2 = pos2[pos2[, (a[i, 2] - 1) * 3 + i2, drop = FALSE] != num[i], , drop = FALSE]
        }
      }
    }
    pos2
  }
  library(e1071)
  pos = permutations(9)
  pos11 = func(1, 1)
  pos12 = func(1, 2)
  pos13 = func(1, 3)
  pos21 = func(2, 1)
  pos22 = func(2, 2)
  pos23 = func(2, 3)
  pos31 = func(3, 1)
  pos32 = func(3, 2)
  pos33 = func(3, 3)
  a = matrix(0, 9, 9)
  dimnames(a) = list(letters[1:9], letters[1:9])
  notUnique = function(a, sw, n) any(apply(a, sw, function(x) length(unique(x)) != n))
  for (i11 in 1:nrow(pos11)) {
    a[1:3, 1:3] = pos11[i11, ]
    for (i12 in 1:nrow(pos12)) {
      a[1:3, 4:6] = pos12[i12, ]
      if (notUnique(a[1:3, 1:6], 1, 6)) next
      for (i13 in 1:nrow(pos13)) {
        a[1:3, 7:9] = pos13[i13, ]
        if (notUnique(a[1:3, ], 1, 9)) next
        for (i21 in 1:nrow(pos21)) {
          a[4:6, 1:3] = pos21[i21, ]
          if (notUnique(a[1:6, 1:3], 2, 6)) next
          for (i22 in 1:nrow(pos22)) {
            a[4:6, 4:6] = pos22[i22, ]
            if (notUnique(a[4:6, 1:6], 1, 6) || notUnique(a[1:6, 4:6], 2, 6)) next
            for (i23 in 1:nrow(pos23)) {
              a[4:6, 7:9] = pos23[i23, ]
              if (notUnique(a[4:6, ], 1, 9) || notUnique(a[1:6, 7:9], 2, 6)) next
              for (i31 in 1:nrow(pos31)) {
                a[7:9, 1:3] = pos31[i31, ]
                if (notUnique(a[, 1:3], 2, 9)) next
                for (i32 in 1:nrow(pos32)) {
                  a[7:9, 4:6] = pos32[i32, ]
                  if (notUnique(a[7:9, 1:6], 1, 6) || notUnique(a[, 4:6], 2, 9)) next
                  for (i33 in 1:nrow(pos33)) {
                    a[7:9, 7:9] = pos33[i33, ]
                    if (notUnique(a[7:9, ], 1, 9) || notUnique(a[, 7:9], 2, 9)) next
                    return(a)
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}
solve(system.file("puz1.txt",package="sudoku"))
solve(c("--9----6-",
        "1---3---7",
        "-6---93--",
        "--3----4-",
        "7---1---8",
        "-4----2--",
        "--74---1-",
        "2---8---5",
        "-8----9--"))