SAS program to solve Sudoku (sudokuを解くSASPRG)
>100 Views
January 27, 26
スライド概要
SAS言語を中心として，解析業務担当者・プログラマなのコミュニティを活性化したいです
関連スライド
各ページのテキスト
SAS program to solve Sudoku (sudokuを解くSASPRG) Miyuki Aso (麻生 美由紀) Statistical & Quantitative Sciences Japan Takeda Pharmaceutical Company Limited 28 January 2026 @ Osaka-SAS Ben. (大阪SAS勉強会)
免責事項 / Disclaimer 本日の内容および意見は、発表者個人の見解であり、所属組織の公式な見解を示すものではありませ ん。内容に基づく判断・行動は、参加者ご自身の責任においてお願いいたします。 The views and opinions expressed in this presentation are those of the speaker and do not necessarily reflect the official views of their organization. Any decisions or actions taken based on the content of this presentation are the sole responsibility of the participants. 2
Abstract: SudokuパズルをBase SASの機能のみで且つ1秒未満で解くことができるSASPRGを作成したので、簡単に 紹介する。 I’ve developed a SAS program that can solve Sudoku puzzles using only Base SAS functionality in under one second, and I’d like to give you a brief introduction. 3
Introduction: What is Sudoku? (数独とは？) ⚫ Sudoku is a logic-based number placement puzzle (named by Nikoli in 1984). ⚫ The game consists of a 9x9 grid divided into nine 3x3 subgrids or “boxes”. ⚫ The goal is to fill the grid so that: 1. Each column 2. Each row, and 3. Each 3x3 box Contains the numbers 1 through 9 without repeating any numbers within those sections. ⚫ Though the grid starts with some numbers pre-filled (called “givens”), solving Sudoku requires logical thinking—not guesswork. ⚫ It’s a popular brain exercise worldwide! 4 Q0 8 5 1 4 1 8 2 9 3 1 2 3 4 6 2 6 7 8 9 1 8 9 2 7 5 4 6 1 https://www.nikoli.co.jp/ja/puzzles/sudoku/
Introduction: Past attempts to solve Sudoku using SAS ⚫ 日本での過去の論文・発表 • 「数独パズルを解くSASプログラム」（2011）: https://www.sas.com/content/dam/SAS/ja_jp/doc/event/sasuser-groups/usergroups11-b-07.pdf • 「Sudoku-Solving System by SAS®」(2012): https://support.sas.com/resources/papers/proceedings12/2252012.pdf • 「Excelで数独解答プロセスをリアルタイムで可視化するSASプログラム」(2014): https://www.sas.com/content/dam/SAS/ja_jp/doc/event/sas-user-groups/usergroups14-d-17.pdf ⚫ 海外の論文も多数存在（若干古め） • 「SAS® And Sudoku」(2007): https://ksdata.ku.edu/ksdata/sashttp/SGF2007/SASandSudoku-011-2007.pdf • 「Yet Another Sudoku Solver: PROC FCMP 」(2012): https://support.sas.com/resources/papers/proceedings12/433-2012.pdf • 「Solving Samurai Sudoku Puzzles – A First Attempt」(2013): https://analytics.ncsu.edu/sesug/2013/BB-01.pdf 5
- https://www.sas.com/content/dam/SAS/ja_jp/doc/event/sas-user-groups/usergroups11-b-07.pdf
- https://support.sas.com/resources/papers/proceedings12/225-2012.pdf
- https://www.sas.com/content/dam/SAS/ja_jp/doc/event/sas-user-groups/usergroups14-d-17.pdf
- https://ksdata.ku.edu/ksdata/sashttp/SGF2007/SASandSudoku-011-2007.pdf
- https://support.sas.com/resources/papers/proceedings12/433-2012.pdf
- https://analytics.ncsu.edu/sesug/2013/BB-01.pdf
Introduction: My current attempt to solve Sudoku using SAS ⚫ 「数独 プログラム」で検索すると、Python・R・JavaScript・Excel VBA・C言語などの様々な言語を用いた様々なPRGが紹介されている 無論普通に解くのが一番面白いのですが… ⚫ 解法のアプローチは大きく分けて2パターン： 1. 人間の解き方をPRGを再現する 2. CPUにしかできない解き方を実装する（総当たり、複雑な連立方程 式・論理式を構築して解く、バックトラック法など） ⚫ 今回はバックトラック法を実装したSASPRGを紹介する ⚫ 数独を解くSASプログラムに関する論文は約10-15年前の論文が多い ので、2026年現在のSAS Ver.で作成してみたらどうなるのか？ ⚫ SAS OnDemand for Academics（SAS Studio, SAS9.4M7, Base SAS） 内 で開発（趣味 自己研鑽のため） 6 ↑https://www.nikoli.co.jp/ja/puzzles/sudoku/ より抜粋 ※参考：人間の数独の解き方の基本はこちら 「数独のルールと解き方」 https://www.nikoli.co.jp/ja/wpcontent/uploads/2023/02/sd41_rule.pdf
Example Puzzle: Easy Sudoku 簡単な数独の例題を3問用意します E1 E2 2 3 4 5 8 9 5 1 1 7 6 3 9 4 7 8 4 3 2 2 3 7 6 2 2 1 3 4 8 9 3 9 5 9 3 1 4 9 5 4 5 1 5 4 3 8 8 https://mainichi.jp/articles/20211213/org/00m/040/001000c 1 6 8 2 7 7 8 7 6 1 4 2 3 9 9 1 4 8 8 https://www.nikoli.co.jp/ja/wp-content/uploads/2023/02/sd41_rule.pdf 7 1 8 3 6 7 3 8 9 6 6 6 1 8 8 9 4 2 E3 7 1 4 9 5 6 8 2 2 3 7 1 https://sudokujapan.com/blog/category/sudoku-story/
Example Puzzle: Hard Sudoku 難しい数独の例題を3問用意します H1 H2 5 3 1 8 2 7 1 4 5 1 6 3 2 5 3 5 3 9 2 8 5 1 9 3 7 https://gigazine.net/news/20100822_hardest_sudoku/ 6 1 4 7 7 2 3 2 4 3 http://www.aisudoku.com/en/AIsudoku_Top10s1_en.pdf 4 4 8 2 3 1 3 8 6 7 8 6 4 8 9 9 6 9 7 5 7 3 H3 9 7 4 8 9 2 6 7 1 7 5 9 8 6 http://www.aisudoku.com/en/AIsudoku_Top10s1_en.pdf
Methodology : 事前準備 Prerequisite ⚫ 開発環境： SAS OnDemand for Academics (SAS studio) (SAS 9.4M7) ⚫ CARDSステートメントで盤面を再現したSASデータセットを作成（空白セルには0を入れておく） →必ず数値変数 c1-c9, 9変数9オブザベーション のSASデータセットとする H1 5 3 8 2 7 1 4 5 5 1 3 7 3 6 6 2 8 5 9 4 3 9 7 SASデータセット 9
Methodology : Backtracking Method Backtracking Method (バックトラック法)とは？ 計算問題やパズルを解くための探索アルゴリズムの一種で、「すべての可能性を試しながら解を見つける」 方法です。ただし、途中で「これ以上進んでも解が見つからない」と判断できる場合、そこから先の探索を やめて戻る（バックトラックする）効率的な仕組みが特徴です。 タテヨコBOXをみてそのセルに入る可能性のある数字を小 さい数から順番に試し、矛盾が生じたらストップする 矛盾なく数字が入れられるセルまで逆戻りする。このセルの 場合7がダメだったので次に入りそうな数字の9を入れてみる 数字を入れた次のセルから数字を入れる試行を再開、途中 で矛盾が生じたらまたストップして逆戻りする 1 1 9 1 2 5 3 4 6 2 8 3 6 7 5 ? 2 5 3 4 6 8 8 2 7 1 4 6 あれ？ 3 5 3 7 4 6 1 8 1 一つ戻って 9を入れよう 5 5 3 6 6 2 7 1 5 3 9 7 9 6 7 2 7が入った！ 次は2行目だ！ 3 あれ？ 7 3 9 8 5 5 8 4 1 4 7 3 9 9 3 8 8 4 5 4 6 2 2 7 7 3 ? 5 5 1 10 7 6 2 8 5 9 4 3 9 7 これをすべ ての数字が 矛盾なく埋 まるまで続 ける
Methodology : Implementing the Backtracking Method in a SAS Program
How can the Backtracking Method be implemented in a SAS program?
-> By using the FCMP procedure to handle arrays or matrices.
The FCMP procedure (FCMPプロシジャ)とは？
SASにおいてユーザー定義関数 (Ex.1) および サブルーチン(Ex.2) を作成するために用いるプロシジャ
(参考: https://documentation.sas.com/doc/ja/pgmsascdc/9.4_3.5/proc/p10b4qouzgi6sqn154ipglazix2q.htm)
<Ex.1 : function statement >
<Ex.2 : subroutine statement >
proc fcmp outlib=work.functions.func;
function addedtaxf(price, taxrate);
totalp=int(price+price*taxrate*0.01);
return(totalp);
endsub;
quit;
proc fcmp outlib=work.functions.func;
subroutine addedtaxs(price, taxrate, totalp);
outargs totalp;
totalp=int(price+price*taxrate*0.01);
endsub;
quit;
options cmplib=work.functions;
data ts1;
item="5 kilos-rice"; kakaku=4580; zeiritsu=8;
pricet=addedtaxf(kakaku,zeiritsu);
run;
options cmplib=work.functions;
data ts2;
call missing(pricet);
item=" 5 kilos-rice"; kakaku=4580; zeiritsu=8;
call addedtaxs(kakaku,zeiritsu,pricet);
run;
11
関数とサブルーチン
の定義の仕方と呼び
出し方の違いに注目
（Ex1とEx2の結果は
同じ）
Methodology : Implementing the Backtracking Method in a SAS Program
The FCMP procedure (FCMPプロシジャ)とは？（続き）
SASにおいてユーザー定義関数およびサブルーチンを作成するために用いるプロシジャ
→加えて、FCMP内では行列操作 (Ex.3) や 配列を引数とした関数の作成 (Ex.4) を行うことも可能！
（参考: https://www.docswell.com/s/6484025/K6VDQE-2025-04-15-043654,
https://documentation.sas.com/doc/ja/pgmsascdc/9.4_3.5/proc/p0f3ukbprxtdfrn1cljibie17wzn.htm）
<Ex.3 : array statement and call transpose>
<Ex.4 : function statement with varargs option>
proc fcmp;
array mt1[2, 3] (1,2,3,4,5,6);
array trn_mt1[3,2] / nosymbols;
call transpose(mt1, trn_mt1);
rc=write_array("dsmt1", mt1);
rc=write_array("dstrn_mt1", trn_mt1);
quit;
proc fcmp outlib=work.functions.func;
function summation(y[*]) varargs;
total=0;
do i=1 to dim(y);
total=total + y[i];
配列を引数
end;
にするとき
return(total);
に指定する
endsub;
オプション
quit;
転置を行うための
サブルーチン
options cmplib=work.functions;
data ts1;
a=1;b=2;c=3;d=4;e=5;
array A2E[5] a b c d e;
x=summation(A2E);
run;
→これら (Ex.1 ～ Ex.4) のFCMPプロシジャの機能を活用して、sudokuパズルを解くためのPRGを開発することに
した！ (実装するアルゴリズムの詳細は次ページに記載)
12
Methodology : Implementing the Backtracking Method in a SAS Program 【Details of the algorithm to be implemented (実装するアルゴリズムの詳細)】 1. Create a function in FCMP to check whether a candidate number already exists in a given row, column, or 3×3 box. （FCMPで、候補数字が指定された行・列・3×3のBOXに既に存在するかを確認するための関数を作成する。） 2. From the Sudoku dataset, generate arrays for rows, columns, and boxes within FCMP (total 9 × 3 = 27 arrays). （Sudokuデータセットから、FCMP内で行・列・ BOX用の配列を生成する（合計で9×3＝27個の配列）） 3. Treat the 9×9 Sudoku board as a matrix in FCMP and use a DO loop to iterate forward from [1,1] → [1,2] → … → [9,9], trying to place numbers while validating constraints. （FCMPで9×9のSudoku盤面を行列として扱い、DOループで[1,1] → [1,2] → … → [9,9]の順に前進しながら、制約 を確認しつつ数字を配置する。） 4. If a contradiction occurs (no valid number can be placed), switch to backward traversal in the DO loop, undoing previous placements until a valid restart point is found. （矛盾が発生した場合（有効な数字が配置できない場合）、DOループを後退させ、再開可能な地点が見つかる まで前の配置を取り消す。） 5. Resume forward traversal from the restart point, continuing the trial-and-error process. （再開ポイントから前進処理を再開し、試行錯誤を続ける。） 6. Repeat this forward/backward cycle until all cells [9,9] are filled without contradictions, then exit the loop. （この前進・後退のサイクルを繰り返し、[9,9]まで矛盾なくすべてのセルが埋まったら、ループを終了す る。） 13
Methodology : Materials used in the FCMP procedure 0 0 5 3 0 0 0 0 0 8 0 0 0 0 0 0 2 0 0 7 0 0 1 0 5 0 0 4 0 0 0 0 5 3 0 0 0 1 0 0 7 0 0 0 6 0 0 3 2 0 0 0 8 0 0 6 0 5 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 9 7 ☜array inp[9,9]: 問題の盤面のmatrix Input Matrix Array Used to Validate and Update Data Each row Each column 0 0 5 3 0 0 0 0 0 0 8 0 4 0 0 0 0 0 0 0 5 8 0 0 0 7 0 9 8 0 0 0 0 0 0 2 0 0 0 7 0 1 0 6 0 0 3 0 0 0 0 0 0 1 0 3 0 0 7 0 0 1 0 5 0 0 5 0 0 0 0 3 0 4 0 0 0 0 0 2 0 5 0 0 0 0 4 0 0 0 0 5 3 0 0 3 0 0 0 0 2 5 0 0 4 0 0 0 1 0 0 0 3 0 1 0 0 7 0 0 0 6 0 0 1 0 7 0 0 0 0 0 0 5 0 7 0 2 0 0 0 0 3 2 0 0 0 8 0 0 0 0 5 0 0 0 0 9 3 0 0 0 0 6 0 8 0 0 6 0 5 0 0 0 0 9 0 0 5 3 0 0 0 0 7 0 6 0 0 0 4 0 0 0 0 0 4 0 0 0 0 3 0 0 2 0 0 0 8 0 3 0 5 0 0 0 0 0 0 0 9 0 0 0 0 0 9 7 0 0 0 0 0 0 6 0 9 0 0 0 0 9 0 3 0 7 0 0 array trn_Ri[1,9]: i行目のarray array trn_Cj[1,9]: j列目のarray Output Matrix ☜array outp[9,9]: 解答を埋めるためのmatrix 14 Each box array trn_Bz[1,9]: z番目のBOXのarray *BOX番号zの取得のため次の計算式を 用いる:行番号をi, 列番号をjとすると、 z=mod(i+2, 3)*3+mod(j+2, 3)+1
Implementation : Overview 1 The implemented code: %sudoku_solver() (sudoku_solver.sas) • 約650行のSASPRG、SASマクロとして作成 (proc fcmpの定義部分：約400行) • *PharmaForest / devil のSASパッケージの1つとして2025/7/25に公開 (Ver. 0.1) • 全コードはこちら： https://github.com/PharmaForest/devil/blob/main/devil/06_macros/sudoku_solver.sas *PharmaForest / devil DEVIL (Developer’s Ideas Library) https://github.com/PharmaForest/devil Devilパッケージは、PharmaForestの中でも「遊び心」と「コラボ」を目的とした 特別なSASパッケージです。 どんな段階のアイデアでも歓迎し、試作・デモ・メンバー募集・冗談ネタなど、 自由に使って楽しむことを目指しています。 作者は「Any Developers」とされており、有用性よりも「面白さ」「悪ノリ」も 含めた発想を重視する、開かれた共同開発の場です。（※README.mdをAI要約） 15
SAS Package Short Tips: How to Use the SAS Package
SASパッケージを使うにはどうしたらいいの？
-> 自分のローカルの環境にフォルダを作成し、その中にGitHubからダウンロードしたSPFinit.sasを入れ
て、下記のコードをご自身のSAS環境で実行するだけで%sudoku_solver()が使えるようになります。
-> Let’s implement the following steps and code.
filename packages "C:\Users\XXXXXX\saspackage";
%include packages(SPFinit.sas);
%installPackage(devil, mirror=PharmaForest);
%installPackage(misc, mirror=PharmaForest);
%loadPackage(devil);
* Download the SPFinit.sas file from the below link and save it in your own directory.
https://github.com/yabwon/SAS_PACKAGES/tree/main/SPF
** If you would like to use the devil package, please install both the devil package and the misc package.
16
Implementation : Overview 2 A log file An RTF file *Here is the SAS code you need to write to run %sudoku_solver(); data sudoku1; input c1-c9 8.; cards; 005300000 800000020 070010500 400005300 010070006 003200080 060500009 004000030 000009700 ; %sudoku_solver(puzzle=sudoku1, outputpath=[set your own path], rtfYN=[N or Y]); Input: • a SAS dataset (a sudoku puzzle filled 0 to blank, c1-c9, 9obs) 17 Output: • Intermediate SAS datasets (only in work library) • sudoku_answer.log • sudoku_answer.rtf (if you set to Y in ‘rtfYN=‘)
Implementation : Code explanation *[function 1] A function to check the possible numbers; function check_row(value, Q[*]) varargs; total=0; do p=1 to dim(Q); if Q[p]=value then total+1; end; return(total); endsub; *[function 2] A subroutine to solve Sudoku.; subroutine solve_sudoku(rx, cy, kz, numbt, __backtrack); outargs __backtrack; (…) do until (__backtrack=numbt); (…) end; rc=write_array('__sudoku__ans', outp); endsub; KEY POINT The SAS macro %sudoku_solver() has only one function and one subroutine! • check_row()は候補数字が指定された行・列・ 3×3のBOXに既に存在するかを確認するための 関数 • check_row()をsolve_sudoku()の中で何回も呼び出 す • solve_sudoku()内で数独を解くためのMaterialsの 準備、 Backtracking Method、解答盤面作成のプ ロセスを実行している • solve_sudoku()内ではdo untilやdo i=1 to 9のよう なdo loopやleave(do loopから離脱)を活用してい る 全コードはこちら：https://github.com/PharmaForest/devil/blob/main/devil/06_macros/sudoku_solver.sas 18
Results : 結果： • 事前に用意した例題全問(E1からH3まで)を解くことができた • おおむね1秒未満で解答を導き出すことに成功した • 実行結果は以下の通り： Puzzle Solved? Processing Time Num of BKTR E1 〇 0.249 sec. 39 E2 〇 0.13 sec. 185 E3 〇 0.125 sec. 3 H1 〇 0.299 sec. 2855 H2 〇 0.201 sec. 2577 H3 〇 1.107 sec. 33968 • • These programs are executed on SAS Studio. Despite slight variations in execution time across environments, it consistently delivered an answer in just about one second. 解答LOG: sudoku_answer.log 19
Discussion Backtracking MethodをSASプログラムで再現できたのか？ • DO LOOP内の処理を工夫することによってBacktracking Methodのようなものを実装することができた(終了条件に達した時 Leaveステートメントを用いる、現在処理中のセルの位置の取得、DOの逆順で処理するなど) ≒ 疑似的な再帰処理の実装？ • 9*9の行列形式の問題を解くにあたって、IMLなどのパッケージを導入しなくても知恵とコードの工夫次第で、十分事足りる ことがわかった • PROC FCMPにて関数やサブルーチンを定義する有用性を示すことができた • →によって、SASにおけるデータ処理の際の時間の短縮につながるかもしれない Recursion (再帰処理)とは？ ある処理の実行中に、その処理自身を呼び出して冒頭から実行すること （※SAS® Help Centerによると、一応FCMPプロシジャでも再帰を実装することは可能らしい https://documentation.sas.com/doc/ja/pgmsascdc/9.4_3.5/proc/n1712ebq466zztn1qli0vyf0e4v8.htm） 勇気がある方はぜひSASでの再帰処理の実装を試していただきたいのですが、 趣味の範囲にとどめることを推奨します 20
Conclusion ⚫ 結論：Base SASの機能(SAS9.4M7以降)でも、FCMPプロシジャ内の関数定義・サブルーチン定義にお いて、主にDO LOOPを使ってPRGコードを工夫することでBacktracking Methodを表現することが可能 であり、それによって数独パズルを解けることが分かった。 ⚫ 最後に： • どんな言語であってもPRGを試行錯誤してロジックを工夫して何か一つのものを作成するのは楽しい！ • それがたとえ、それをするのに向いていない言語で作られたものあっても、自分で模索しながら頑張った 成果は何かの役に立つと信じています（個人的願望） • みなさんもSASで面白そうなことを実装したら…ぜひdevilパッケージにjoinしてみては Thank you for your attention! 21 ?
References 1. ニコリ「数独の遊び方、ルール、解き方」 URL: https://www.nikoli.co.jp/ja/puzzles/sudoku/ 2. 第11回大阪sas勉強会 森岡 裕「Proc FCMPで行列計算」 URL: https://www.docswell.com/s/6484025/K6VDQE-2025-04-15-043654 3. SAS Institute Inc. “The FCMP Procedure” (PROC FCMP Documentation). URL: https://documentation.sas.com/doc/ja/pgmsascdc/9.4_3.5/proc/p10b4qouzgi6sqn154ipglazix2q.htm 4. GitHub - SAS_PACKAGES “SAS Packages Framework” URL: https://github.com/yabwon/SAS_PACKAGES 5. GitHub - PharmaForest “PharmaForest” URL: https://github.com/PharmaForest 22