HOME»応用情報技術者試験掲示板»令和4年春期午後問3 設問3の記述二題について
投稿する

令和4年春期午後問3 設問3の記述二題について [4299]

 さん(No.1) 
https://www.ap-siken.com/kakomon/04_haru/pm03.html
解説を読みましたが、理解できませんでした。
データ構造Zというのは要素数が80ある配列board×9個分あって、nが1の時boardを1〜80まで見ると0か1が表示される構造になるとい認識であっているでしょうか?
また、「入れる数字がなくマスを空白にして前に戻る場合、そのマスに数字を入れる前の状態のデータ構造Zが必要になりますが」←これはどうしてでしょうか?
また、そもそも入れる数字がない場合とはどういうことなのでしょうか?図1を見ると全てのマスに何らかの数字が入るのが答えになるため、「入れる数字がない場合」は存在しないように思えるのですが…
穴埋めはケアレスミス除きほぼ正解できましたが、この問題が理解できず困っております。
2023.07.05 18:47
boyonboyonさん(No.2) 
AP シルバーマイスター
ちょっと長くなりますが、問題例でz[x][n]を図3のかたちに合わせてかいてみます。
z[x][1]は、
000 000 000
000 001 001
000 100 100

100 001 000
010 000 000
000 000 000

000 000 100
110 000 101
000 000 000
1になっているところに1が入れられます。
・・・
z[x][4]は、
000 101 000
000 000 000
000 100 100

100 000 000
000 000 000
000 000 000

000 001 000
000 000 000
000 000 000
1になっているところに4が入れられます。
他の数字も同じようになります。

プログラムのトレースをします。
最初の空白のマスはzを参照すると3,8になります。
まず、3を入れます。次の空白のマスは、4,5になります。
①4を入れます。
②次の空白のマスは、入れられる数がありません。→「入れる数字がない場合」
③戻って、4の代わりに5を入れます。・・・・

①の後、z[x][4]は、
000 000 000
000 000 000
000 000 100

100 000 000
000 000 000
000 000 000

000 001 000
000 000 000
000 000 000
に更新されます。

③で、z[x][4]を元に戻したいのですが、戻すにはもう一度重複チェックをしないと戻せません。
101
000
100
の所です。
バックアップがあれば、すぐに戻すことができます。
2023.07.06 01:33
jjon-comさん(No.3) 
AP プラチナマイスター
> そもそも入れる数字がない場合とはどういうことなのでしょうか?

「入れる数字がない場合」という表現は問題文の次の箇所に登場します。

> (3): (2)で見つけた空白のマスに,1~9の数字を順番に入れる。
> (4-2) ルールにのっとっていない場合は,(3)に戻って次の数字を入れる。
> このとき,入れる数字がない場合には,マスを空白に戻して
> 一つ前に数字を入れたマスに戻り,(3)から再開する。

つまり、
1~9の数字を順番に入れてみたけれど、すべて「ルールにのっとっていない」
ことが判明した。だからもう「入れる数字がない」。
これはこの数独パズルにおいて、そのマスより前に別のマスに当てはめた
数字がまちがっていたことになり、そこからやり直すことになります。

----
> データ構造Zというのは要素数が80ある配列board×9個分あって、
> nが1の時boardを1~80まで見ると
> 0か1が表示される構造になるとい認識であっているでしょうか?

いいえ、間違っています。
図1 問題例 における次の■のマスを例に取ります。これはboard[9]です。

2□1
■4□2□□3□□
5□□







ここは空白マスなので、単純に発想するならば、
1~9 の9回ループを試みる総当たりのアルゴリズムになるのですが、

> 盤面の横1行,縦1列,及び太線で固まれた3×3の枠内
> の全てにおいて,1~9の数字が一つずつ入ること

という数独パズルのルールを知っているならば、
■は1,2,3,4,5,6,7ではない。
■は8,9のどちらかである。
ことが分かります。
この状態を Z[9][n=1~9] = [0,0,0,0,0,0,0,1,1] と表すための配列です。

----
> 「入れる数字がなくマスを空白にして前に戻る場合、
> そのマスに数字を入れる前の状態のデータ構造Zが
> 必要になりますが」←これはどうしてでしょうか?

前述の■を例に説明します。
8,9のどちらかであることが分かっていますから、
先に8を入れることで Z[9][n=1~9] = [0,0,0,0,0,0,0,0,1] となります。

「図2 図1の解答」を参照すると ■の解答は9になるとのこと。
となると8を入れた試みは失敗するので、
8を入れる前の元の状態に戻さねばなりません。
しかし Z[9][n=1~9] = [0,0,0,0,0,0,0,0,1] というデータからは
・ルール違反なのでその数字はダメという確定的な 0
・仮に8を入れてみたという暫定的な 0 
の両者を区別することができません。

なので、この問題では次の手段を取っています。

8を入れる前に
> A:データ構造Zを退避する (11文字)
より具体的に表現するならば、
盤面全体の数字候補の状況 Z[][] をゲームのセーブポイント機能によってまるごと取得し、スタックにpushして、またその状態に戻れるようにしておく。

8を入れた試みが失敗だと判明したのなら、board[9]に格納した8を空白マスに戻して、
> B:退避したデータ構造Zを取り出す (15文字)
より具体的に表現するならば、
あらかじめセーブしておいた、盤面全体の数字候補の状況 Z[][] をスタックからpopする。
(これにより Z[9][n=1~9] は [0,0,0,0,0,0,0,1,1] に戻る)そして、
> 戻ったマスで取得したリストの次の数字から再開する。
2023.07.06 01:57
jjon-comさん(No.4) 
AP プラチナマイスター
回答No.3の次の表現は,
> ゲームのセーブポイント機能によってまるごと取得し

「RPGゲームなどで進捗状況をいったんセーブして
  いつでもそこからゲームを再開できる機能のように」という比喩です。

この数独アルゴリズムのプログラムにセーブポイント機能が搭載されている,
と言っているわけではありません。念のため。
2023.07.06 08:37

返信投稿用フォーム

スパム防止のためにスレッド作成日から30日経過したスレッドへの書込みはできません。
© 2010-2024 応用情報技術者試験ドットコム All Rights Reserved.

Pagetop