paiza times

paizaがお届けする、テック・キャリア・マネジメント領域における「今必要な情報」を届けるWebメディア

logo

paizaがお届けする、テック・キャリア・マネジメント領域の「今必要な情報」を届けるWebメディア

Pythonで魔方陣のプログラミング問題を解くための考え方

f:id:paiza:20200630115818j:plain
Pixabayからの画像

f:id:paiza:20180910132940p:plainこんにちは。倉内です。

プログラミングの基本を学習したあと、さらに力をつけるにはやはり自分でコードを書く経験を増やすことが大切です。

Webサービスやアプリなどの作成に取り掛かるのもよいですが、いろいろなプログラミング問題を解いてみるのもおすすめです

問題文から「どんな機能を実装することが求められているのか?」「どんな条件や制約があるのか?」を理解してコードを書くことで、ロジックを考える力が身につきます。また、分からないことを自力で調べる力も鍛えられます。

そこで今回は、少しだけ難しめのプログラミング問題を例に、問題文の理解や考え方などをお伝えしながら解説をしたいと思います。

今回解説する問題の難易度って?

この記事では、paizaが提供している問題を解いてプログラミングスキルを測るスキルチェックというサービスのBランク相当の問題を扱います。

スキルチェックでは、問題の難易度をS・A・B・C・Dのランクに分けており、基礎文法を習得できていれば解けるDランクから、問題文を正確に読み解き採用すべきアルゴリズムや大規模データのテストケースを考慮する必要があるSランクまでさまざまな問題を公開しています。

スキルチェックについて詳しくはこちら
paizaのスキルチェック

今回はBランク相当の難易度の問題を解説していきます。「D・Cランクの問題はある程度解けるけど、Bランクはまだやったことがない…」という方も一緒に取り組んでいきましょう。

スキルチェックの問題はpaizaが提供している就職・転職サービスの求人応募に関係するため、解説や解答を公開することはできません。よってゲームイベントで公開しているプログラミング問題を使います。

こちらはコードを公開したり友人と相談して解いたりしても構いませんので学習にぜひご利用ください。

Bランク相当の問題解説

今回は、異世界ファンタジーの舞台でプログラミング学習ができる『ロジックサマナー』にあるBランク相当の問題をPythonで解説します。

このゲームではプログラミング問題を「封印」、プログラミングを「召喚魔法」といい、ITエンジニアのあなたは伝説の召喚士として問題を解いて世界を救う使命を負っています。ぜひ一緒にBランクの封印を解いていきましょう。

書いたコードはゲーム内で提出でき、OKかNGの判定がされます。

Mission:魔法陣(封印レベルB)

あなたは魔法陣を作成しています。

ここで、N 行 N 列の魔方陣とは、
1 から N^2 までの数字を N 行 N 列に並べたもので、各行、各列、および 2 つの対角線それぞれについて、そこに並んだ数の総和がいずれも等しくなるようなものを言います。

例えば、3 行 3 列の魔方陣の一例は以下のようになります。


誤ってこの魔方陣にコーヒーをこぼしてしまったため、魔方陣の中の 2 つの数字が見えなくなってしまいました。

優秀な魔法使いであるあなたは、2 つの見えなくなってしまった数を補うことで、この魔方陣を修復しようと考えました。魔方陣の行数・列数を表す N、および見えている数字の情報が与えられるので、魔方陣を修復してください。

例えば、入力例 1 を説明する図は以下のようになります。


この例では 3 行 3 列の魔法陣を作りましたが、3 行目の 2 列目と 3 行目の 3 列目が見えなくなってしまいました。魔法陣の中で見えていない数字は 4, 9 の二種類です。

3 行目の 2 列目が 4 で、3 行目の 3 列目が 9 である可能性と3 行目の 2 列目が 9 で、3 行目の 3 列目が 4 である可能性との 2 つの可能性が考えられます。後者は正しい魔法陣となりますが、前者は正しい魔法陣とはなりません。よって、答えとしては図 1 の魔法陣を出力します。なお、正しい魔法陣が一通りであることは保証されています。

入力される値:

入力は標準入力にて以下のフォーマットで与えられます。

N
m_{1, 1} m_{1, 2} ... m_{1, N}
m_{2, 1} m_{2, 2} ... m_{2, N}
...
m_{N, 1} m_{N, 2} ... m_{N, N}

・1 行目に作った魔法陣の大きさ N が与えられます。
・続く N 行のうちの i 行目 (1 ≦ i ≦ N) には N 個の整数が半角スペース区切りで与えられます。i 行目の j 番目 (1 ≦ i ≦ N) の整数 m_{i, j} は作った魔法陣の i 行 j 列目の数を表します。ただし、コーヒーをこぼして見えなくなった部分は 0 になっています。
・入力は合計で N + 1 行となり、入力値最終行の末尾に改行が 1 つ入ります。

条件:

条件
すべてのテストケースにおいて、以下の条件をみたします。

・3 ≦ N ≦ 10
・0 ≦ m_{i, j} ≦ N*N (1 ≦ i ≦ N, 1 ≦ j ≦ N)
・m_{1, 1}, m_{1, 2}, ..., m_{N, N} の中で 2 つだけ 0 になるものが存在する
・m_{i, j} ≠ 0, m_{k, l} ≠ 0 となる i, j, k, l について (i, j) ≠ (k, l) のとき m_{i, j} ≠ m_{k, l} が成り立つ (1 ≦ i, j, k, l ≦ N)

考え方:

少し前にBランクよりもう少し易しいCランク相当の問題の解説をしたのですが、今回はさらに問題文が長く、条件も複雑になりました。

いきなりコードを書くのは難しいため、問題文の理解と方針を立てるところから始めましょう。

まずは問題文にあった3行3列の魔方陣(入力例1)で答えを求めてみて、何を問われているか・どう考えるとよいかを整理します。

条件によるとコーヒーをこぼして見えなくなったところは「0」で表すんでしたね。

6 1 8
7 5 3
2 0 0

1、2行目と1列目は値がすべて入っているので合計値は「15」が正しいと分かります。3行1列の「2」と「0」になっている3行2列および3行3列の2つの値を足すと「15」になるような値を求めると考えるとよいでしょうか?

ただ、ここで問題文をもう一度見ていただきたいのですが「あなたは“魔法陣”を作成しています」「N 行 N 列の“魔方陣”とは、…」と使い分けされていますよね。(誤変換ではないんです…)

魔方陣というのはWikipediaによると「n×n 個の正方形の方陣に数字を配置し、縦・横・対角線のいずれの列についても、その列の数字の合計が同じになるもののことである。特に1から方陣のマスの総数 n2 までの数字を1つずつ過不足なく使ったものを言う。」とあり、まさに今回の問題そのものです。

そして実は魔方陣の縦・横・対角線の値の和(sumの s としましょう)は

s = n×(n^2+1)÷2

という式で求められることが知られています。

入力例1のnは3なので、s = 3×(3^2+1)÷2 = 15 となり正しい合計値となりました。

もちろん前述のとおり今回の問題では、「0」のない行または列の値を足して「15」とも出せるのですが、上記の式が分かっていると「「0」のない行もしくは列を探して、その値を合計する」というステップは不要になるのでコードは短く書けます。

正しい合計値 s が分かったら、あとは「0」が1つの行もしくは列を見つけて「求めたい値 = s - 「0」以外の値の合計」で答えが導けそうです。

入力例1では、2列目を使って「3行2列の値 = 15 - 6 = 9」、3列目を使って「3行3列の値 = 15 - 11 = 4」となり、魔法陣を出力すると以下の通りとなり正しい値を求められたことが分かります。

6 1 8
7 5 3
2 9 4

コードを書く:
①標準入力で与えられる値を取得する

最初に標準入力から魔法陣の大きさNと値を受け取ります。

Python3では、input関数を使うんでしたね。整数として扱いたいのでint型で取得します。

n = int(input())

魔法陣の値は二次元リストに格納することにしましょう。ちなみに二次元リストについては、paizaラーニングの動画講座「Python入門編6: 多次元リストを理解しよう」で学ぶことができます。

内包表記を使って記述します。魔法陣は「magic square」というらしいのでsquareというリストにしました。

(参考)Pythonリスト内包表記の使い方 | note.nkmk.me

square = [[int(m) for m in input().split()] for _ in range(n)]

「for _ in range(n)」の部分は「for i in range(n)」のように書いてもいいのですが、このあとこの変数は使わないので「_」としてあります。

入力例1をsquareに格納し、標準出力してみると以下のようになります。

[[6, 1, 8], [7, 5, 3], [2, 0, 0]]

与えられた値を変数nとリストsquareへ格納することができました。

②魔方陣の列・行・対角線の値の和を求める

さきほどの式を利用しましょう。べき乗は「**」で記述します。

s = n * (n ** 2 + 1) // 2

Python3では「/」で割り算をすると、結果が整数であっても浮動小数点数(float型)になってしまいます。今回、結果は必ず整数になるはずなので「//」を使って小数点以下を切り捨てた結果を s に格納します。

③「0」のあるインデックスを求める

続いて2つの「0」がどこに存在するかを取得します。二次元リストを検索して「0」があった行・列を覚えておくことにしましょう。

行を i で、列を j で表し、1つ目の「0」のインデックスをzi1、zj1、2つの目の「0」のインデックスをzi2、zj2という変数に格納します。

なお、入力例1の魔方陣の値はこのように表すことができます。

square[0][0] square[0][1] square[0][2]
square[1][0] square[1][1] square[1][2]
square[2][0] square[2][1] square[2][2]

よって任意の値を示すとき、square[i][j]となります。

Pythonではリストの要素のインデックスを取得する際に index() や enumerate() を使います。今回はリストの要素が重複している(=「0」が2つある)かつ、どちらのインデックスも取得したいため enumerate() のほうを使います。

# ①②で書いたコードは省略

# 0のあるインデックスを求めてリストzに格納
z = []
for i,i_v in enumerate(square):
    for j,j_v in enumerate(i_v):
        if j_v == 0:
            z.append((i,j))

# zi1, zj1, zi2, zj2にそれぞれ格納
zi1, zj1 = z[0]
zi2, zj2 = z[1]

正しく取れているか入力例1で確認してみましょう。

print(z)

print(zi1, zj1)
print(zi2, zj2)

# 実行すると
# [(2, 1), (2, 2)]
# 2 1
# 2 2
# と出力され「0」のある位置が正しく取れた
④0が同じ行・列ではないところで「s-見えている値の合計」を求める

入力例1(3行3列の魔方陣)のように3行目に「0」が2つ存在する場合、3行目は正しい値を求める行としては適していません。

そのためzi1とzi2が同じでないか(=同じ行ではないか)、もしくはzj1とzj2が同じでないか(=同じ列ではないか)を条件にして正しい値を求めるのに適した行もしくは列を探します。

当該の行または列の値の合計値は sum() を使って求めます。

if zi1 != zi2:
    square[zi1][zj1] = s - sum([square[zi1][j] for j in range(n)])
    square[zi2][zj2] = s - sum([square[zi2][j] for j in range(n)])
elif zj1 != zj2:
    square[zi1][zj1] = s - sum([square[i][zj1] for i in range(n)])
    square[zi2][zj2] = s - sum([square[i][zj2] for i in range(n)])

これで「0」になっていた square[zi1][zj1] と square[zi2][zj2] はそれぞれ求めた正しい値が入ったはずです。

正しい値が求められたかまた入力例1で試してみます。

print(square[zi1][zj1])
print(square[zi2][zj2])

# 実行すると
# 4
# 9
# と出力された。

正しい値が求められました。

⑤正しい魔法陣を出力する

あとひと息です。最後に求めた値を魔法陣の形で出力しましょう。

リストから値を出力するときはjoinを使った書き方を覚えておくと、今回のように二次元リストを使った場合二重ループを回さずに表現できます。

書き方はこうです。

'間に挿入したい文字列(今回は半角スペース)'.join([連結したい文字列のリスト])

(参考)Pythonで文字列を連結・結合(+演算子、joinなど) | note.nkmk.me

for row in square:
    print(' '.join(map(str, row)))

入力例1で出力結果を確認します。

6 1 8
7 5 3
2 9 4

正しい結果が出力できました。入力例2でも確認しておきます。

1 15 8 24 17
19 3 21 12 10
13 22 20 6 4
25 9 2 18 11
7 16 14 5 23

問題なさそうですね!では、すべてのコードを合わせて、ゲームの画面で提出してみます。

# 何行何列の魔法陣かを示すnを取得
n = int(input())

# n×nの大きさの魔法陣の値を二次元リストsquareに格納
square = [[int(m) for m in input().split()] for _ in range(n)]

# 魔方陣の列・行・対角線の値の和sを求める
s = n * (n ** 2 + 1) // 2

# 0のあるインデックスを求めてリストzに格納
z = []
for i,i_v in enumerate(square):
    for j,j_v in enumerate(i_v):
        if j_v == 0:
            z.append((i,j))

# zi1, zj1, zi2, zj2にそれぞれ格納
zi1, zj1 = z[0]
zi2, zj2 = z[1]

# 0が同じ行・列ではないところで「s-見えている値の合計」を求める
if zi1 != zi2:
    square[zi1][zj1] = int(s) - sum([square[zi1][j] for j in range(n)])
    square[zi2][zj2] = int(s) - sum([square[zi2][j] for j in range(n)])
elif zj1 != zj2:
    square[zi1][zj1] = int(s) - sum([square[i][zj1] for i in range(n)])
    square[zi2][zj2] = int(s) - sum([square[i][zj2] for i in range(n)])

# 魔法陣を出力する
for row in square:
    print(' '.join(map(str, row)))

コード詠唱に成功しました!

なお、解き方はひと通りではありませんので、ご自分で考えた方法での実装もぜひ試してみてください。

このあとの学習法について

Bランク相当の問題を解いてみて、「難しかったかも…」という方は、Cランク相当の問題を解説した記事のほうをチェックしてみてください。

paiza.hatenablog.com

上記記事の問題が「これなら解ける!」という場合は、練習問題集「Bランクレベルアップセット」での学習をおすすめします。

この問題集は、Cランク問題をたくさん解くことでBランク問題を解くための力をつけるという目的で作成したものです。現在はPython3、Ruby、Java、C#の解答コードをご用意しています。

もう少しBランク相当の問題をいろいろ解いてみたいという方は、以下の記事でPythonの解答コードを公開していますので取り組んでみてください。

エンジニアが死滅シタ世界』より、[MISSION LEVEL: B] 高層タワー、砂漠の公園、隔離された街のゲート

paiza.hatenablog.com

「高層タワー」は解説記事もあります。

paiza.hatenablog.com

「Bランクくらいなら意外にいけそう!」という方は、スキルチェックのBランク問題、そしてA・Sランクの問題にも挑戦してみてください。

まとめ

paizaのプログラミングゲームで公開しているBランク相当の問題を解いてみました。

今回は数値を扱う問題でしたが、文字列の操作や法則を見つける問題などさまざまな内容があります。これが少し難しいと感じた方も、ぜひご自分が得意なジャンルで挑戦してみてくださいね。

たくさん解いて慣れるためにゲームイベントレベルアップ問題集も活用していきましょう!

そして力がついてきたなと思ったら冒頭でも紹介した「スキルチェック」で高ランクの問題に挑戦してみてください。




これからプログラミング学習を始めたいという方には、paizaラーニングがおすすめです。Python、Java、C言語、C#、PHP、Ruby、SQL、JavaScript、HTML/CSSなど、プログラミング未経験者や初心者でも動画で学べる入門レッスンを公開しています。

Python入門編」「C#入門編」「ITエンジニアの就活準備編」といった人気講座も完全無料となっておりますので、プログラミングを学びたい方・ITエンジニアを目指したい方はぜひごらんください。

詳しくはこちら
paizaラーニング

paizaのおすすめコンテンツ

Webセキュリティ入門 ハッカー入門 Webセキュリティ講座がスタート!CVは内田真礼さん! Python✕AI 機械学習入門講座 CVに上坂すみれさんを起用!人気の機械学習講座を公開中!
paiza転職 paiza新卒 EN:TRY paizaラーニング 記事内に記載している情報は、記事公開時点でのものとなります。 Copyright Paiza, Inc, All rights reserved.