ナンプレを解くプログラム
締め切りが 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
最新の画像[もっと見る]
- 算額(その2135) 11時間前
- 算額(その2134) 18時間前
- 算額(その2133) 1日前
- 算額(その2132) 3日前
- 算額(その2131) 4日前
- 算額(その2130) 4日前
- 算額(その2129) 5日前
- 算額(その2128) 5日前
- 算額(その2127) 6日前
- 算額(その2126) 6日前
※コメント投稿者のブログIDはブログ作成者のみに通知されます