ナンプレを解くプログラム

ナンプレを解くプログラム

締め切りが 2018/03/07 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】
簡単なナンプレの問題を解くプログラムを書いてみましょう。

【問題】
次のようなナンプレがあります。
・2x2のマス（Box）が縦横ふたつずつ並んだ4x4のマスがある
・それぞれのマスには1~4の数字が入り、それらは行／列の4つのマスに同じ数字がくることはない（行／列の合計は10となる）
・2x2のマス（Box）にも同じ数字がくることはなく、合計は10となる
・最初に1~4の数字がランダムにひとつずつ設定されている（同じ行／列／Boxに複数の数字が設定されることは無い）

初期状態の例（＿は数字の入っていない状態を表します）



このナンプレを解くプログラムを書いて、数字を埋めてください。

【入出力】
CSV形式のテストデータを標準入力で受け取る想定で、結果を標準出力するプログラムを作ってください。

上図のナンプレでは、以下のようなCSVファイルが入力されます。

    1.    1,0,0,0
    2.    0,0,3,0
    3.    0,0,0,4
    4.    0,2,0,0

これに対して、以下のようなデータを標準出力から出力してください。

    1.    1,3,4,2
    2.    2,4,3,1
    3.    3,1,2,4
    4.    4,2,1,3
【入出力サンプル】
Input
1,0,0,0
0,0,3,0
0,0,0,4
0,2,0,0

Output
1,3,4,2
2,4,3,1
3,1,2,4
4,2,1,3

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

ブルートフォースで簡単に書く

permutations = function (n)
{
  z = matrix(1)
  for (i in 2:n) {
    x = cbind(z, i)
    a = c(1:i, 1:(i - 1))
    z = matrix(0, ncol = ncol(x), nrow = i * nrow(x))
    z[1:nrow(x), ] = x
    for (j in 2:i - 1) {
      z[j * nrow(x) + 1:nrow(x), ] = x[, a[1:i + j]]
    }
  }
  z
}

f = function(x) {
  g = function(a) {
    b = which(a != 0, arr.ind = TRUE)
    x = b[1] + 2 * b[2] - 2
    y = a[b]
    A = permutations(4)
    A = A[A[, x] == y, ]
    return(A)
  }
  x = matrix(x, ncol = 4, byrow = TRUE)
  A = g(x[1:2, 1:2])
  B = g(x[1:2, 3:4])
  C = g(x[3:4, 1:2])
  D = g(x[3:4, 3:4])
  for (i in 1:6) {
    for (j in 1:6) {
      for (k in 1:6) {
        for (m in 1:6) {
          # 横方向のチェック
          if (length(unique(c(A[i, 1], A[i, 3], B[j, 1], B[j, 3]))) != 4) next
          if (length(unique(c(A[i, 2], A[i, 4], B[j, 2], B[j, 4]))) != 4) next
          if (length(unique(c(C[k, 1], C[k, 3], D[m, 1], D[m, 3]))) != 4) next
          if (length(unique(c(C[k, 2], C[k, 4], D[m, 2], D[m, 4]))) != 4) next
          # 縦方向のチェック
          if (length(unique(c(A[i, 1], A[i, 2], C[k, 1], C[k, 2]))) != 4) next
          if (length(unique(c(A[i, 3], A[i, 4], C[k, 3], C[k, 4]))) != 4) next
          if (length(unique(c(B[j, 1], B[j, 2], D[m, 1], D[m, 2]))) != 4) next
          if (length(unique(c(B[j, 3], B[j, 4], D[m, 3], D[m, 4]))) != 4) next
          cat(sprintf("%d,%d,%d,%d\n", A[i, 1], A[i, 3], B[j, 1], B[j, 3]))
          cat(sprintf("%d,%d,%d,%d\n", A[i, 2], A[i, 4], B[j, 2], B[j, 4]))
          cat(sprintf("%d,%d,%d,%d\n", C[k, 1], C[k, 3], D[m, 1], D[m, 3]))
          cat(sprintf("%d,%d,%d,%d\n", C[k, 2], C[k, 4], D[m, 2], D[m, 4]))
        }
      }
    }
  }
}

# f(c(1, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, 4, 0, 2, 0, 0))
x = scan(file("stdin", "r"), sep=",")
f(x)

入力
1,0,0,0
0,0,3,0
0,0,0,4
0,2,0,0

出力
1,3,4,2
2,4,3,1
3,1,2,4
4,2,1,3

入力
0,0,0,4
0,2,0,0
0,0,3,0
1,0,0,0

出力
3,1,2,4
4,2,1,3
2,4,3,1
1,3,4,2