〈論文〉SAS^(R) 言語で解く数独パズル
37
0
0
全文
(2) 第59巻. 第2号. 論. 1.序. 1.1は. じめ に. 我 々 は 数 独 パ ズ ル を 解 くSASプ. ロ グ ラ ム(SudokuSolvingSystem:SSS)(1)を. 開発 し. た。 数 独(日 本 の パ ズ ル 制 作 会 社 ニ コ リの 登 録 商 標)と は,9×9の る マ ス 目 に1∼9ま. 正 方 形 の 枠 内 の空 い て い. で の 数 字 を 入 れ る ペ ン シ ル パ ズ ル の 一 つ で,「 ナ ン バ ー プ レ イ ス(ナ. プ レ)」 と も呼 ば れ て い る 。 基 本 ル ー ル は 極 め て 単 純 で 以 下 の2つ. (1)空. い て い る マ ス 目 に1∼9の. (2)横. 列(「. 行 」),縦. ン. で あ る。. いず れ か の 数 字 を 入 れ る。. 列(「 列 」)及 び,太. 線 で 囲 ま れ た3×3の. ボ ッ ク ス(「 箱 」)内. に 同 じ数 字 が 複 数 含 ま れ て は い け な い 。. 図1.1に あ る9個. 例 題 を 示 す 。 そ の 解 答 の 図1.2に の マ ス 目 で1∼9の. 示 して い る よ う に,各. 全 て の 数 字 を 使 わ な け れ ば な ら ず,同. 「行 」 「列 」 「箱 」 に 一 グル ー プ内 で数 字 の. 重複 は許 され な い。. 遍. . .. 辺. 1. 2. 4. .. 8. 9. ン プ レ ポ ー タ ブ ル 』voLl,株. .. ■. 4 6 5 1 . 2 9 3 7. 5. 3. 1. 図1.2数. 7 11 6 4 9 8 3 逐 5 4 5 3 2 7 6 1 9 8 2 9 8 5 3 1 7 4 6. ■. 1. 圃. 8. 7 4 8. 3. 独問題. 1 4 2 δ 6 3 5 7 9. 4. 4 6. 3 5 6. 2. 2. 6 3 5 9 4 7 8 1 2 8 7 971 2 5 4 6 3 3 6 1 7 5 9 2 8 4. 18. 9. 3. 7. 6. 出 典:(『SUPERナ. 9 2 7 3 R. 5. 1. 8 6 7 図1.1数. 独解答. 式 会 社 ビ デ オ 出 版). (1)本 論 文 で 解 説 して い る数 独 プ ロ グ ラ ム は、 周 防 が 開発 を始 め、 途 中 で 知 平 菜 美 子(当 時学 部3 回生)が 参 加 し、 共 同 開 発 した。 そ の研 究 成 果 を2011年7月 に 開催 さ れ た 日本SASユ ー ザ ー総 会 2011で 、 知 平 ・周 防(2011)と 周 防 ・知 平(2011)の 二 つ の 論 文 発 表 を行 い、 知 平 は奨 励 賞 を受 賞 した。 そ の 二 つ の論 文 を統 合 して知 平 が 学部 卒 業 論 文 に ま とめ た。 そ の卒 業論 文 を周 防 が更 に加 筆 修 正 して 周 防 ・知 平(2012)と して 出版 した。 そ の 論 文 の英 語 版 を フ ロ リダ で 開 催 され たSAS GlobalForum2012で 招 待 論 文 と してSuoh(1912)を 発 表 した 。 本 論 文 は 周 防 ・知 平(2012)を 八 木 章 教 授 の退 職 記 念 号 用 に更 に改 稿 した もの で あ る。 132(530).
(3) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). 従 っ て,こ. の パ ズ ル で は,行,列,ブ. い くの で あ る が,SASで で き な い の で,本. ロ ッ ク の そ れ ぞ れ に,1∼9の. は 原 則 的 に 横 一 列,つ. 来SASで. テ ィ ン の 概 念 が な い 上 に,プ. ま りオ ブザ ベ ー シ ョン ご と に しか 計算 処理. 解 くに は 大 変 不 向 き な 問 題 で あ る。 更 に,SASに. は サ ブル ー. ロ グ ラ ム 全 体 を 繰 り返 し処 理 す る こ と も普 通 に は で き な い 言. 語 構 造 で あ る。 そ こ で 数 多 くのSASマ と し て 使 い,か. 数字 を当てはめて. つ,%include文. ク ロ を 定 義 し,こ. れ らを サ ブル ー テ ィ ンの代 用 品. で プ ロ グ ラ ム 全 体 を そ の 中 に 再 帰 的 に 組 み 込 む こ と で,同. じ プ ロ グ ラ ム を 繰 り 返 し実 行 で き る よ う に し た 。 そ の 結 果,極. め て 興 味 深 い 構 造 のSAS. プ ロ グ ラム にな った。 本 論 文 で は,そ. 1.2SSSの SSSで. 用 法 及 び 性 能 に つ い て 記 述 す る。. 開 発 か ら完 成 まで の 過 程. は 数 独 を 解 くた め に作 戦 ① ∼ ⑥ を 組 み 込 ん で い る。 こ れ ら の 作 戦 の 詳 細 に つ い て. は 第4節 SSSの. の プ ロ グ ラ ム 構 造 の 解 説,利. と 第6節. で 解 説 し て い る。. 開 発 は 作 戦 ① と ② か ら成 るSASプ. ロ グ ラ ム が 一 つ だ け の バ ー ジ ョ ン0か. た 。 こ の プ ロ グ ラ ム で は 初 級 問 題 を 解 く こ と が 出 来 た が,中 っ た 。 こ れ を 解 決 す る た あ に,マ た が,プ. ら始 ま っ. 級 問題 を解 くこ とは 出来 な か. ク ロ を 新 た に い くつ か 追 加 し て バ ー ジ ョ ン ア ッ プ を 計 っ. ロ グ ラ ム の コ ン パ イ ル の 時 点 で 解 決 で き な い 問 題 が 生 じ た 。 ロ グ画 面 の エ ラ ー メ. ッ セ ー ジ は 著 者 に は 意 味 不 明 で 理 解 で き な か っ た 。 恐 ら く,%incIude文 自 身 を 再 帰 的 に実 行 で き る よ う に し た た め,こ. で この プ ロ グ ラム. の プ ロ グ ラム の 中 で定 義 して い るマ ク ロを. 不 必 要 に何 度 も 定 義 し直 し て い る こ と か ら生 じ る ト ラ ブ ル と推 測 し た 。 従 っ て,こ 服 す る た め に,マ. れ を克. ク ロ の 定 義 部 分 と数 独 を 実 際 に 解 き に 行 く解 法 エ ン ジ ン の 部 分 を 分 離 し. て 別 々 のSASプ. ロ グ ラ ム に し て,バ. ー ジ ョ ン1を. 作 っ た 結 果,先. こ の 段 階 で,新. た に作 戦 ③ ④ ⑤ を 追 加 し た 結 果,イ. の トラ ブ ル は 解 消 し た 。. ン タ ー ネ ッ ト上 の 超 難 問 と い わ れ て い. る問題 を解 くこ とが 出来 る よ うに な った。 そ の 後 さ ら に イ ン タ ー ネ ッ ト上 に あ っ た 難 問 を10題 試 し て み る と,半 と が 判 明 し た 。SSSが. 分 しか解 け な い こ. 数 独 を 解 く際 に 手 が か り に す る マ ス 目 の 選 択 は,オ. リジナ ル 局 面 の. マ ス 目 の 配 置 に依 存 し て い る の で,必 ず し も,最 適 の マ ス 目 が 選 択 さ れ て い る訳 で は な い 。 そ こ で,オ. リ ジ ナ ル 局 面 を 右 に90度 ず つ 回 転 し て か ら解 答 す る ア ル ゴ リズ ム を 追 加 し,バ. ー ジ ョ ン1 .5を 作 成 し た 。 そ れ で も解 け な い 問 題 が2問 て バ ー ジ ョ ン2を. 残 っ た の で,新. た に作 戦 ⑥ を追 加 し. 作 成 し た 結 果,全 て の 問 題 を 解 く こ と が 出 来 る よ う に な っ た 。た だ,次 々. と マ ク ロ を 作 っ て 作 戦 を 追 加 し て い っ た 結 果,プ ロ グ ラ ム の 制 御 が 複 雑 に な りす ぎ た た め, 133(531).
(4) 第59巻. 第2号. こ の 段 階 で す べ て の 作 戦 を 整 理 ・統 合 す る こ と に し,こ て,新. れ ま で の作 戦 ① ② は そ の ま ま に し. た に作 成 し て 追 加 し た 新 作 戦 ③ か ら な る バ ー ジ ョ ン3を. ョ ン の 詳 細 に つ い て は 第6節. 作 成 した。 これ らの バ ー ジ. で 解 説 し て い る。. 本 節 と次 節 で は バ ー ジ ョ ン1を. 採 り上 げ て シ ス テ ム の 解 説 を 行 っ て い る が,本. 節 で解 説. し て い る基 本 的 な プ ロ グ ラ ミ ン グ は そ の 後 の バ ー ジ ョ ン で も 引 き継 が れ て い る。. 2.SASで. 2.1フ SASで. 数 独 を 解 く た め の2つ. の技法. ィル タ 数 独 を 解 く 際 の 問 題 点 は,SASで. は原 則 的 に は 同一 オ ブザ ベ ー シ ョン内 で の 演算. し か 行 う こ と が で き な い と い う 点 で あ る。 数 独 パ ズ ル の 性 質 上,行 グ ル ー プ に つ い て そ れ ぞ れ 演 算 を 行 い,解. ・列 ・箱 と い う3つ. き進 め て い か な くて は な ら な い 。SSSで. の. は,問. 題 を 解 き始 め る前 に 問 題 の 初 期 局 面 を 表 現 し て い る デ ー タ セ ッ トか ら行 ・列 ・箱 ご と に 計 算 処 理 が 容 易 に で き る デ ー タ セ ッ トを 作 成 し,こ. れ ら の グ ル ー プ の 処 理 結 果 を 合 成 し て,. 各 マ ス 目 の 候 補 ナ ン バ ー を 見 つ け る方 法 を 採 用 し た 。 そ の た め に 「フ ィ ル タ」 と い う概 念 を導 入 した。 SSSで. は 始 め に マ ス 目毎 に 対 応 す る 数 値 変 数fiIter(最. 大9桁. 手 が か り に し て 正 解 の 数 字 の 特 定 し て い く。つ ま り こ のfiIterは ー と な る最 も 重 要 な 情 報 で あ る. 。 具 体 的 に は,filterは. の 整 数)を 作 成 し,そ. 数 独 を 解 く際 の 思 考 の キ. 空 いて い るマ ス 目が 所 属 す る行 ・. 列 ・箱 の グ ル ー プ の い ず れ か で 既 に 使 用 さ れ て い る数 字 を 使 っ て 最 大9ケ し た も の で あ り,そ … κ. g]と 表 さ れ,κ. れを. タ の整 数 で表 現. の 中 に 含 ま れ て い る 数 字 は そ の マ ス 目 で は 使 え な い 。fiIterは[κ1κ2 、-0ま. た はi(1≦i≦9の. 整 数)と. 「123406780」 の 場 合,こ の 中 に含 ま れ て い な い5と9が. な る。 例 え ばfilterの. 値が. そ の マ ス 目 の 候 補 ナ ン バ ー に な る。. 2.2再. 帰 的 プ ログ ラ ミン グ. SSSで. は,い わ ゆ る ゲ ー ム 木 の 探 索 を す る た め の 専 用 の プ ロ グ ラ ム は 組 み 込 ま ず に,「 再. 帰 的 プ ロ グ ラ ミ ン グ」 を 採 用 し た 。. 2.2.1一. 般 的 な 再 帰 的 プ ロ グ ラ ミ ン グ技 法. 下 の プ ロ グ ラ ム で は 再 帰 的 処 理 の 例 で よ く使 わ れ る 階 乗 計 算 を,再 を 使 っ てSASで. 記 述 して み た。 134(532). 帰 的 プ ロ グ ラ ミン グ.
(5) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). /*factoriaI-set-initial'sas*/. プ ログ ラ ム①1. optionsmPrintnoGenter;. '. %letNニ4;*CaIGulateN!;. datafactoriaI;f=&N;run;procprint;titIe"lnitialvaIueN=&N";run;. %macrofaGtorial; %letN=%evaI(&N-1); datafactorial;setfactorial. ;fニ&N*f;run;. procprint;title"Nニ&N";run;. %if&N=2%then%abort; %include"C:¥SAS_Forum¥2011¥recursive¥factorial.sas"; %mend;. /*factorial.sas*/ %factorial;. こ の 例 で は4の fに4を. プ ログ ラム②. 階 乗 を 求 め て い る。 プ ロ グ ラ ム ① で ま ず デ ー タ セ ッ トfactorialの. 初 期 セ ッ ト し,か. つ,マ. ク ロfactorialを. ラ ム ② で 行 わ れ る。 マ ク ロfactorialの factorial.sasを. 中 で%includeを. 使 っ てSASプ. ログ ラ ム. ロ グ ラ ム ① の 下 線 部 の2行. が 繰 り返. で 計 算 さ れ た 直 後 に 収 束 条 件 で あ る 「マ ク ロ 変 数Nが2」. あ る こ と を チ ェ ッ ク し て,%abortに. 変数. 定 義 し て お く。 後 の 計 算 処 理 は プ ロ グ. 再 帰 的 に 組 み 込 む こ と に よ っ て,プ. し実 行 さ れ る。4×3×2ま. Nの. ≡. で. よ って 強 制 的 に実 行 を 終 了 させ て い る。 これ が な い と. 値 が ど ん ど ん 一 ず つ 小 さ く な っ て 掛 け 算 を 繰 り返 す 無 限 ル ー プ に 陥 る 。 こ の 例 で は プ. ロ グ ラ ム ② の 構 造 が 極 あ て 簡 単 で,再. 帰 的 実 行 に よ っ て マ ク ロ展 開 し た プ ロ グ ラ ム は 全 て. 実 行 し 終 わ っ て い る。 以 下 に実 行 ロ グ と実 行 結 果 を 示 す 。. 135(533).
(6) 第59巻 一''''''"ヲロ'グ ヲ 云 ②'め. 実 行'Ei'グ''"てNOTE行. 第2号. 省 略y''''''"1. プログ ラム① の実 行結 果 1nitialvaIueN=4 18/*factorial.sas*/. 0BSf. 19%factorial; MPRlNT(FACTORIAL)datafactorial;. 14. MPRlNT(FACTORlAL)setfactoriaI; MPRlNT(FACTORIAL)f=3*f; MPRlNT(FACTORlAL)run;. 1_._ズ. MPRlNT(FACTORlAL):procprint;. ロ互 乏 ム ②Q黒. 儲. 責塁.......1. N=3. MPRlNT(FACTORlAL):titIe"N=3"; MPRlNT(FACTORIAL):run;. 0BSf MPRlNT(FACTORlAL)datafactoriaI;. 112. MPRlNT(FACTORIAL)setfactorial; MPRlNT(FACTORlAL)f=2*f; MPRlNT(FACTORlAL)run;. N=2. MPRlNT(FACTORlAL):procprint;. 0BSf. MPRlNT(FACTORlAL):titIe"N=2";. 124. MPRlNT(FACTORlAL):run;. ERROR:%ABORTス. テ ー. トメ ン. トに よ っ て 、. 実 行 が 中 止 さ れ ま し た 。. 2.2再. 帰 的 プ ログ ラ ミン グ技 法. SSSの. 実 行 は 以 下 に 示 すSASプ. ロ グ ラ ムpuzzIe. _soIve_finaI.sasを. こ と に よ っ て 行 わ れ て い る。 こ こ で は バ ー ジ ョ ン1のSSSを こ の プ ロ グ ラ ム(バ ー ジ ョ ン1)で. は 以 下 の4つ. 使 って解 説 して い る。. の 処 理 を行 って い る。. (1)複. 数 の マ ク ロ変 数 の 設 定. (2)探. 索 対 象 のSASデ. (3)実. 行 ロ グ(LOG画. (4)数. 独 解 法 エ ン ジ ン に 相 当 す る マ ク ロ 「aII」 の 実 行. 上 の 処 理(2)で,各. 再 帰 的 に実 行 す る. ー タ セ ッ トORIGINALを. 別名で保存. 面 情 報)や 実 行 結 果(OUTPUT画. 面 情 報)を 外 部 フ ァ イ ル に 出 力. 作 戦 適 用 後 に 新 た に確 定 で き た マ ス 目 が 見 つ か っ た か ど う か を チ ェ. ッ ク す る 際 の 比 較 対 象 と な る 元 の デ ー タ セ ッ トを 別 名 で 保 存 し て い る。 SSS(バ. ー ジ ョ ン1)に. お け る 処 理(4)に. 中 で 使 わ れ て い る マ ク ロ の う ち,作. 相 当 す る マ ク ロ 「aII」 の 定 義 を 以 下 に 示 す 。 こ の. set _second,作. 戦. ⑤. 戦 ② のrepeat,作. のoperation5とmake_operation5の. puzzle_solve_final.sasは%incIudeを に あ る マ ク ロselectlor2の. 中 でSASプ. 中 に 組 み 込 ま れ て い る 別 の マ ク ロonce. 下 に 示 す マ ク ロset_secondで. 戦 ④ の ロ グ. 使 っ て 再 帰 的 に 実 行 さ れ て い る 。 ま た,作. puzzle_solve_final.sasが%incIudeで 例 え ば,以. 戦 ⑧ のonce_again3,作. _again4の. ラ ム. 戦 ④ の 中 中 で も. 再 帰 的 に使 わ れ て い る。 は 136(534). 「%include&run_solve」. が そ の再 帰 的使 用.
(7) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防) を し て い る個 所 で あ る。 そ の 結 果,図2.1に. 示 す よ う な マ ク ロ 展 開 が 行 わ れ る 。 そ の 図 に あ る右 端 の 図 で 示 す よ. う に,「 こ こ で 正 解 が 見 つ か る 」 と い う個 所 で 正 解 が 得 られ た 場 合 は,そ. の下 に残 って い る. プ ロ グ ラ ム は不 要 とな る の で 実 行 せ ず に 直 ち に プ ロ グ ラ ム の 実 行 を 中止 す る。 こ の制 御 は%abort命 ERRORメ. 令 を 使 う こ と で で き る 。 前 節2.2.1に あ る 実 行 例 に 示 す 実 行 ロ グ に あ る よ う に, ッ セ ー ジ が 出 る が,こ. の 場 合 は 「正 常 終 了 」 で あ る 。. /*puzzle_solve_finaLsas*//*バ. ー ジ ョ ン1*/. *Beforethisprogramisrun, "puzzle _make_originaI_data.sas"mustberun. oPtionsmprintSPOOL;. %letloop_no=15;*各 *以. 局 面 の 繰 り返 し 回 数 の 上 限 を 指 定 し て く だ さ い;. 下 は 設 定 不 要;. %Ietstar=*;/*blank=VaIidODS,"*"=StoPODS;*/ %letround=%eval(&round+1); %letfound=0; %letwrong=0;/*0=NotWrongAnswer,1=WrongAnswer*/ %Ietnew_round=%evaI(&new_round+1);. data; if×w=Othendo; starttime=TIMEO;putstarttime=time. /*現. 在 日 時 をSAS日. 付 値 で 返 す*/. CalISympUt("Starttime",Starttime); end; run; %Iettime_SW=1;. dataoriginal _before; *thisdatasetwillbecomparedwith"new"originalatthebottom; SetOriginal; run; odsIistingGIose; odshtmlfile="&output¥ROUND&round.. _&which.. _&new_which._&operation5_no._&set5_no..xIs"; procprintdata=original; titIe"ROUND&round:&new. _round.data=originaI";run;. odshtmlcIose; odslisting; PROCPRINTTOlo9="&lo9¥logROUND&round._&which._&new_whiGh. _&operation5_no._&set5_no..txt"NEW;RUN; PROCPRINTTOprint="&lo9¥outputROUND&round._&which,_&new_whiGh. _&operation5_no._&set5_no..txt"NEW;RUN; %all;*解. 法 エ ン ジ ン;. 137(535).
(8) 第59巻. %macroset_second;%*作. 第2号. 戦 ④ へ の 移 行 の た めORIGINAL1を. %if¬_yet=0%then%output;%*す. セ ッ. トす る;. べ て の マ ス 目 に 正 解 済 み;. %else%do; %if&operation5=1%then; %eIse%do; %if&which=5AND&new_which=0 %then%do;%IetwhiGh=1; %set_operation4_3(original_&which); %include&run_solve; %end; %end; %end; %mendset_seGond;. 138(536).
(9) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). ー. 実 行 の必 要 な し. 図2.1%includeに. 3.SSS(バ. 本 節 で は,SSSの バ ー ジ ョ ン1に. よ る マ ク ロ展 開 図. ー ジ ョ ン1)のSASプ. ログ ラム の解 説. 初 期 の 開発 段 階 で作 成 した. つ い て 解 説 を す る。 バ ー ジ ョ ン. 3ま で 開 発 を 終 了 し た 現 時 点 で は,そ. れ以 前 の. バ ー ジ ョ ン は 不 要 に な っ た と言 え る が,そ. れ ら. の バ ー ジ ョ ン か ら 多 くの こ と を 学 ん だ 結 果,今 の バ ー ジ ョ ン3の. 開 発 が 可 能 と な っ た 。従 って,. ま ず 最 初 に バ ー ジ ョ ン1の. 解 説 を す る こ とは き. わ あ て 意 義 深 い と考 え る。. SSS(バ. ー ジ ョ ン1)は. 次 の4つ. のプ ログラム. か ら な る。. 図3.1SASデ. ①sudoku_macro.sas ②puzzle_make_originaLdata.sas ③puzzle_solve_final.sas ④reCOnStrUCt.SaS こ の 節 で は こ れ ら の プ ロ グ ラ ム の 詳 細 に つ い て 記 述 す る。. 一139(537)一. ー タ セ ッ ト作 成 手 順.
(10) 第59巻 3.1デ. 第2号. ー タ表 現 方 法. ま ず,SASで. 数 独 を 解 くた め に は,図3.1に. 示 す 様 に,問. 題 を 入 力 し必 要 なSASデ. ー. タ セ ッ トを 作 成 す る。 は じ め に,9行9列 問 題 は 図3.2(上. の 初 期 局 面 を テ キ ス トフ ァ イ ル に 入 力 す る 。 例 え ば,先. の 図1.1の. 段 中 央)に 示 す よ う に テ キ ス トエ デ ィ タ で 作 成 す る 。 「0」は 空 い て い る マ. ス 目 を 表 す 。 こ の テ キ ス トフ ァ イ ル をSASデ. ー タ セ ッ ト(ORIGlNAL:9変. ー シ ョ ン)に 変 換 す る 図3 .2(上 段 右)。 こ の 処 理 は 上 記 の ②puzzIe. 数 ・9オ ブ ザ ベ. _make_originaLdata.sas. で 行 わ れ る。空 い た マ ス 目 に 数 字 が 確 定 さ れ る た び にORIGINALに. 追 加 さ れ,次. の処 理 に 引. き 渡 さ れ る。 こ のORIGINALか. ら,81個. の 全 て の マ ス 目 の 位 置 情 報(行. 数 字 の 値 を 変 数 と す る デ ー タ セ ッ トCELL(81オ 央)。 各 マ ス 目 の 箱(box)番 号(j)か らSAS関. 号 は 図3.2(下. 番 号,列. 番 号,箱. 番 号)と. ブ ザ ベ ー シ ョ ン)を 作 成 す る 図3.2(下. 段 右)に 示 す 。 こ の 箱 番 号 は,行. 段 中. 番 号(i)と 列 番. 数 を使 って以 下 の計 算 式 で求 め る こ とが で き る。. 箱 番 号=max(int((i-1)/3),0)+int((j-1)/3)+2*int((i-1)/3)+1 こ のCELLを て,そ. 使 っ て,同. れ ぞ れ3つ. 図3.2に. の デ ー タ セ ッ トROW,COL,BOXに. あ る こ の4つ. ロ グ ラ ム はsudoku. 保 存 す る 図3.2(下. の デ ー タ セ ッ トは ④reconstruct.sasに. _macro.sasの. all _filterとverifyの 自動 的 に こ の4つ. 一 の 行 ・列 ・箱 に属 す る セ ル を 同 じ オ ブ ザ ベ ー シ ョ ン に ま と め. よ り作 成 さ れ る 。 こ の プ. プ ロ グ ラ ム の 中 で 定 義 さ れ て い るSASマ. 中 で%includeで. 組 み 込 ま れ て お り,ORIGINALが. の デ ー タ セ ッ ト も更 新 さ れ る。. 140(538). 段 左)。. ク ロ の う ち,. 更 新 さ れ る た び に,.
(11) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). 000801000. R1 '. 臼. q. 3. 6. 54. ア. .. 2 .. .5. .. ■1. 蛙. 2 4 3. 5. 1. 2 1. 占 42. 止 直. 1. OBS. 006030900. 7. 一. a2. a3. a4. a5. a6. a7. a8. a9. 0. 0. 8. 0. 1. 070000030. 0. 0. 0. 0. 2. 0. 0. 6. 0. 3. 0. 9. 0. 0. 607000504. 3. 0. 7. 0. 0. 0. 0. 0. 3. 0. 000206000 200070008. 4. 6. 0. 7. 0. 0. 0. 5. 0. 4. 5. 0. 0. 0. 2. 0. 6. 0. 0. 0. 6. 2. 0. 0. 0. 7. 0. 0. 0. 8. 000405000. 7. 0. 0. 0. 4. 0. 5. 0. 0. 0. 308000402. 8. 3. 0. 8. 0. 0. 0. 4. 0. 2. 9. 0. 1. 0. 3. 0. 9. 0. 8. 0. ■1. OlO309080. 数独 問題. a1. 1. 1. デ ー タ セ ッ トORIGINAL. テキス ト ROW. フ ァイ ル. OBS 1. a1. a2. ・巫暉. 3. a6. a7. 8. a9. n. nn. R. ∩. 1. n. r. 21. n. n6. o. 3. o. 9. n. `. 3 4. 0. 70. 0. 0. 0. 0. 3. 0. 6. 07. 0. 0. 0. 5. 0. 4. 5. 0 2. 00 00. 2 0. 0 7. 6 0. 0 0. 0 0. 0 8. 0. 00. 4. 0. 5. 0. 0. 0. OBS. 3 0. 08 10. 0 3. 0 0. 0 9. 4 0. 0 8. 2 0. 1. 6 7 8 9. n. 2. 1. 2. 3. 1. 3. 4. 1. 4. 5. 1. 6. 1. 7. COL OBS 1. a1. a23. a4. a5. a6. a78 03. ㊥㊥国. a9. 1111112121213133■. 5 6. 2. 444555666. 1. 7. 3. ♂騨. 6. 0. 2. 2. n. ∩. 7. n. n. ∩. rn. 1. 3 4. n. A. n. 7. n. n. nq. r 1. 8. 1. 8. 8 0. 0 3. 0 0. 0 0. 2 0. 0 7. 40 0. 9. 1. 9. 0. 3 0. 1. 0. 0. 0. 6. 0. 5. 0. 9. 10. 2. 1. 7 8. 0 0. 0 3. 5 0. 0 0. 0 0. 0 0. 4 0. 0 8. 2. 2. 12. 2. 3. 9. 0. 9 0 1 0. 11. 0. 4. 0. 8. 0. 2. 0. 13. 2. 4. 14. 2. 5. 15. 2. 6. 16. 2. 7. 17. 2. 8. 18. 2. 9. 5 6. BOX OBS. a1. a2. a3. a4. a5. a6. a7. 8. a9. 1 2 3. 0. 0. 0. 0. 0. 7. 0. 6. 0. 8 0. 0 9. 0 0. 0 0. 3 0. 0 3. 1 0. 0 0. 0 0. 4 5. 6 0. 0 2. 2 0. 0 0. 0 0. 0 7. 7 0. 0 6. 0 0. 6 7 8. 5 0. 0 3. 0 0. 0 0. 0 1. 4■. 0. 8 0. ノ1. ∩. つ. 0 0 nI. n. `. 9. n. 4n. o. o. 9. r 1. 1. In. n R. Il. .攣 ' 1. ψ. 一 一. 0 3. 一0. 1一〇 1 一0 1 一6. 111222333 111222333 444555666 444555666 777888999 777888999 777888999. 2 一0 2 一3. box番. 号. 2 一0 3 一9 3 一0 3 一0. デ ー タ セ ッ トCELL 81オ. ブ ザ ベ ー シ ョンの う ち. 最 初 の18オ. 図3.2数. 3.2プ. V. 冤. 1 一0 2 一8 2 0. 0. 0. 一 1一 1 一0. ブザ ベ ー シ ョンだ け表 示. 独パズルのデータ表現. ロ グ ラ ム の 構 造(バ ー ジ ョ ン1). SSS(バ. ー ジ ョ ン1)を 構 成 す る4つ. のSASフ. ゜ロ グ ラ ム の 関 係 は 図3.3に. 示 す 通 りで あ る。. ①sudoku_macro.sas こ こ に は 数 独 の 解 法 に必 要 な ア ル ゴ リズ ム が 役 割 別 にSASの お り,39個 録1に. の マ ク ロ を 定 義 し て い る。 バ ー ジ ョ ン1で. 示 す 。 利 用 者 は こ の プ ロ グ ラ ム の 冒 頭 で%letに. マ ク ロ言 語 で 記 述 さ れ て. 使 用 し て い る マ ク ロ変 数 の 一 覧 を 付 よ っ てSSSを. プ ロ グ ラ ム を 保 存 す る ドラ イ ブ 名 を 指 定 す る。 こ の プ ロ グ ラ ム はSASセ 一141(539)一. 構 成 す る4つ. のSAS. ッ シ ョンの始 め.
(12) 第59巻. 第2号. に 一 度 実 行 す る だ け で よ い 。 こ れ ら の マ ク ロ の 実 行 は 以 下 で 解 説 す る puzzle_solve_final.sasに. お いて 行 わ れ る。. (START ). ●. SSSを. 保 存 す る ドラ イ ブ 名 を. 指定 ●. 解法 に必要 な全 ての マク ロを. ■ ■ ■ ■ ■ ■ ■. ①sudoku_macro.sas. 定義 マ ク ロ の 中 で%includeに. ●. よ っ. て ④reconstruct.sasが. 実 行. され る. L 7. ●%letで. 解 き た い数 独 問 題 の テ. キ ス トフ ァイ ル 名 の 指 定. ②puzzle_make_originaLdata.sas. ●Xコ. マ ン ドを 使 っ て 必 要 な フ ォル ダ を 自動 作 成 デ ー タ セ ッ トORIGINALを. ●. 作成. ●%letで. マ ク ロ変 数Ioop _noを 設定 正 解 が 出 るか 、あ る い は最 後 の. ■ ■ ■ ■ ■ ■ ■. ③puzzle_solve_final.sas. ●. 候補 の局面 が制 限回数 を超 え るま で 実 行 され る YE. 別 の 問題 を 角翠くカ・ど うか?. NO. (END ) 図3.3プ. ログ ラ ム 実行 手 順. ②puzzle_make_original_data.sas こ の プ ロ グ ラ ム で は 解 こ う と す る数 独 問 題 を あ ら か じ め テ キ ス トエ デ ィ タ で 作 成 し た テ キ ス トフ ァ イ ル を 読 み 込 ん で,デ 冒 頭 で%letに. ー タ セ ッ トORIGINALを. 作 成 す る 。そ の た あ に プ ロ グ ラ ム. よ っ て そ の 数 独 問 題 の テ キ ス トフ ァ イ ル 名 を 指 定 す る(拡 張 子 は 指 定 し な く. て よ い)。 ま た,こ sudoku _macro.sasで. の プ ロ グ ラ ム の 中 でXコ 指 定 した ドラ イ ブ(例. マ ン ド を 使 っ て,DOS命. え ばCド. ラ イ ブ)に,次. の2つ. 令 が 実 行 さ れ, の フ ォル ダ が 自. 動 的 に新 規 作 成 さ れ る。. (1)OUTPUT画. 面 に 出 力 さ れ る 情 報 の う ち,ODS機. る 情 報 を 格 納 す る フ ォル ダ(¥sudoku¥output. 142(540). 能 を 使 ってhtml形. _window). 式 で 出力 され.
(13) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). (2)LOG画. 面 の 全 情 報(Iog.txt),及. び(1)以 外 のOUTPUT画. 面 の 情 報(output.txt). を 保 存 す る た あ の フ ォル ダ(¥sudoku¥Iog_window). 一 般 的 にSASプ. ロ グ ラ ム を実 行 す る と. ,ロ グ 情 報 がLOG画. 画 面 に 表 示 さ れ る。SSSの. 面 に,計 算 処 理 結 果 がOUTPUT. 実 行 を こ の 通 常 の 方 法 で 行 う と,%include文. グ ラ ム を 書 き加 え て い くの で,LOG情 告 情 報 が 頻 繁 に 出 現 し て,実. 報 の 量 が 表 示 限 度 を 軽 く超 え て し ま い,あ. 行 の 中 断 が 起 き る。 し か しLOG情. ダ の 中 に外 部 の テ キ ス トフ ァ イ ルIog.txtと. 使 っ て 上 の(2)の. 確 認 の た め 必 要 と な る。 そ の 情 報 の 中 に は,数. る情 報 も あ る。 ま た,SSSの. フ ォル. し て 自動 的 に 出 力 ・保 存 し て い る。. 面 に 表 示 さ れ る 処 理 途 中 の デ ー タ セ ッ トの 情 報 も,プ. か の 局 面 だ け を 別 個 保 存 し て,数. ふ れ の警. 報 は プ ロ グ ラム 開 発 中 は貴. 重 な デ ィ バ ッ グ用 情 報 と し て 不 可 欠 で あ る の で,procprinttoを. OUTPUT画. で何 度 も同 じ プ ロ. ロ グ ラム 開発 中 は動 作 の. 独 を 解 い て い る 際 の ポ イ ン ト と な る い くつ. 独 解 法 の プ ロ グ ラム実 行 中 の進 行 状 況 を容 易 に確 認 で き. エ ン ドユ ー ザ の 立 場 で は,途. 結 果 の 解 答 だ け を 見 た い 場 合 も あ る。 従 っ て,OUTPUT画. 中 結 果 は 重 要 で は な く,最 後 の 面 の 情 報 は3種. 類 の 異 な る形 で 保. 存 し て い る。 解 法 の 際 の 局 面 の 進 行 状 況 を 確 認 で き る情 報 は,上 保 存 す る 際 は,マ. の(1)に. ク ロ変 数round,which,new_whichの. ど の タ イ ミ ン グ で 作 成 さ れ たOUTPUT画 「round5 _4_3.xls」(実. 際 はhtmlフ. 保 存 して い る 。htmI形. 値 を フ ァ イ ル 名 に使 い,実. 式で 行 中の. 面 情 報 で あ る か が 分 か る よ う に した 。 例 え ば. ァ イ ル)は マ ク ロ 変 数round=5,which=4,new_which=3. の 際 に 出 力 し た 局 面 を 表 し て い る。 こ の 局 面 は ラ ウ ン ド5を 実 行 中 に 現 れ た 局 面 で あ る こ と が 分 か る。whichとnew. _whichは. た め に使 用 し て い る変 数 で,新. 作戦 ③ と作戦 ④ にお い て そ れ ぞ れ候 補 局 面 を設 定 す る. し く局 面 を 設 定 す る と1増. え る の で,実. 1少 な い 値 の 時 に 出 現 し た こ と を 意 味 す る。 つ ま り,which=3(作 ら 更 に作 戦 ④ に進 ん だ 時 のnew _which=2(作 最 終 結 果 の 解 答 だ け は,OUTPUT画 は(2)の. フ ォ ル ダ にoutput.txtと. 面(3.3節. 図3.4)に. 戦 ③ の 第3番. 目 の 局 面)か. 目 の 局 面)を 表 示 し て い る 。 直 接 表 示 して い る 。 そ の 他 の 情 報. して保 存 した。. こ れ ら最 終 的 な 解 答 以 外 のOUTPUT情 が 設 定 す る こ と が で き,出. 戦 ④ の 第2番. 際 は そ の数 字 か ら. 報 とLOG情. 報 を 出 力 す る か ど う か は エ ン ドユ ー ザ ー. 力 し な い と設 定 す れ ば 解 答 に 至 る ま で の 実 行 時 間 を か な り短 縮. す る こ と が で き る。. 143(541).
(14) 第59巻. 第2号. ③puzzle_solve_final.sas こ の プ ロ グ ラ ム の 冒 頭 の%letで. マ ク ロ 変 数Ioop. し な い 場 合 の デ フ ォ ル ト値 は15と. _noを. ユ ー ザ ー が 設 定 す る 。敢 え て 設 定. し て い る。 こ の マ ク ロ変 数Ioop. _noの. 値 は 各 局 面 にお い. て こ の プ ロ グ ラ ム の 実 行 を 再 帰 的 に 繰 り返 す 回 数 の 上 限 値 を 意 味 し て い る。 こ の 値 が 小 さ す ぎ る と,正. 解 に近 づ い て い る に も か か わ ら ず,回. 能 性 が あ る。 実 際 に数 独 をSSSに. 解 か せ た 実 験 結 果 か ら デ フ ォ ル ト値15あ. え る。 た だ し こ の マ ク ロ変 数 は 第6節. で 解 説 す る バ ー ジ ョ ン3で. こ の プ ロ グ ラ ム の 冒 頭 で は,%evaI関 自動 的 に1ず. 数 制 限 の た め に 途 中 で 打 ち切 ら れ る可 た り が 妥 当 と考. は不 要 に な った。. 数 に よ っ て マ ク ロ 変 数new _roundとroundの. つ 増 や さ れ る。 マ ク ロ変 数new_roundは. この プ ロ グ ラム の実 行 の 開始 か ら終. 了 ま で に こ の プ ロ グ ラ ム が 繰 り返 し実 行 さ れ た 総 回 数 で あ り,マ. ク ロ変 数roundは. 局 面 か ら数 え て こ の プ ロ グ ラ ム を 繰 り返 し実 行 し た 回 数 を 表 し て い る。 第4節 戦 ③ や 作 戦 ④ で 探 索 の 対 象 と な る複 数 の 候 補 局 面(正. で 述 べ る作 正解 の. し て セ ッ トす る度 に こ の マ ク ロ変. リ セ ッ トさ れ る 。. こ の プ ロ グ ラ ム は%includeに. よ っ て 自 動 的 に 繰 り返 し実 行 さ れ る の で,各 局 面 に お い て. 無 限 ル ー プ に 陥 ら な い よ う に再 帰 的 に 実 行 を 繰 り返 す 回 数 を マ ク ロ変 数roundで き,そ. 各候 補. 解 の 局 面 か も し れ な い し,不. 局 面 か も し れ な い)を そ れ ぞ れ デ ー タ セ ッ トORIGINALと 数roundは0に. 値 も. の 値 がIoop. _noの. 値 を 超 え る と そ れ 以 上 の 探 索 は 中 止 し て,次. に移 る。 従 っ て こ の プ ロ グ ラ ム の 実 行 が 始 ま る と,正. 解 が 出 る か,あ. 数 えてお. の候 補 の 局 面 の探 索 るい は最 後 の候 補 の. 局 面 か ら数 え て 再 帰 的 実 行 の 回 数 が 制 限 回 数 を 超 え る ま で 自動 的 に 繰 り返 し実 行 さ れ る。. ④reCOnStrUCt.SaS こ の プ ロ グ ラ ム は,引 ROW,COL,BOXを. 作 成 す る 。 こ の プ ロ グ ラ ム は ①sudoku. alLfiIterとverifyの. 3.3プ. き 渡 さ れ た デ ー タ セ ッ トORIGINALか. 中 で%includeに. ロ グ ラ ム(バ ー ジ ョ ン1)の. SSS(バ ー ジ ョ ン1)を. (1). sudoku. ら4つ. _macro.sasの. の デ ー タ セ ッ トCELL 中 に あ るSASマ. ク ロ. よ り 自動 的 に 組 み 込 ま れ て 実 行 さ れ る。. 利用法. 利 用 す る時 の手 順 を以 下 に示 す。. _macro.sasの. 冒 頭 で%letで. プ ロ グ ラ ム を 保 存 す る ド ラ イ ブ 名 を 指 定 後,. サ ブ ミ ッ トす る 。. (2). puzzle_make_original_data.sasの ル 名(拡. 張 子 不 要)を. 指 定 し,サ. 冒 頭 の%letで,数. 独 問題 の テ キ ス. ブ ミ ッ トす る 。(デ. ー タ セ ッ トORIGINALが. 成 さ れ る 。). 144(542). トフ ァ イ 作.
(15) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防) (3)puzzle_solve_final.sasの. 冒 頭 で%Ietに. ブ ミ ッ トす る 。loop _noは. 上 記 の(1)∼(3)を. 行 っ た 後,正. れ る(図3.4左)。. よ り マ ク ロ 変 数loop_noを. 解 が 得 ら れ れ ば,OUTPUT画. 正 解 が 得 ら れ な か っ た 場 合 は,途. 局 面 を 作 る直 前 の 局 面,つ れ る(図3.4右)よ. 面 に正 解 の 最 終 局 面 が 表 示 さ. 中 結 果 と し て,作. 戦 ③ で複 数 の候 補. ま り正 解 で あ る と確 定 し て い る数 字 の み が 入 っ た 局 面 が 表 示 さ. う に は な っ て い る が,こ. 際 に現 れ た も の で,最. 設 定 後,サ. 設 定 しな け れ ば デ フ ォ ル ト値15が 設 定 さ れ る 。. の 画 面 表 示 は開 発途 中 の バ ー ジ ョンの 実 行 の. 新 バ ー ジ ョ ン で は 溶 け な い 解 け な い 数 独 問 題 は な い の で,出. 現 しな. い は ず で あ る。 引 き 続 き 別 の 数 独 問 題 を 解 く場 合 は(2)と(3)を. ここまで しか出来ませんで した. O 6 0 9 0 0. ー ジ ョ ン1)の5つ. O. 7. は5種. 0. ー ジ ョ ン1)で. 0. 0. 2. SSS(バ. 0. 0. 1. 4.SSS(バ. 3 0. 解 け な い 問題 の実 行結 果 のOUTPUT画 行 結 果 のOUTPUT画. O. 0. 8. 図3.4実. 面. 0. 0 0. 9 a O. 4. 7. 図1.1の 問題 の実 行 結 果 のOUTPUT画. 0 0. 0. 9. 3. 8. 5. 5. 2. 8. O. 9. 6. 7 a O. 4. 9. 8. 5 9. 7. 6. 0. 7. 0 0. 3. 2. 0. 1. 3. 7. 5. 5. 0. O. 6. O. 8. 6 a O. 6. 0. 0. 0. 3. 1. 2 0. 0. 1. 0. 6. 4. 3. 0. 0. 8. 1. 5. 4. 7. 9. 4. 9. 0. 5. 3. 8. 4. 7. 0. 7. 4. 2. 3. 0. 0. 2. 5. 6. 7. 1. 6. 8. 0. 0 5. 5. 3. 5 a O. 9. 2. 6. a8. 3. 0. 4. 1. 3. 9. 9. 7. 2. 6. 5. 8. a4. 4. 2. 9. 2. 0. 0. 1. 5. 4. a2. 3. 7. 8. 1. 5. 1. 0. 3. 6. 4. 7. 0. 9. 4. 0. 7. 1. 2. 0. 6. 7. 1. 0. 2. 5. 4. 3. OBS. 3 a 5. 2. a9. 0. 8. a8. 0. 3. a7. 8. 9. a6. 3. a4. 8. a3. a O. a 5. 1. a2. 5 a 6. 正解が得 られました OBS. 繰 り返 す 。. 面. 面. の作 戦 の解 説. 類 の 作 戦 ① ∼ ⑤ を 採 用 して い る 。 こ の う ち 作 戦 ① と ② で は,. い わ ゆ る ゲ ー ム 木 を 探 索 せ ず に直 ち に 新 し い 数 字 を マ ス 目 に 確 定 で き る。 実 行 す る作 戦 は 図4.1に. 示 す よ う に,作. 戦 ① か ら順 次 適 用 し て い き,そ. の 結 果,新. しい マ ス 目 に数字 を確. 定 す る こ と が で き な か っ た 場 合 に は 次 の 作 戦 に 移 る。 そ こ で 新 た に 確 定 で き る数 字 を 見 つ け た 場 合 は 次 の 作 戦 に移 ら ず,デ. ー タ セ ッ トORIGINALを. に戻 っ て 実 行 す る よ う に設 計 し た 。 な ぜ な ら ば,新 る こ と に よ っ て,そ. ア ッ プ デ ー ト した 後,再. び作 戦 ①. た に 確 定 で き た マ ス 目 が1つ. で も増 え. の 情 報 が 他 の 行 ・列 ・箱 に 波 及 効 果 を 与 え,フ. ィ ル タ の 更 新 が 行 わ れ,. そ の 結 果 と し て 新 た な マ ス 目 に数 字 が 確 定 で き る可 能 性 が 高 くな る か ら で あ る。 ま ず 作 戦 ① を 実 行 す る前 に,局. 面 探 索 の キ ー と な る変 数fiIterを 145(543). 作 成 す る。.
(16) 第59巻 こ こ で は 先 の 図1.1の. 第2号. 数 独 問 題 を と り上 げ て 解 説 す る 。. :. 一 一 ・ レ. 、. 論 理 的 推 論 か らマ ス 目の 数字 を確 定 す る。 局面 の進展 がな けれ ば作 戦③ へ進 む。. 作戦① 1. ト. 作戦② ノ. ■■■■■■■■■■■■1. 2個 の候 補 ナ ンバ ー が あ る マ ス 目を二 つ選 び4個 の候 補 局 面 作 成 後 、作 戦 ① と② を適 用 す る。適 用 して も、局 面 の進 展 が な け れ ば. ⇒. 作戦③. 作 戦 ④ へ 進 む。. /一 ■1. ム. 作戦④. ). 作戦⑤. 旦. 曼._..._..…. 作 戦 ③ で 作 成 した4個 の 候 補 局 面 毎 に、 更 に候 補 ナ ンバ ー が2個 あ る任 意 の マ ス 目を2個(2個 な けれ ば1個)選 び、. 作 戦 ③ で 作 成 した4個 の 候 補 局 面 毎 に、 更 に 候 補 ナ ンバ ーが2個 あ る任 意 の マ ス 目を最 大4個 ま で選 び、候 補 局 面 を最. 候 補 局 面 を 最 大16個 ま で に拡 大 す る。 そ の一 つ 一 つ に対 して 作 戦 ① と② だ け を適 用 す る。 こ れ を 全 て の 候 補 局 面 に 対 して 行 った. 大64個 まで 作 成 ・保 存 す る。 そ の一・ つ 一 つ に対 して作 戦 ① ∼④ を 適 用 す る 。 これ を全 て の 候 補 局 面 に対 して 行 っ た 後 、正 解 に た ど り着 か な けれ ば ギ ブ ア ッ プ宣 言 を す る。. 後 、 局 面 の進 展 が な け れ ば 作 戦 ⑤ へ進 む。 図4.15つ. の作 戦. 作 戦① こ の 作 戦 ① で 数 字 を 特 定 す る方 法 と し て は2種 1つ 目 は,空. の マ ス 目 に候 補 ナ ン バ ー が1個. 当 然 そ の 数 字 が 確 定 す る。 図4.2は あ る。 同 図 の(1)で. 図1.1の. 類 あ る。 し か 残 っ て い な い 場 合 で あ る。 こ の 場 合 は. 数 独 問題 の フ ィル タ 情 報 を 図 示 した もの で. 指 し示 す マ ス 目 のfiIterは[123456089]で. あ り,7以. 外 の数 字 は この マ. ス 目 が 所 属 す る 行 ・列 ・箱 の い ず れ か で 使 用 さ れ て い る。 つ ま り候 補 ナ ンバ ー は[7]し か 残 っ て い な い 。 従 っ て,こ 2つ 目 は,1つ. の 時 点 で こ の マ ス 目 の 数 字 は7に. 確 定 す る。. の マ ス 目 に複 数 の 候 補 ナ ン バ ー が あ る場 合 で も,行. ・列 ・箱 の グ ル ー プ. ご と に見 た 時 に或 る数 字 が そ の マ ス 目 だ け に 候 補 ナ ン バ ー と し て 残 っ て い る場 合 に も,そ の 数 字 は 確 定 に な る。図4.2の(2)で る が,こ filterに. の(2)の. 指 し示 す マ ス 目 で は 候 補 ナ ン バ ー は[1][2][9]の3個. マ ス 目 の あ る 「行 」 を 見 て み る と,(2)の. は 全 て2が. 入 っ て い る,つ. を 入 れ る こ と が で き る の は(2)の. あ. マ ス 目以 外 の 空 い た マ ス 目 で は. ま り[2]が 使 え な い こ と が 分 か る。 従 っ て,こ. の 行 で[2]. マ ス 目 だ け だ と い う こ と に な る 。 従 っ て こ の 時 点 で(2) 146(544).
(17) SAS⑪.言 語 で 解 く数独 パ ズ ル(周 防) の マ ス 目 の 数 字 は2に こ の2種. 確 定 す る。. 類 の 方 法 に よ り新 た に 数 字 が 見 つ か っ た 場 合 は,空. し た 後,ORIGINALを. 更 新 し た 後,puzzIe. _soIve_finaI.sasの. 先 頭 に再 帰 的 に戻 る。 この方. 法 で 新 し い 数 字 が 見 つ か ら な くな る ま で 繰 り返 し た 後,次. 123 006 780 023 006 709 023 006. 100 006 780 103 006 709. 6. 456 700. 7. 100 006 780. 8. 2 123 456 080. 3. 3. 103 056. 9. 003 006. 089 123 400. 103 000. 089 103 056. 003 450. 456 700. 456 709. 7. 780 020 006 780 103 456 780. 8. 780 123 006 089. 456 780. 一 2. 一 〇〇6. 023 406 780. 4 023 450 089. 006 789. 謝 樹 幽5 700. 103. 1. 103 450 089. 1. 123 406. 一 一 一 〇〇6 〇〇6 〇〇6 700 120 006 780 103 450 780 123 400. の 作 戦 ② へ 移 る。. 6. 幽 閥 幽 講 700. 103 000 780. 3. 一. 一 456. 6. 089 020 450 789 020 450 089. 120 056 789. 7 003 450 709 023 450. の マ ス 目に そ の数 字 を追 加. 5 i2B{ 巨, 5【翻 :・13翼■. 450 789. 9醇. 4. 789 103. 103 000 089 003 006. 123 400 089 023 406. 089. 089 023. 400 3 霊緊. 一. 二覧6. 階隆 矯 456 080 023 450 780 023 450 080 023 400. (2). 8 020 450 080. 2. 080 123. ;1 ・..23. 8. 翻50 9. 図4.2作. 456 080. 400 089. (1). 戦①. 作戦 ② こ の 作 戦 で は,作. 戦 ① で 新 た な 数 字 が そ れ 以 上 確 定 で き な くな っ た 場 合 に,ま. 情 報 だ け の ア ッ プ デ ー トを 試 み る。 次 に 候 補 ナ ン バ ー が2つ. ずfilter. しか な い マ ス 目を探 す。 そ し. て そ の マ ス 目 が 所 属 す る行 ・列 ・箱 の グ ル ー プ の 中 で 同 じ組 み 合 わ せ の 数 字 の マ ス 目,つ ま り 同 じfiIter情. 報 を 持 つ マ ス 目 を 探 す 。同 じ数 字 の 組 み 合 わ せ の マ ス 目 が2つ. 合 は そ の グ ル ー プ の 中 で は も う そ の 数 字 は そ の2つ. の マ ス 目以 外 の マ ス 目 で は 使 え な い こ. と に な る。 そ こ で そ の グ ル ー プ 内 の 他 マ ス 目 のfiIterに filterを. ア ッ プ デ ー トす る。 例 え ば,図4.3で. 補 ナ ン バ ー が 共 に1と6で つ に は6が. あ る。 つ ま り こ の2つ. 入 る こ と は 確 定 し て い る。 従 っ て,こ. る こ と は な い の で,同 一 行 の 他 の マ ス 目 のfiIterに 4.3b)Q. 147(545). あ った場. さ ら に そ の2つ. 黒 い マ ス 目2つ. の 数 字 を 追 加 し,. は 同 じ行 に あ り,か. の マ ス 目 の ど ち ら か に1が. 入 り,も. の 行 の 他 の マ ス 目 で は1と6が は1と6を. つ候 う1. 候補 にな. 追 加 す る こ と が で き る(図.
(18) 第59巻. 123. 123. 006. 006. 780. 780. 023. 103. 006. 006. 709. 709. 123. 3 6. 7. 006. 7. 780. 7. 3. 123 450 780. 700. 700. 2. 023 406 023. 056. 056. 780 103. 456. 450. 080. 006 089. 780. 789. 456. 456. 8. 8. 7° Ω一. 4. 6. 5. 7. 3. 8. 5. 難. 護 聡顛験. 006. 406. 789. 789. 780 023 006. 023. 709 023. 400. 006. 789. 780. 4. :●:. 020 456. 023. 089. 080. 080. 700. 023. 023. 450. 450. 789. 780. 020. 023. 020. 450. 450. 450. 7. 9. 450 089. 123 456 080. 123. 3. 123. 鱗灘 蔭≡1. 400. 123 006. 089. 089. 103. 103. 006. 7. 3. 123. 123. 789 103. 400. 056. 780. 789. 006. 7. 780. 450. 7. 780. 3. 023. 023. 456. 456. 123. 9. 406. 089. 023. 023. 006. 406. 789. 789 023. 8. 3. 5. 2. 4. 020. 023. 020. 456. 456. 456. 700. 780. 089. 080. 080. 123. 023. 023. 023. 056. 450. 450. 8. 789 020. 780 023. 020. 450 089. 450 ハAA. 056 780 103. 2. 4. 6. 5. 7. 3. 4. 8. 5. 780 103. 450. 456 780. 1AA. 406 7員 日. 8. :●瑚61. :●:弓3. を囹. コ囹 ・:7. ●】. 阯8爬 】. 123 蟻襲 藝§ 006 璽§ 789 嚢 難§. 4. 囚 号 β二. 3. 2. 1購 灘 蕎. 123 400. 藝. 089. 089. 猛譲心. 凹載. 巽. 凹麟ア. 嚢 糞 霧 霧 藝巽. 藝 嚢. 戦 ② 適. 、琵. 阿. 妻. 123. 123. ・・回. ・・同. 780. 780. 図4.3b作. こ の 確 認 を 行 ・列 ・箱 の 全 て に 対 して 行 っ た 後,新. 450 080. 123 406 7Ωn. 123 450. 9. 2. 憲騨. 戦 ② 適 用 前 の フ ィル タ情 報. 400 789. 8. 023. 406. 400. 089. 780. 環曝鑓. 780. 再 実 行 す る。 そ の結 果,新. 056. 6 003. 709. 123. 000. 選§. =▼. M黙溝. 780. 2. 780. 懇馨 1作 甕. 回23 ・・回. ・・回. 123. 1. 400. 8. 780. 123. 3. 護1翻1. 灘 瀬1. 作戦②適用 123. 2. 720. 陰】. 2. 406. 8. n° Ω一 080 〇23 4002. 4. 789. 図4.3a作. 123 006. 6. 023 456. 123. 3. 006. 123 006. 020 456. :●:陽`1. ■匹匪置:●】 劉` 一 剛陪隅】7習. 123. 1灘嚢 巽嚢. 023. 2. 089 置 ●:臨6鴫 引. 8. 089. 023. 3. 5. 780. 400. 400. 089. 780. 2. 4. 123. 000. 780. 103 456. 7RO 123. 056. 780. 123. 3. 400 023. 123. 103. 780. 123. 123. 9. 056. 123. 023 780 123 406. 3. 789 003. 023 406. 2. 103. 780. 6. 1. 400 780. 023 006. 8. 第2号. 戦 ② 適 用 後 の フ ィル タ 情 報. し く な っ たfiIterを. 使 って作 戦 ① を. しい数 字 が見 つ か れ ば そ の数 字 を追 加 した 後 に ま た作 戦 ① に戻. り,見 つ か らな けれ ば作 戦 ② に進 む。 作 戦 ② の実 行 に も関 わ らず,新. しい数 字 が見 つ か ら. な けれ ば次 の作 戦 ③ に移 る。. 作戦③ 作 戦 ② を実 行 した 後 で も新 た な数 字 が見 つ か らな か った場 合 に は,正 解 が必 ず含 ま れ る 複 数 の 候 補 局 面 を 作 り,そ. れ ら を 一 つ ず つ チ ェ ッ ク し て い く。 候 補 局 面 を 作 る た め に,現. 時 点 で 確 定 し て い る 局 面 に お い て 候 補 ナ ン バ ー が2個. あ る マ ス 目 を 行 ・列 ・箱 の グ ル ー プ. とは 関 わ りな く任意 の2個 を取 り出 す。そ の取 り出 した候 補 ナ ンバ ー の全 て の組 み 合 わせ, つ ま り4通 りの 組 み合 わ せ の候 補 局 面 を作 成 す る。 この4通. りの局 面 の い ず れ か1つ は必. ず正 解 な の で,そ れ ぞ れ の候 補 局面 に対 して逐 次,作 戦 ① と作 戦 ② を実 行 す る。 例 と して 挙 げ た 図4.4の わ せ,つ. 場 合,黒. 色 の マ ス 目 を2つ. ま り(1)の マ ス 目 に は1か7,(2)の. 選 び,こ. の2つ. の マ ス 目の候 補 の全 て の組 み合. マ ス 目 に は3か5の. 数 字 を 入 れ た4つ. の候 補. 局 面 を作 成 し実 行 す る。 そ の 際,途 中 で誤 答 が判 明 す るか,局 面 に進 展 が な くな った場 合 は そ こで 中止 して,残 りの 局 面 を順 次 試 して い く。4つ. の 局面 全 て を試 して も,正 解 に達 しな い場 合 は次 の作 戦 148(546).
(19) SAS⑪.言 語 で 解 く数独 パ ズ ル(周 防). ④ に移 る。. 000. 020. 000. 103. 000. 450. 456. 450. 450. 450. 089 100 400. 009. 089 100 450. 709 103 450. 709 100 450. 4. 089. 709. 709 000. 000. i暉2:σ. 7. 450. 450. 700 120. 700 120. 藤. 123. 406 709 023. 456 709 023. 7 6. 9. 089 000. 020. 400. 406. 789. 709. 4. 4. 6. 9. 406 709. 3123. :●:2. 経. 8. 重. L.▼.r. 9癬1 靴)竺0 響 遡6 406 :撒'089. (1). 103. 5. 9. 450. 4. 1. 089 103 400. 100 450. 089. 056. 056. 456. 020. 103. 080 000. 780 000. 400 789 123. 400 089 123. 450 789. 000. 000. 700. 700 103. 1. 400. 450. 406. 780 103 450. 789. 3. 780 103 050 780. 780. 駈1. 圏鱒 団780 ● 」. 089. 456 089. 020 450. 020 056. 020 450. 780 100. 789 120. 789. 450. 456. 8. 080 003 450. 089 023 056. 080. 089. 5. 図4.4作. 103 400 雲≡≡ 罷i'ヨ ≡ 匿'. 009 100 450. ・ 載 . 709 (麗 圃 ℃懸 騒壽003篇 蒜孟 藏 墜鞠 .h§ 456 、 踊餐≡ 盟璽跳 789 78響 藝. 3. 5. 4. 8. 9. 7. 2. 023 400. 020 450. 780 103. 120. 789 120. 4. 450. 023 450. 089 023 450. 080. 089. 8. (2). 戦③. 出 典:(http://robohei。jugem.cc/?eid-1689). 作戦 ④ 作 戦 ③ で試 み た4つ の 局 面 そ れ ぞ れ に対 して,更 に候 補 ナ ンバ ー が2個 あ る任 意 の マ ス 目を取 り出 し,新 し く候 補 の 局面 を作 成 す る。 作 戦 ④ で は候 補 ナ ンバ ー が2個 あ るマ ス 目 が1つ. しか な い場 合 も想 定 し,マ ス 目を1つ だ け使 用 す る場 合 と,2つ. ち らか を実 行 す る。 作 戦 ③ で作 成 した4通. 使 用 す る場 合 の ど. りの組 み合 わ せ の局 面 を1つ 取 り出 し,候 補 ナ. ンバ ー が2個 の マ ス 目を 列挙 す る。 そ の様 な マ ス 目が2つ 以 上 あ る場 合 に は,そ れ か ら任 意 にマ ス 目を2つ 取 り出 し候 補 ナ ンバ ー の 組 み合 わ せ で4つ の新 しい 局面 を作 る。 マ ス 目 が1つ. しか な い場 合 は そ の マ ス 目の み使 用 し2つ の新 しい局 面 を作 る。 新 しい局 面 を作 成. した らそ れ ぞ れ の 局 面 につ い て作 戦 ① か ら実 行 す る。 これ を作 戦 ③ の4通. りの 局面 す べ て. につ い て そ れ ぞ れ試 す。 従 って,作 戦 ④ で は最 高16個 の新 しい局 面 を作 成 し,試 す こ とが で き る。. 作 戦⑤ 作 戦 ④ を 実 行 し て も正 解 が 得 ら れ な か っ た 場 合,作 補 局 面 の デ ー タ セ ッ ト(originaL1∼originaL4)の ー が2個. あ る マ ス 目 を 最 大4個. 戦 ③ で 作 成 し保 存 し て い る4つ. ま で使 用 し. そ れ ぞ れ の 局 面 に つ い て,候. ,最. 149(547). 大64個. の 候 補 局 面 を 作 成 す る。4個. の候. 補 ナ ンバ なけれ.
(20) 第59巻. 第2号. ば あ る だ け を 使 っ て 候 補 局 面 を 作 成 す る。 候 補 局 面 を す べ て 作 成 し 終 え る と,ま 候 補 局 面 を 初 期 局 面 と し て 設 定 し,作 る。 そ の 後 再 帰 的 にpuzzIe に よ っ て,作. ず最 初 の. 戦 ⑤ で 使 用 し て い る マ ク ロ変 数 以 外 を 全 て 初 期 化 す. _soIve_finaI.sasを%includeに. 戦 ① か ら作 戦 ④ ま で を 逐 次,次. よ って再 帰 的 に実 行 す る こ と. 々 に 実 行 す る こ と が で き る。 そ れ に も か か わ. らず 解 が 得 られ な い 場 合 に は 次 々 に残 りの 候 補 局 面 を 初 期 局 面 と し て 設 定 し繰 り返 し puzzle_solve_final.sasを. 再 帰 的 に実 行 す る。. 作 戦④ と⑤ の相 違 点 1.作. 戦 ④:作. 戦 ③ で作 成 した 候 補 局 面 ご と に更 に新 た に候 補 ナ ンバ ー を追 加 して候 補. 局 面 を 作 成 ・保 存 して 実行 す るた め,再 帰 的 に 作 戦 ③ に 再 突 入 す る と,未 処理 の候 補 局 面 を 壊 して しま うた め 作戦 ③ を 再 び 実 行 で きず,作 戦 ① と作 戦 ② しか実 行 で きな い。 2.作. 戦 ⑤:作. 戦 ③ で 作 成 した 局 面 を 基 に候 補 ナ ンバ ー を大 幅 に増 加 して候 補 局 面 を作. 成 ・保 存 して い る。 従 って そ れ らの 全 て の 候 補 局 面 を逐 次 初 期 局 面(ORIGINAL)と して 作 戦 ① か ら作戦 ④ ま で 実 行 す る こ とが で き るの で,幅 広 くか つ 深 く探 索 で き る。. 作 戦 ① と作 戦 ② か ら得 られ る結 果 は 「確 定 した」 正 解 で あ る。 一 方,作 戦 ③ と作 戦 ④ で は 「確 定 す るに は 至 らな い」候 補 の 局 面 を 列 挙 す るが,そ の 中 に正 解 は必 ず含 ま れ て い る。 ほ とん どの数 独 問題 は作 戦 ① ∼④ で解 けた が,超 難 問 は作 戦 ⑤ ま で進 ま な い と解 け な か っ た。. 一 般 的 にゲ ー ム を コ ン ピ ュー タに させ る と きは ゲ ー ム木 を作 って探 索 す るの が普 通 で あ る。 数 独 の 場 合,対 search)あ SSSは. 戦 型 ゲ ー ム で は な い が,ゲ. る い は 幅 優 先 探 索(breadthfirstsearch)を. ー ム 木 を 作 っ て 深 さ 優 先 探 索(depthfirst す る こ と は で き る。 し か し,我. ゲ ー ム 木 を 探 索 す る特 別 の ア ル ゴ リズ ム は 組 み 込 ん で い な い 。 そ の 代 わ り に,再. 的 な プ ロ グ ラ ミ ン グ を 採 用 す る こ と で,結. 果 的 に は,そ. 々の 帰. の 両方 の探 索 方 法 を使 って い る こ. と に な る。 作 戦 ① と作 戦 ② で は,局 面 の 論 理 的 推 論 か ら確 定 で き る マ ス 目 の 数 字 だ け を 探 して い る 。 従 っ て,こ. の段 階 で は ゲ ー ム 木 は必 要 と しな い。 この二 つ の作 戦 で確 定 した局 面 を新 た に. 初 期 局 面(SASデ. ー タ セ ッ トORIGINAL)と. 行 し に行 く こ と に な る。 つ ま り,再 作 戦 ③ ∼ ⑤ は,単. し て 再 度puzzle_solve_final.sasを. 再 帰 的 に実. 度 作 戦 ① か ら適 用 し て 行 く。. 純 な論 理 的推 論 か らは もは や新 た な数 字 が 見 つ か らな い段 階 で適 用 す 150(548).
(21) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防) る作 戦 で あ る。 我 々 が 考 案 し た フ ィ ル タ と い う概 念 を 利 用 し て,正 候 補 局 面 を 作 成 し て,そ は,先. の 図4.1に. れ ぞ れ に 対 し て 作 戦 ① か ら適 用 し て い くが,作. 示 す よ う に,作. 方 が 遙 か に よ い 。 実 際 問 題 と し て,99.9%の. 行 時 間 つ ま り検 索 効 率 を 考 慮 す る と,あ. 数 独 問 題 は 作 戦 ④ ま で で 解 く こ と が で き た 。言. さ優 先 探 索 を し て い る こ と に な る が,各. 常 の 評 価 関 数 は 使 っ て い な い 。 ど の 作 戦 の 実 行 中 で も,最 戦 ① と ② で あ る。 各 候 補 局 面 の 評 価 は,(1)作. た か(マ ク ロ変 数found 或 い は(3)検. る. 戦 ⑤ を 持 ち 出 さ な くて も ほ と ん ど の 数 独 問 題 は 解 け る と い う こ と で あ る。. 作 戦 ③ ∼ ⑤ で は,深. の は,作. 戦 ③ ∼⑤ の相 違 点. 成 す る 候 補 局 面 の 数 と適 用 す る作 戦 の 範 囲 で あ る。 作 戦. ⑤ が あ れ ば 作 戦 ④ は 不 要 の よ う に 思 え る が,実. い 換 え れ ば,作. 解 の 局 面 も含 む 複 数 の. _sw=1),(2)ル. 候 補 局 面 の 評 価 に い わ ゆ る通 終 的 に マ ス 目の数 字 を確 定 す る. 戦 ① と② で 新 た な 数 字 が 確 定 で き. ー ル に 反 す る 局 面 が 出 現 し た か(マ ク ロ 変 数wrong=1),. 索 す る ラ ウ ン ド(探索 の 深 さ,マ ク ロ 変 数round)が. 制 限 以 内 か の3点. で 行 わ れ,. そ の 後 の 処 理 の 制 御 を し て い る。 SSSは. い わ ゆ る一 種 の ヒ ュ ー リス テ ィ ッ ク プ ロ グ ラ ミ ン グ技 法 を 採 用 し て い る。 つ ま り. 解 く手 が か り と な る マ ス 目 が た く さ ん あ る 中 か ら事 前 に 決 め ら れ た 個 数 の マ ス 目 を 選 ぶ 場 合,そ. の 「選 び 方 」 に よ っ て は 解 け な い 場 合 も起 こ り う る の で,全. け る保 証 は な い が,そ. れ に も か か わ ら ず,現. て の数 独 問題 が必 ず解. 実 に は この 時 点 で試 した す べ て の数 独 問題 の. 正 解 を 得 る こ と が で き た 。 正 解 を 得 る確 率 を さ ら に 上 げ る た め に,後. の バ ー ジ ョ ン で は,. 初 期 局 面 を90度 ず つ 右 回 転 し た 局 面 で 解 く戦 略 を 追 加 し た 。 こ れ に つ い て は 第6節. で解 説. し て い る。. 5.プ. ロ グ ラ ム(バ ー ジ ョ ン1)の. 性能評価. こ こ ま で の 開 発 時 点 で 試 し た 数 独 問 題 は す べ て 正 解 を 得 る こ と が で き た 。市 販 本 や イ ン タ ー ネ ッ ト上 に 難 問 と して 紹 介 さ れ て い る 問 題 に つ い て は 超 難 問(図5.1) 以 外 は,作 戦 ④ ま で で 正 解 を 得 る こ とが で き た 。現 段 階 で 最 も難 し い と思 わ れ る こ の 超 難 問 も作 戦 ⑤ を 使 用 す る こ と で 解 答 を 得 る こ とが で き た 。 こ の プ ロ グ ラ ム が 解 答 に か か っ た 時 間 は,こ. の 超 難 問 で7分14秒(経. ル の 問 題 で は36秒 しか か か って い な い 。 更 に,最. 過 時 間)で あ り,図1.1の. とOUTPUT情. 中 級 レベ. 終 結 果 だ け を 表 示 し て,LOG情. 報 を 出 力 し な い よ う に設 定 す る こ と で,解. を 大 幅 に 短 縮 す る こ と が で き た 。 具 体 的 に は 図5.1の. 報. 答 を得 る まで に かか る時 間 超 難 問 は2分49秒,図1.1. の 問 題 は20秒 で 解 答 を 得 る こ と が で き た 。こ れ は 十 分 に 満 足 の い く結 果 だ と思 わ れ 151(549).
(22) 第59巻 る 。 た だ し,実. 第2号. 行 時 間 は パ ソ コ ン のCPUと. メ モ リ サ イ ズ に 依 存 す る の で,こ. れ ら. の 数 字 は 一 応 の 目安 で あ る。. 5. 3. 8. 2 7. 1. 5. 4. 5 1. 3 6. 7. 3 6. 9. 5. 3. 4. 9 図5.1超. ⇒. 8. 2. 7. 1. 4. 5. 3. 2. 7. 6. 9. 8. 8. 3. 9. 6. 5. 4. 1. 2. 7. 6. 7. 2. 9. 1. 8. 5. 4. 3. 4. 9. 6. 1. 8. 5. 3. 7. 2. 2. 1. 8. 4. 7. 3. 9. 5. 6. 7. 5. 3. 2. 9. 6. 4. 8. 1. 3. 6. 7. 5. 4. 2. 8. 1. 9. 9. 8. 4. 7. 6. 1. 2. 3. 5. 5. 2. 1. 8. 3. 9. 7. 6. 4. 難問. 図5.2超. 難問解答. 出 典:(httD://gigazine.net/news/20100822hardestsudoku/). 6.バ. SSS(バ ー ジ ョ ン1)の. ー ジ ョ ン ア ッ プ. 完 成 に よ り,前. 節 に 示 し た 「超 難 問 」(図5.1)は. が,そ の 後 新 た に イ ン タ ー ネ ッ ト上 で 見 つ け た 難 題10問(付 第7節. の 表7.1に. 示 す よ う に,6問. 録4:a1∼a10)を. 解 くこ とが 出 来 た 解 い て み る と,. が 解 け な い こ と が 判 明 した 。 そ こ で 新 し い 戦 略 を2つ. 追加 して バ ー ジ ョンア ッ プを 図 った。. 6.1バ ー ジ ョン1.5(右90度 ず つ 回 転) 新 た な戦 略 と して,ま ず初 期 局面 を作 る際 に,テ キ ス トフ ァイ ル を そ の ま ま読 み込 ん だ オ リジナ ル 局 面 だ けで な く,そ の局 面 を90度 ず つ右 回転 させ た合 計4つ. の初 期 局 面 を作 成. した。 これ は 局 面 を右 回転 させ る こ とで,作 戦 ③ 以 降 で候 補 局面 を作 成 す る際 に,使 用 す るマ ス 目の 選 択順 序 が変 わ るの で,組 み合 わ せ が変 わ り,新 た な数 字 を確 定 で き る可 能 性 が あ るか らで あ る。 この作 戦 を追 加 した結 果,解 来 た(第7節. 表7.1)。. 152(550). けな い6間 中4問 を新 た に解 くこ とが 出.
(23) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防) 6.2バ. ー ジ ョ ン2(作. 戦 ⑥ の 追 加). バ ー ジ ョ ン1 .5で も ま だ 解 け な い 問 題 が2問 作 戦 ⑤ ま で は,候. 補 ナ ン バ ー が2個. な マ ス 目 が な い ケ ー ス が あ り,作. あ る の で,新. た に 作 戦 ⑥ を 追 加 した(図6.1)。. あ る マ ス 目 の み を 使 用 し て い た が,難. 戦 ⑥ で は 候 補 ナ ン バ ー が3個. 問ではそのよ う. あ る マ ス 目 も使 用 す る こ と. に した。 作 戦 ⑥ で は作 戦 ③ で作 成 した4つ の候 補 局 面 の そ れ ぞ れ に つ い て,更 に候 補 ナ ン バ ー が3個. の マ ス 目 を 最 高3個. 取 り 出 し,最. 高108(27×4)個. の候 補 局 面 を 作 成 す る こ と に. した。. ;. 、. 論 理 的 推 論 か らマ ス 目 の数 字 を確 定す る。 局 面 の進 展 が な けれ ば 作戦 ③ へ進 む。. 作戦①. ・・ レ. 1. 〉. 作戦② ノ. 2個 の 候 補 ナ ンバ ー が あ るマ ス 目を 二つ選 び4一 個 の候 補 局 面作 成後 、作 戦 ① と② を適用 す る。適 用 後 、局 面の進 展 が な け れ ば作戦 ⑥ へ進 む。. ⇒. 作戦③. /. ム. 作戦⑥. レ. 作戦⑤. 5. o. 作 戦 ③ で 作成 した4個 の候 補 局 面 毎 に、更 に候 補 ナ ンバー が 3個 あ る任 意 のマ ス 目を最 大3 つ 選 び、候 補 局 面 を最 大27個 まで に拡 大す る。そ の一 つ一 つ に対 して 作 戦 ① と② だ け を 適 用 す る。 これ を全 て の 候 補 局 面 に 対 し て 行 った 後 、局面 の進 展 が な け れ ば 作戦⑤ へ 進 む。. 図6.1作. 作 戦③ で作 成 した4個 の候 補 局 面 毎 に 、更 に候 補 ナ ンバ ー が2個 あ る任 意 のマ ス 目を最 大4個 ま で選 び 、候 補 局面 を最 大64個 ま で作 成 ・保 存す る。 そ の一 つ 一 つ に対 して 作 戦① ∼ ③ を適 用 す る。 これ を全 ての 候補 局面 に対 して行 っ た 後 、正 解 にた ど り着 かな けれ ば次 の初 期 局 面 を試 す 。4つの 初期 局 面 を 試 して も解 答 が 得 られ な けれ ば途 中 結果 を出力 す る。 戦⑥. 更 に,作 戦 ⑥ は作 戦 ⑤ の後 に実 行 す るの で はな く,作戦 ⑤ の前 に実 行 す る こ とに した。 これ は プ ロ グ ラム 構造 上,作 戦 ⑤ を実 行 す る際,再 帰 的 に プ ロ グ ラム を実 行 す る と きに, 作 戦 ③ で作 成 した候 補 局 面 を壊 して しま うか らで あ る。 作 戦 ⑥ の候 補 局 面 を作 成 す る際 に は作 戦 ③ で作 成 した候 補 局面 が必 要 に な るの で,作 戦 ⑤ の前 に作 戦 ⑥ を実 行 した。 また作 戦 ⑥ 作 成 後 は作 戦 ④ を 削 除 し,作 戦 ③,作 戦 ⑥,作 戦 ⑤ とい う順 番 で実 行 す る よ う に した。 そ もそ も作 戦 ④ は作 戦 ⑤ の縮 小 版 で あ り,初 の 問題 で は解 答 時 間 の短 縮 が 図 れ る とい う理 由 で,残 153(551). ・中級. して い た が,作 戦 ⑥ を追 加 後,プ. ロ.
(24) 第59巻 グ ラ ム の 構 造 が 複 雑 化 し,実 間 も増 加 し た の で,作. 第2号. 行 時. 戦④ を削除. した ほ うが相 対 的 に時 間 の短 縮 に な る と考 え,作 そ の 結 果,作. 戦 ④ を 削 除 した。. 戦 ① ② ③ ⑥ ⑤ で全 て. の 問題 を解 くこ とが 出来 た。 解 法 エ ン ジ ン に相 当 す る マ ク ロ 「alU を 右 に示 す 。 先 の 難 問10題(付 録4:a1∼a10) の 中,5問. は初 期 局 面 を何 回 か右. 90度 回 転 し た 結 果 解 く こ と が 出 来 た(第7節. 表7.1)。. この段 階 で 組 み込 ん だ マ ク ロの 数 が39個. に な っ て し ま っ た の で,. よ く似 た マ ク ロ を 整 理 ・統 合 し た 結 果,マ. ク ロ の 数 を26個. にす る こ. とが で きた。. 6.3バ. ー ジ ョ ン3(新. バ ー ジ ョ ン2で. 作 戦 ③ の 作 成). 新 た に作 戦. ⑥ を 追 加 し た こ と で,こ. れ ま. 作戦①. レ. 1. 作戦②. で 解 け な か っ た 問 題 も解 く こ. }. 論 理 的 推 論 か らマ ス 目の 数 字 を確 定 す る。 局面の進展 がなければ新作 戦 ③ に進 む。. と が 出 来 る よ う に な っ た が, 作 戦 ⑥ を 組 み込 む と制 御 が 非. 新作戦③. 常 に複 雑 に な っ た 。 こ れ は,. o. 人 間 が 数 独 を 解 く際 に用 い る,. い わ ゆ る ヒ ュー リス テ ィ ッ ク ス を次 々 に追加 して採 用 した 結 果 で あ る。 こ こ まで の 開 発 プ ロセ ス で得 た情 報 ・知 識 を. 候 補 ナ ンバ ー が2個 あ る い は3個 の マ ス 目 を指 定 し た 数 だ け取 り出 し(デ フ ォル ト6)候 補 局 面 を 作 成 す る。 そ の一 つ 一 つ に対 して 作戦 ① と作 戦 ② を 適 用 す る。 全 て の 候 補 局 面 に対 して行 った 後 は 、 次 の 初 期 局 面 を 作 戦 ① か ら順 次 実 行 す る。4つ の 初 期 局 面 全 て に お い て も解 答 が 得 られ な けれ ば 途 中 結 果 を 出 力 す る。. 総 合 的 に判 断 して,作 戦 ③ ⑥. 図6.2新 154(552). 作戦③.
(25) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防). ⑤ の 候 補 局 面 を 順 番 に作 成 ・実 行 す る よ り も,一. 度 に あ る程 度 の 個 数 の 候 補 局 面 を 作 っ て. し ま っ て か ら そ れ ぞ れ の 候 補 局 面 を 解 き に 行 く方 が,実 ム 化,及. 行 時 間 の短 縮 と プ ロ グ ラム の ス リ. び 制 御 の 簡 素 化 に つ な が る の で は な い か と考 え た 。 そ こ で 現 在 ま で 作 成 し た 作 戦. ③ ⑤ ⑥ を 統 合 し て 「新 」 作 戦 ③ を 作 成 す る こ と に し た 。 新 作 戦 ③ は 候 補 ナ ン バ ー が2個. あ る マ ス 目 だ け で な く3個. 面 を 作 成 す る。 あ ら か じ め マ ク ロ変 数seIect_noで 数 を 設 定(デ. フ ォ ル トは6)し. り な い 分 は 候 補 ナ ン バ ー が3個. て お き,ま. あ る マ ス 目 も使 用 し て 候 補 局. 候 補 局 面 の 作 成 に使 用 す る マ ス 目 の 個. ず 候 補 ナ ン バ ー が2個. の マ ス 目 を 取 り 出 し,足. の マ ス 目 か ら追 加 し た 。 こ の 新 作 戦 ③(図6.2)で. 今 ま で解. くこ との で きた全 て の数 独 問題 を解 くこ とが 出来 た。 新 作 戦 ③ を 作 成 す る作 業 に伴 い,こ reconstruct.sasを sudoku _macro.sasの のSASプ ち,不. 独 立 し たSASプ. れ ま で%include文. で 使 って いた プ ロ グ ラ ム. ロ グ ラ ム と し て 保 存 し な い で,ひ. 中 で 定 義 す る こ と に した 。 そ の 結 果,SSSは. ロ グ ラ ム か ら構 成 さ れ る こ と に な っ た 。 ま た,そ 要 と な っ た マ ク ロ を 整 理 し た 結 果,バ. とつ の マ ク ロ と し て. 以 下 に 示 す ① ∼ ③ の3つ. れ ま で に作 成 した マ ク ロ の う. ー ジ ョ ン2で26個. あ っ た マ ク ロ を21個 に 整 理. で きた。 バ ー ジ ョ ン3で. 使 用 し て い る マ ク ロ変 数 の 一 覧 を 付 録2に. プ ロ グ ラ ム の 詳 細 を 解 説 す る が,プ. 示 す 。 以 下 で バ ー ジ ョ ン3の. ロ グ ラ ム 全 体 は 大 き い の で,紙. 幅 の 関係 で本 論 文 に は. 掲 載 し な い 。 プ ロ グ ラ ム の 日本 語 版 と英 語 版 が そ れ ぞ れ 利 用 手 順 と共 に,以 zipフ. ァ イ ル 形 式 で ア ッ プ ロ ー ド して あ り,誰. 本 語 の 利 用 手 順 は 付 録3に. 下 の サ イ トに. で も ダ ウ ン ロ ー ドが 可 能 で あ る 。 な お,日. も あ る。. (1)日 本 語 版http:/mighty.gk.u-hyogo.ac.jp/confidential/Japanese_sudoku.zip (2)英 語 版http:/mighty.gk.u-hyogo.ac.jp/confidentiaI/sudoku.zip. ①sudoku_macro.sas こ の プ ロ グ ラ ム に は 全 部 で21個 の マ ク ロ が 定 義 さ れ て い る。 利 用 者 は こ の プ ロ グ ラ ム の 冒 頭 で 以 下 の(1)∼(4)ま. で を%letで. (1)SSSが. 保 存 さ れ て い る ドラ イ ブ 名 と フ ォ ル ダ 名. (2)LOG画. 面 情 報 及 びOUTPUT画. 面 情 報 を 保 存 す る フ ォル ダ 名. (3)LOG画. 面 情 報 及 びOUTPUT画. 面 情 報 の 出 力 の 要 ・不 要. (4)新. 指 定 す る。. 作 戦 ③ で 候 補 局 面 を 作 成 す る の に 利 用 す る マ ス 目 の 個 数(デ フ ォル トで は6に. 定 済). 155(553). 設.
(26) 第59巻. 第2号. こ こ で 設 定 さ れ た ドラ イ ブ 名 は 以 下 の2つ. のSASプ. ロ グ ラ ム ② と③ で も共 用 さ れ る。. こ の プ ロ グ ラ ム で 定 義 さ れ て い る マ ク ロ の 関 係 を 示 す マ ク ロ構 造 図 を 図6.3に 枠 で 示 さ れ た マ ク ロ に は%includeに. よ りpuzzle_solve_final.sasが. 示 す。 太. 含 ま れ て お り,再. 帰. 的 に実 行 さ れ る。. reCOnStrUCt. [llfilt∈]{1 1・. makefilter. ・lvel. 【図 注 】. flndcheck. 太 枠 の マ ク ロ に は%includeに puzzle.solve.final.sasが. よ り. 含 ま れ る. 匝 ヨ{1讐響l verlfyreCOnStrUCt. routput. t・・nl r. once. IoOP -. <. -. again3. again3. く. ㌦. qSet.・. checkno. zero. keep _pair. 團{1. 1・P・ ・ati・n.・・iginall. set _orlglnaI. ・iginall. outut. turn. 図6.3マ. ク ロ構 造 図(バ ー ジ ョ ン3). ②puzzle_make_original_data.sas この プ ロ グ ラム で は あ らか じめ作 成 して お い た解 きた い数 独 問題 の テ キ ス トフ ァイ ル名 (拡 張 子 無 し)を%let文. で 指 定 す る。 こ の プ ロ グ ラ ム を 実 行 す る と,テ. の ま ま読 み 込 ん だ 局 面,及. び そ の 局 面 を90度 ず つ 右 回 転 さ せ た3個. 期 局 面 を 作 成 す る。 ま た,Xコ ル ダ に,(1)OUTPUT画. 面 情 報 の 内,html形. (2)そ れ 以 外 のOUTPUT画 (log_window)が. マ ン ドに よ りsudoku_macro.sasで. キ ス トフ ァ イ ル を そ. の 局 面 の 合 計4個. 指定 した結 果保 存 用 フ ォ. 式 で 保 存 す る フ ォ ル ダ(output _window),及. 面 情 報 とLOG画. の初. び,. 面 情 報 を テ キ ス トフ ァイ ル で保 存 す る フ ォル ダ. 自 動 作 成 さ れ る 。 連 続 し て 別 の 数 独 問 題 を 解 く場 合,前. 回の結果 がその フ. ォ ル ダ に残 っ た ま ま に な っ て い る。 そ の フ ォ ル ダ の 中 の フ ァ イ ル を 消 去 す る か ど う か の 問 い 合 わ せ がDOSプ. ロ ン プ ト画 面 に 表 示 さ れ る の で,利. 入 力 す れ ば 前 回 の 結 果 は 削 除 さ れ る。Nと に上 書 き さ れ て し ま う の で,前. 用 者 がYま. 入 力 す れ ば,今. た はNを. 回 の実 行 結 果 が前 回 の実 行 結 果. 回 の 実 行 結 果 を 保 存 し て お き た い 場 合 は,あ 156(554). 入 力 す る。Yと. らか じめ そ の.
(27) SAS⑪ 言 語 で 解 く数独 パ ズ ル(周 防) フ ォ ル ダ ご と 別 の 場 所 に 利 用 者 が 自分 で 保 存 す る。Xコ. マ ン ドを 使 っ てDOS命. れ た フ ォ ル ダ に 出 力 さ れ る テ キ ス ト フ ァ イ ル 及 びhtmlフ 変 数rotate,round,set3_noの Explorer画. 令 で作 成 さ. ァ イ ル の フ ァ イ ル 名 に は,マ ク ロ. 値 が 使 用 さ れ て い る。 こ れ に よ り,プ. ロ グ ラム実 行 中 に. 面 で こ れ らの フ ァ イ ル の 作 成 状 況 を 見 る こ と に よ っ て,現 在 ど の 候 補 局 面 が 実. 行 中 で あ る か 分 か る。. ③puzzle_solve_final.sas こ の プ ロ グ ラ ム で はsudoku. _macro.sasで. 定 義 した マ ク ロ を 実 際 に 実 行 し て 問 題 を 解 い. て い る。 こ こ に プ ロ グ ラ ム本 体 を 示 す こ の プ ロ グ ラ ム の 冒 頭 で は,%eval関 自動 的 に1ず. 数 に よ っ て マ ク ロ 変 数roundとnew. つ 増 や さ れ る。 マ ク ロ変 数roundは. し実 行 し た 回 数 で あ り,マ. ク ロ変 数new. _roundは. _roundの. 値 も. 各 局 面 に お い て こ の プ ロ グ ラ ム を 繰 り返 この プ ロ グ ラム の実 行 の 開始 か ら終 了 ま. で に こ の プ ロ グ ラ ム が 繰 り返 し実 行 さ れ た 総 回 数 を 表 し て い る。 新 作 戦 ③ で 探 索 の 対 象 と な る複 数 の 候 補 局 面(正 面 か も し れ な い)を roundは0に. そ れ ぞ れ デ ー タ セ ッ トORIGINALと. 正 解 の局. し て セ ッ トす る 度 に マ ク ロ 変 数. リセ ッ トさ れ る 。. こ の プ ロ グ ラ ム は 実 行 を 始 め る 際 に,マ がSAS時. 解 の 局 面 か も し れ な い し,不. 間 で 設 定 さ れ る。 そ し て,正. ラ ム 実 行 終 了 時 刻 が マ ク ロ変 数endtimeに オ リ ジ ナ ル 局 面 及 び 右90度. ク ロ変 数starttimeに. 解 が 得 ら れ る,得 設 定 さ れ,そ. ず つ 回 転 さ せ た3つ. 局 面 に設 定 。 全 て の 作 戦 を 実 行 し,正. プ ロ グ ラム実 行 開始 時 刻. ら れ な い に か か わ ら ず,プ. の 差 か ら実 行 時 間 を 計 算 す る。. の 局 面 の 計4つ. の局 面 を順 次 オ リジナ ル. 解 が 得 ら れ な い 場 合 は 次 の 局 面 を 設 定 す る。. 157(555). ログ.
(28) 第59巻. /*puzzle_solve_final.sas*//*バ. 第2号. ー ジ ョ ン3*/. *Beforethisprogramisrun, "puzzI. e _make_originaI_data.sas"mustberun.;. oPtions&non.notes&non,sourGe;. *以 下 は 設 定 不 要; %letround=%eval(&round+1); %Ietnew_round=%evaI(&new_round+1); %Ietfound=0; *新 し い 数 字 が マ ス 目 に 追 加 さ れ て い れ ば1が %letwrong=0;*局. 自 動 的 に 設 定 さ れ る;. 面 に 矛 盾 が 生 じた 場 合 に1が. 自 動 的 に 設 定 さ れ る;. datanull; if×w=Othendo; starttime=DATETIMEO;putstarttime=time. *現 在 日 時 をSAS日. 付 値 で 表 す;. CaIISympUt("Starttime",Starttime); *実 行 開 始 時 刻 をSAS時. 間 で 設 定;. end; run;. %lettime_sw=1;*starttimeを. 設 定 後1に. 設 定 す る;. %set_rotate; *オ リ ジ ナ ル 局 面 及 び3回. dataoriginal *上. で 設 定. 右90度. 回 転 し て で き た4つ. の 局 面 を 順 次 設 定 す る;. _before; した 局 面 を 別 の デ ー タ セ ッ. トで 保 存. し て お く'. SetOriginal; run;. &star.odsIistingGIose; &star.odshtmlfile= "&output¥&rotate ._ROUND&round._作. 戦 ③ORIGINAL&set3_no..xIs";. &star.proGprintdata=original; title"ROUND&round:&new. _round.data=originaI";run;. &star.odshtmIcIose; &star.odsIisting;. &star.PROCPRINTTOlo9= "&Iog¥Iog&rotate &star.PROCPRINTTOprint= "&log¥output&rotate. %all;*解. . _ROUND&round._作. ._ROUND&round._作. 戦 ③ORIGINAL&set3_no..txt"NEW;RUN;. 戦 ③ORIGINAL&set3_no,.txt"NEW;RUN;. 法 エ ン ジ ン;. 158(556).
関連したドキュメント
市場を拡大していくことを求めているはずであ るので、１だけではなく、２、３、４の戦略も
「第 3 章 SAS/ACCESS Interface to R/3 のインストール」では、SAS/ACCESS Interface to R/3 のインストールについて順を追って説明します。SAS Data Surveyor for
これはつまり十進法ではなく、一進法を用いて自然数を表記するということである。とは いえ数が大きくなると見にくくなるので、.. 0, 1,
Windows Hell は、指紋または顔認証を使って Windows 10 デバイスにアクセスできる、よ
点から見たときに、 債務者に、 複数債権者の有する債権額を考慮することなく弁済することを可能にしているものとしては、
Q-Flash Plus では、システムの電源が切れているとき（S5シャットダウン状態）に BIOS を更新する ことができます。最新の BIOS を USB
に文化庁が策定した「文化財活用・理解促進戦略プログラム 2020 」では、文化財を貴重 な地域・観光資源として活用するための取組みとして、平成 32
自然言語というのは、生得 な文法 があるということです。 生まれつき に、人 に わっている 力を って乳幼児が獲得できる言語だという え です。 語の それ自 も、 から
