Presentation is loading. Please wait.

Presentation is loading. Please wait.

SQL による数独の解法 青山学院大学理工学部 矢吹太朗・佐久田博司. 数独とは何か ナンプレとも呼ばれ る制約充足問題 各行・列・ブロック に 1 から 9 の数字を一 つずつ当てはめる 新聞等に載っている ものはとても簡単 人間には難しいもの → もある.

Similar presentations


Presentation on theme: "SQL による数独の解法 青山学院大学理工学部 矢吹太朗・佐久田博司. 数独とは何か ナンプレとも呼ばれ る制約充足問題 各行・列・ブロック に 1 から 9 の数字を一 つずつ当てはめる 新聞等に載っている ものはとても簡単 人間には難しいもの → もある."— Presentation transcript:

1 SQL による数独の解法 青山学院大学理工学部 矢吹太朗・佐久田博司

2 数独とは何か ナンプレとも呼ばれ る制約充足問題 各行・列・ブロック に 1 から 9 の数字を一 つずつ当てはめる 新聞等に載っている ものはとても簡単 人間には難しいもの → もある

3 SQL で数独を解くことの意義 1. 非手続き的解法の優位性 – How ではなく What を記述すればよい – 手続き的解法では How が必要 例:『プログラミング言語 Ruby 』(オライリー, 2009 ) 2. オプティマイザのベンチマーク – オプティマイザの性質が、本解法に強く影響 – (結論:結合順序を最適化するべきではな い)

4 非手続き的解法の優位性

5 手続き的解法と非手続き的解法 手続き的解法非手続き的解法 問題 (What) 手続き (How) 実行 解 問題 (What) 実行 解

6 手続き的解法(容易な順) ネストした for 文による全探索(非現実 的) – 非手続き的解法と同程度に単純 探索の枠組み – 単純な { 幅 | 深さ } 優先探索 – Dancing Links: Knuth’s Algorithm X の実装 数独に特化したアルゴリズム

7 ネストした for 文(非現実的) for (v12=1; v12<=9; v12++) { for (v13=1; v13<=9; v13++) { if (v12!=1 && v12!=2 && v12!=3 && v12!=4 && v12!=5 && v12!=7 && v12!=8 && v12!=9 && v13!=1 && v13!=3 && v13!=4 && v13!=5 && v13!=6 && v13!=7 && v13!=8 && v13!=9 && v13!=v12) { print v12, v13; } ループ最深部の if 文の 評価回数は、 空白が増えると 指数関数的に増加

8 ネストした for 文(実行可能) for (v12=1; v12<=9; v12++) { if (v12 についての条件 ) { for (v13=1; v13<=9; v13++) { if (v12!=v13 && v13 についての条件 ) { print v12, v13; } 効率はよいが、 プログラムを書くのが面倒

9 SQL による解法(実行可能) SELECT v12, v13 FROM t12, t13 WHERE v12<>1 AND v12<>2 AND v12<>3 AND v12<>4 AND v12<>5 AND v12<>7 AND v12<>8 AND v12<>9 AND v13<>1 AND v13<>3 AND v13<>4 AND v13<>5 AND v13<>6 AND v13<>7 AND v13<>8 AND v13<>9 AND v12<>v13 非現実的なネストした for 文 に似ているが、これは実行可能

10 非手続き的解法の優位性 ネストした for 文(手続き 的) for (v12=1; v12<=9; …) for (v13=1; v13<=9; …) if (v12!=1 && …) print v12, v13; >>> このまま実行される (非現実的) SQL (非手続き的) SELECT x.n AS v12, … FROM x t12, x t13, … WHERE v12<>1 AND … >>> オプティマイザ >>> 実行プラン >>> 実行 □

11 オプティマイザのベンチマーク

12 最初の結果 RDBMS 実行時間 MySQL 5.1.41 1 秒程度 PostgreSQL 8.4.2 測定不能 Oracle 11.1 31 秒 SQL Server 2008 SP1 27 秒 DB2 9.7 FP1 測定不能 Firebird 2.1.3 測定不能 Athlon X2 3800+, 主記憶 1GB, Windows XP SP3 32bit

13 相違の原因:結合順序 空白 1 個にテーブル 1 個 が対応 テーブルの結合順序が 重要 – 直接の関連があるもの を結合させればよいは ず 右は FROM 句の記述通 りの結合順序 – 最適を目指すのは面倒 色の薄い部分に対応する テーブルが先に結合

14 MySQL のテーブル結合順序 FROM 句の記述通りの 順番で結合 テーブルにインデッ クスがあると、記述 通りにならないこと がある 安全のためには、 SELECT STRAIGHT_JOIN … 色の薄い部分に対応する テーブルが先に結合

15 PostgreSQL のテーブル結合順序 不適切な結合順序 – このままでは測定不能 FROM 句の記述通りの 順番で結合できるよ うに、コンマではな く「 CROSS JOIN 」 と書く 色の薄い部分に対応する テーブルが先に結合

16 Oracle のテーブル結合順序 結合順序は適切最適化を止める 時間がかかりすぎる SELECT /*+ ORDERED */ …

17 SQL Server のテーブル結合順序 結合順序は適切最適化を止める 時間がかかりすぎる SELECT … WHERE … OPTION (FORCE ORDER)

18 1. 結合順序が不適切 2. 結合方法が不適切 3. 条件が不適切な形に書き換えられる v12<>1 AND v12<>2 → v12 NOT IN (1,2) DB2 がダメな 3 つの理由

19 Firebird がダメな理由 不明

20 結合順序についてのまとめ RDBMS 結合順序の最適化対策 MySQL 5.1.41 FROM 句の記述通 り 不要 PostgreSQL 8.4.2 誤り最適化を止める Oracle 11.1 時間がかかる最適化を止める SQL Server 2008 SP1 時間がかかる最適化を止める DB2 9.7 FP1 誤りなし Firebird 2.1.3 不明なし

21 最終結果 RDBMS 最初の結果最終結果 MySQL 5.1.41 1 秒程度 PostgreSQL 8.4.2 測定不能 1 秒程度 Oracle 11.1 31 秒 1 秒程度 SQL Server 2008 SP1 27 秒 9秒9秒 DB2 9.7 FP1 測定不能 Firebird 2.1.3 測定不能 □

22 SQL による数独の解法のまとめ 1. 非手続き的解法の優位性 – How ではなく What を記述すればよい 2. オプティマイザのベンチマーク – 結合順序を最適化するべきではない MySQL :最適化していない(対策は不要) PostgreSQL :誤った最適化(最適化を止める) Oracle と SQL Server :時間のかかる最適化(最適化 をやめる) DB2 と Firebird では本解法は利用できない

23 今後の展望 他の RDBMS についての調査 本解法の適用性のソースコードレベルで の議論(オープンソースの RDBMS のみ) SQL で制約充足問題を解く一般的な方法の 検討

24 予備スライド

25 単純な { 幅 | 深さ } 優先探索 実は 9x9 の数独は簡単 1. 探索木を作る – 親ノード:空白を 1 つ選択 – 子ノード:入りうる数を入 れる 2. 単純な { 幅 | 深さ } 優先探索 で解ける Mathematica で約 10 行

26 数独に特化したアルゴリズムの 例 数字の候補が一つし かないところを探す 例: 7 行 8 列は「 8 」 簡単な問題は、これ を繰り返すだけで解 ける このようなアプロー チは数独では非推奨

27 SELECT t12.n AS v12,t13.n AS v13,t14.n AS v14,t15.n AS v15,t17.n AS v17,t19.n AS v19,t21.n AS v21,t23.n AS v23,t24.n AS v24,t26.n AS v26,t27.n AS v27,t28.n AS v28,t31.n AS v31,t32.n AS v32,t35.n AS v35,t36.n AS v36,t38.n AS v38, t39.n AS v39,t41.n AS v41,t42.n AS v42,t45.n AS v45,t46.n AS v46,t48.n AS v48,t49.n AS v49,t51.n AS v51,t53.n AS v53,t54.n AS v54,t56.n AS v56,t57.n AS v57,t58.n AS v58,t62.n AS v62,t63.n AS v63,t64.n AS v64,t65.n AS v65,t67.n AS v67,t68.n AS v68,t69.n AS v69,t72.n AS v72,t73.n AS v73,t74.n AS v74,t75.n AS v75,t76.n AS v76,t77.n AS v77,t79.n AS v79,t81.n AS v81,t83.n AS v83,t84.n AS v84,t85.n AS v85,t86.n AS v86,t87.n AS v87,t88.n AS v88,t91.n AS v91,t92. n AS v92,t94.n AS v94,t95.n AS v95,t96.n AS v96,t98.n AS v98,t99.n AS v99 FROM x t12,x t13,x t14,x t15,x t17,x t19,x t21,x t23,x t24,x t26,x t27,x t28,x t31,x t32,x t35,x t36,x t38,x t39,x t41,x t42,x t45,x t46,x t48,x t49,x t51,x t53,x t54, x t56,x t57,x t58,x t62,x t63,x t64,x t65,x t67,x t68,x t69,x t72,x t73,x t74,x t75,x t76,x t77,x t79,x t81,x t83,x t84,x t85,x t86,x t87,x t88,x t91,x t92,x t94,x t95,x t96,x t98,x t99 WHERE t12.n<>1 AND t13.n<>1 AND t14.n<>1 AND t15.n<> 1 AND t17.n<>1 AND t19.n<>1 AND t21.n<>1 AND t23.n<>1 AND t31.n<>1 AND t32.n<>1 AND t41.n<>1 AND t51.n<>1 AND t81.n<>1 AND t91.n<>1 AND t13.n<>t12.n AND t14.n<>t12.n AND t15.n<>t12.n AND t12.n<>7 AND t17.n<> t12.n AND t12.n<>9 AND t19.n<>t12.n AND t21.n<>t12.n AND t12.n<>3 AND t23.n<>t12.n AND t31.n<>t12.n AND t32.n<>t12.n AND t42.n<>t12.n AND t62.n<>t12.n AND t72.n<>t12.n AND t12.n<>4 AND t92.n<>t12.n AND t14.n<>t 13.n AND t15.n<>t13.n AND t13.n<>7 AND t17.n<>t13.n AND t13.n<>9 AND t19.n<>t13.n AND t21.n<>t13.n AND t13.n<>3 AND t23.n<>t13.n AND t31.n<>t13.n AND t32.n<>t13.n AND t13.n<>5 AND t53.n<>t13.n AND t63.n<>t13.n AND t73.n<>t13.n AND t83.n<>t13.n AND t15.n<>t14.n AND t14.n<>7 AND t17.n<>t14.n AND t14.n<>9 AND t19.n<>t14.n AND t24.n<>t14.n AND t14.n<>2 AND t26.n<>t14.n AND t14.n<>6 AND t35.n<>t14.n AND t36.n<>t14.n AND t14.n<>3 AND t54.n<>t14.n AND t64.n<>t14.n AND t74.n<>t14.n AND t84.n<>t14.n AND t94.n<>t14.n AND t15.n<>7 AND t17.n<>t15.n AND t15.n<>9 AND t19.n<>t15.n AND t24.n<>t15.n AND t15.n<>2 AND t26.n<>t15.n AND t15.n <>6 AND t35.n<>t15.n AND t36.n<>t15.n AND t45.n<>t15.n AND t15.n<>8 AND t65.n<>t15.n AND t75.n<>t15.n AND t85.n<>t15.n AND t95.n<>t15.n AND t17.n<>7 AND t19.n<>7 AND t24.n<>7 AND t26.n<>7 AND t35.n<>7 AND t36. n<>7 AND t46.n<>7 AND t56.n<>7 AND t76.n<>7 AND t86.n<>7 AND t96.n<>7 AND t17.n<>9 AND t19.n<>t17.n AND t27.n<>t17.n AND t28.n<>t17.n AND t17.n<>8 AND t17.n<>5 AND t38.n<>t17.n AND t39.n<>t17.n AND t57.n<>t17. n AND t67.n<>t17.n AND t77.n<>t17.n AND t87.n<>t17.n AND t17.n<>3 AND t19.n<>9 AND t27.n<>9 AND t28.n<>9 AND t38.n<>9 AND t39.n<>9 AND t48.n<>9 AND t58.n<>9 AND t68.n<>9 AND t88.n<>9 AND t98.n<>9 AND t27.n<> t19.n AND t28.n<>t19.n AND t19.n<>8 AND t19.n<>5 AND t38.n<>t19.n AND t39.n<>t19.n AND t49.n<>t19.n AND t19.n<>2 AND t69.n<>t19.n AND t79.n<>t19.n AND t99.n<>t19.n AND t21.n<>3 AND t23.n<>t21.n AND t24.n<>t21.n AND t21.n<>2 AND t26.n<>t21.n AND t27.n<>t21.n AND t28.n<>t21.n AND t21.n<>8 AND t31.n<>t21.n AND t32.n<>t21.n AND t21.n<>9 AND t41.n<>t21.n AND t51.n<>t21.n AND t21.n<>6 AND t81.n<>t21.n AND t91.n<>t21.n AND t23.n<>3 AND t24.n<>3 AND t26.n<>3 AND t27.n<>3 AND t28.n<>3 AND t31.n<>3 AND t32.n<>3 AND t42.n<>3 AND t62.n<>3 AND t72.n<>3 AND t92.n<>3 AND t24.n<>t23.n AND t23.n<>2 AND t26.n<>t23.n AND t27.n<>t23.n AND t28.n<>t23.n AND t23.n<>8 AND t31.n<>t23.n AND t32.n<>t23.n AND t23.n<>9 AND t23.n<>5 AND t53.n<>t23.n AND t63.n<>t23.n AND t73.n<>t23.n AND t83.n<>t23.n AND t23.n<>7 AND t24.n<>2 AND t26.n<>t24.n AND t27.n<>t2 4.n AND t28.n<>t24.n AND t24.n<>8 AND t24.n<>6 AND t35.n<>t24.n AND t36.n<>t24.n AND t54.n<>t24.n AND t64.n<>t24.n AND t74.n<>t24.n AND t84.n<>t24.n AND t94.n<>t24.n AND t26.n<>2 AND t27.n<>2 AND t28.n<>2 AND t 35.n<>2 AND t36.n<>2 AND t45.n<>2 AND t65.n<>2 AND t75.n<>2 AND t85.n<>2 AND t95.n<>2 AND t27.n<>t26.n AND t28.n<>t26.n AND t26.n<>8 AND t26.n<>6 AND t35.n<>t26.n AND t36.n<>t26.n AND t46.n<>t26.n AND t56.n<> t26.n AND t26.n<>4 AND t76.n<>t26.n AND t86.n<>t26.n AND t96.n<>t26.n AND t28.n<>t27.n AND t27.n<>8 AND t27.n<>5 AND t38.n<>t27.n AND t39.n<>t27.n AND t57.n<>t27.n AND t67.n<>t27.n AND t77.n<>t27.n AND t87.n<>t 27.n AND t28.n<>8 AND t28.n<>5 AND t38.n<>t28.n AND t39.n<>t28.n AND t48.n<>t28.n AND t58.n<>t28.n AND t68.n<>t28.n AND t28.n<>1 AND t88.n<>t28.n AND t98.n<>t28.n AND t38.n<>8 AND t39.n<>8 AND t49.n<>8 AND t69. n<>8 AND t79.n<>8 AND t99.n<>8 AND t32.n<>t31.n AND t31.n<>9 AND t31.n<>6 AND t35.n<>t31.n AND t36.n<>t31.n AND t31.n<>5 AND t38.n<>t31.n AND t39.n<>t31.n AND t41.n<>t31.n AND t51.n<>t31.n AND t81.n<>t31.n AN D t91.n<>t31.n AND t32.n<>9 AND t32.n<>6 AND t35.n<>t32.n AND t36.n<>t32.n AND t32.n<>5 AND t38.n<>t32.n AND t39.n<>t32.n AND t42.n<>t32.n AND t62.n<>t32.n AND t72.n<>t32.n AND t32.n<>4 AND t92.n<>t32.n AND t35. n<>9 AND t36.n<>9 AND t53.n<>9 AND t63.n<>9 AND t73.n<>9 AND t83.n<>9 AND t35.n<>6 AND t36.n<>6 AND t38.n<>6 AND t39.n<>6 AND t54.n<>6 AND t64.n<>6 AND t74.n<>6 AND t84.n<>6 AND t94.n<>6 AND t36.n<>t35.n A ND t35.n<>5 AND t38.n<>t35.n AND t39.n<>t35.n AND t45.n<>t35.n AND t35.n<>8 AND t65.n<>t35.n AND t75.n<>t35.n AND t85.n<>t35.n AND t95.n<>t35.n AND t36.n<>5 AND t38.n<>t36.n AND t39.n<>t36.n AND t46.n<>t36.n AN D t56.n<>t36.n AND t36.n<>4 AND t76.n<>t36.n AND t86.n<>t36.n AND t96.n<>t36.n AND t38.n<>5 AND t39.n<>5 AND t57.n<>5 AND t67.n<>5 AND t77.n<>5 AND t87.n<>5 AND t39.n<>t38.n AND t48.n<>t38.n AND t58.n<>t38.n A ND t68.n<>t38.n AND t38.n<>1 AND t88.n<>t38.n AND t98.n<>t38.n AND t49.n<>t39.n AND t39.n<>2 AND t69.n<>t39.n AND t79.n<>t39.n AND t39.n<>7 AND t99.n<>t39.n AND t42.n<>t41.n AND t41.n<>5 AND t41.n<>3 AND t45.n <>t41.n AND t46.n<>t41.n AND t41.n<>9 AND t48.n<>t41.n AND t49.n<>t41.n AND t51.n<>t41.n AND t53.n<>t41.n AND t41.n<>6 AND t62.n<>t41.n AND t63.n<>t41.n AND t81.n<>t41.n AND t91.n<>t41.n AND t42.n<>5 AND t45.n t42.n AND t46.n<>t42.n AND t42.n<>9 AND t48.n<>t42.n AND t49.n<>t42.n AND t51.n<>t42.n AND t42.n<>1 AND t53.n<>t42.n AND t42.n<>6 AND t62.n<>t42.n AND t63.n<>t42.n AND t72.n<>t42.n AND t42.n<>4 AND t92.n<>t42. n AND t45.n<>5 AND t46.n<>5 AND t48.n<>5 AND t49.n<>5 AND t51.n<>5 AND t53.n<>5 AND t62.n<>5 AND t63.n<>5 AND t73.n<>5 AND t83.n<>5 AND t45.n<>3 AND t46.n<>3 AND t48.n<>3 AND t49.n<>3 AND t54.n<>3 AND t56.n <>3 AND t64.n<>3 AND t65.n<>3 AND t74.n<>3 AND t84.n<>3 AND t94.n<>3 AND t46.n<>t45.n AND t45.n<>9 AND t48.n<>t45.n AND t49.n<>t45.n AND t54.n<>t45.n AND t45.n<>8 AND t56.n<>t45.n AND t64.n<>t45.n AND t65.n<> t45.n AND t45.n<>4 AND t75.n<>t45.n AND t85.n<>t45.n AND t95.n<>t45.n AND t46.n<>9 AND t48.n<>t46.n AND t49.n<>t46.n AND t54.n<>t46.n AND t46.n<>8 AND t56.n<>t46.n AND t64.n<>t46.n AND t65.n<>t46.n AND t46.n<>4 AND t76.n<>t46.n AND t86.n<>t46.n AND t96.n<>t46.n AND t49.n<>9 AND t57.n<>9 AND t67.n<>9 AND t69.n<>9 AND t77.n<>9 AND t87.n<>9 AND t49.n<>t48.n AND t57.n<>t48.n AND t58.n<>t48.n AND t48.n<>2 AND t67.n<>t48. n AND t68.n<>t48.n AND t69.n<>t48.n AND t48.n<>1 AND t88.n<>t48.n AND t98.n<>t48.n AND t57.n<>t49.n AND t58.n<>t49.n AND t49.n<>2 AND t67.n<>t49.n AND t68.n<>t49.n AND t69.n<>t49.n AND t79.n<>t49.n AND t49.n<>7 AND t99.n<>t49.n AND t53.n<>t51.n AND t54.n<>t51.n AND t51.n<>8 AND t56.n<>t51.n AND t57.n<>t51.n AND t58.n<>t51.n AND t51.n<>2 AND t51.n<>6 AND t62.n<>t51.n AND t63.n<>t51.n AND t51.n<>3 AND t81.n<>t51.n AND t91.n<>t51.n AND t53.n<>1 AND t54.n<>1 AND t56.n<>1 AND t57.n<>1 AND t58.n<>1 AND t62.n<>1 AND t63.n<>1 AND t72.n<>1 AND t92.n<>1 AND t54.n<>t53.n AND t53.n<>8 AND t56.n<>t53.n AND t57.n<>t53.n AND t58.n<>t53. n AND t53.n<>2 AND t53.n<>6 AND t62.n<>t53.n AND t63.n<>t53.n AND t73.n<>t53.n AND t83.n<>t53.n AND t53.n<>7 AND t54.n<>8 AND t56.n<>t54.n AND t57.n<>t54.n AND t58.n<>t54.n AND t54.n<>2 AND t64.n<>t54.n AND t6 5.n<>t54.n AND t54.n<>4 AND t74.n<>t54.n AND t84.n<>t54.n AND t94.n<>t54.n AND t56.n<>8 AND t57.n<>8 AND t58.n<>8 AND t64.n<>8 AND t65.n<>8 AND t75.n<>8 AND t85.n<>8 AND t95.n<>8 AND t57.n<>t56.n AND t58.n<>t 56.n AND t56.n<>2 AND t64.n<>t56.n AND t65.n<>t56.n AND t56.n<>4 AND t76.n<>t56.n AND t86.n<>t56.n AND t96.n<>t56.n AND t58.n<>t57.n AND t57.n<>2 AND t67.n<>t57.n AND t68.n<>t57.n AND t69.n<>t57.n AND t77.n<>t5 7.n AND t87.n<>t57.n AND t57.n<>3 AND t58.n<>2 AND t67.n<>t58.n AND t68.n<>t58.n AND t69.n<>t58.n AND t88.n<>t58.n AND t98.n<>t58.n AND t67.n<>2 AND t68.n<>2 AND t69.n<>2 AND t79.n<>2 AND t99.n<>2 AND t62.n<>6 AND t63.n<>6 AND t65.n<>6 AND t67.n<>6 AND t68.n<>6 AND t69.n<>6 AND t81.n<>6 AND t91.n<>6 AND t63.n<>t62.n AND t64.n<>t62.n AND t65.n<>t62.n AND t62.n<>4 AND t67.n<>t62.n AND t68.n<>t62.n AND t69.n<>t62.n AN D t72.n<>t62.n AND t92.n<>t62.n AND t64.n<>t63.n AND t65.n<>t63.n AND t63.n<>4 AND t67.n<>t63.n AND t68.n<>t63.n AND t69.n<>t63.n AND t73.n<>t63.n AND t83.n<>t63.n AND t63.n<>7 AND t65.n<>t64.n AND t64.n<>4 AND t67.n<>t64.n AND t68.n<>t64.n AND t69.n<>t64.n AND t74.n<>t64.n AND t84.n<>t64.n AND t94.n<>t64.n AND t65.n<>4 AND t67.n<>t65.n AND t68.n<>t65.n AND t69.n<>t65.n AND t75.n<>t65.n AND t85.n<>t65.n AND t95.n<>t65. n AND t67.n<>4 AND t68.n<>4 AND t69.n<>4 AND t76.n<>4 AND t86.n<>4 AND t96.n<>4 AND t68.n<>t67.n AND t69.n<>t67.n AND t77.n<>t67.n AND t87.n<>t67.n AND t67.n<>3 AND t69.n<>t68.n AND t68.n<>1 AND t88.n<>t68.n AND t98.n<>t68.n AND t79.n<>t69.n AND t69.n<>7 AND t99.n<>t69.n AND t73.n<>3 AND t75.n<>3 AND t76.n<>3 AND t77.n<>3 AND t79.n<>3 AND t81.n<>3 AND t83.n<>3 AND t91.n<>3 AND t73.n<>t72.n AND t74.n<>t72.n AND t7 5.n<>t72.n AND t76.n<>t72.n AND t77.n<>t72.n AND t79.n<>t72.n AND t81.n<>t72.n AND t72.n<>4 AND t83.n<>t72.n AND t91.n<>t72.n AND t92.n<>t72.n AND t72.n<>7 AND t74.n<>t73.n AND t75.n<>t73.n AND t76.n<>t73.n AND t77.n<>t73.n AND t73.n<>1 AND t79.n<>t73.n AND t81.n<>t73.n AND t73.n<>4 AND t83.n<>t73.n AND t91.n<>t73.n AND t92.n<>t73.n AND t73.n<>7 AND t75.n<>t74.n AND t76.n<>t74.n AND t77.n<>t74.n AND t74.n<>1 AND t79.n <>t74.n AND t84.n<>t74.n AND t85.n<>t74.n AND t86.n<>t74.n AND t94.n<>t74.n AND t95.n<>t74.n AND t96.n<>t74.n AND t76.n<>t75.n AND t77.n<>t75.n AND t75.n<>1 AND t79.n<>t75.n AND t84.n<>t75.n AND t85.n<>t75.n AN D t86.n<>t75.n AND t94.n<>t75.n AND t95.n<>t75.n AND t96.n<>t75.n AND t77.n<>t76.n AND t76.n<>1 AND t79.n<>t76.n AND t84.n<>t76.n AND t85.n<>t76.n AND t86.n<>t76.n AND t94.n<>t76.n AND t95.n<>t76.n AND t96.n<>t7 6.n AND t77.n<>1 AND t79.n<>t77.n AND t87.n<>t77.n AND t88.n<>t77.n AND t77.n<>7 AND t98.n<>t77.n AND t99.n<>t77.n AND t79.n<>1 AND t87.n<>1 AND t88.n<>1 AND t98.n<>1 AND t99.n<>1 AND t87.n<>t79.n AND t88.n<>t 79.n AND t79.n<>7 AND t98.n<>t79.n AND t99.n<>t79.n AND t81.n<>4 AND t83.n<>t81.n AND t84.n<>t81.n AND t85.n<>t81.n AND t86.n<>t81.n AND t87.n<>t81.n AND t88.n<>t81.n AND t81.n<>7 AND t91.n<>t81.n AND t92.n<>t8 1.n AND t83.n<>4 AND t84.n<>4 AND t85.n<>4 AND t87.n<>4 AND t88.n<>4 AND t91.n<>4 AND t92.n<>4 AND t84.n<>t83.n AND t85.n<>t83.n AND t86.n<>t83.n AND t87.n<>t83.n AND t88.n<>t83.n AND t83.n<>7 AND t91.n<>t83.n AND t92.n<>t83.n AND t85.n<>t84.n AND t86.n<>t84.n AND t87.n<>t84.n AND t88.n<>t84.n AND t84.n<>7 AND t94.n<>t84.n AND t95.n<>t84.n AND t96.n<>t84.n AND t86.n<>t85.n AND t87.n<>t85.n AND t88.n<>t85.n AND t85.n 7 AND t94.n<>t85.n AND t95.n<>t85.n AND t96.n<>t85.n AND t87.n<>t86.n AND t88.n<>t86.n AND t94.n<>t86.n AND t95.n<>t86.n AND t96.n<>t86.n AND t88.n<>t87.n AND t87.n<>7 AND t87.n<>3 AND t98.n<>t87.n AND t99.n<> t87.n AND t88.n<>7 AND t88.n<>3 AND t98.n<>t88.n AND t99.n<>t88.n AND t98.n<>7 AND t99.n<>7 AND t92.n<>t91.n AND t91.n<>7 AND t94.n<>t91.n AND t95.n<>t91.n AND t96.n<>t91.n AND t98.n<>t91.n AND t99.n<>t91.n AN D t92.n<>7 AND t94.n<>t92.n AND t95.n<>t92.n AND t96.n<>t92.n AND t98.n<>t92.n AND t99.n<>t92.n AND t94.n<>7 AND t95.n<>7 AND t95.n<>t94.n AND t96.n<>t94.n AND t98.n<>t94.n AND t99.n<>t94.n AND t96.n<>t95.n AND t95.n<>3 AND t98.n<>t95.n AND t99.n<>t95.n AND t96.n<>3 AND t98.n<>t96.n AND t99.n<>t96.n AND t98.n<>3 AND t99.n<>3 AND t99.n<>t98.n; 約 12000 字


Download ppt "SQL による数独の解法 青山学院大学理工学部 矢吹太朗・佐久田博司. 数独とは何か ナンプレとも呼ばれ る制約充足問題 各行・列・ブロック に 1 から 9 の数字を一 つずつ当てはめる 新聞等に載っている ものはとても簡単 人間には難しいもの → もある."

Similar presentations


Ads by Google