情報処理学会 インタラクション 2017
IPSJ Interaction 20173-405-58
2017/3/2

Pict-Doku:ペイントツールに基づく数独問題自動作成システムの提案
土橋拓馬 † 谷尾祐香里† 越後宏紀† 上河恵理† 阿原一志†
概要：数独（ナンバープレース）は多くの人に親しまれているペンシルパズルである．Pict-Doku の従来システム[1]は入力画像に基づく数独問題自動作成システムとして提案された．従来システムでは，数独を解くだけではなく問題を自分で作る楽しみ方もあるという動機から，ユーザが準備した画像を原画として数独の問題を自動作成するものであった．しかし，ユーザの表現できるデザインの幅が狭いという問題点もあった．そこで本稿では，ペイントツールの機能を追加し，ユーザが描いたイラストを原画とするような数独の問題を容易に自動作成するシステムを提案，実装した．

Pict-Doku: A Proposal of Automatic Generator System of Sudoku
Problems Based on a Painting Tool
TAKUMA TSUCHIHASHI† YUKARI TANIO†HIROKI ECHIGO† ERI KAMIKAWA† KAZUSHI AHARA†
Abstract: Sudoku is a pencil puzzle which is very familiar to many people all over the world. Pict-Doku is an

automatic generator system of sudoku problems based on illustrations. In the previous version, we suppose that joyof sudoku is not only solving a given problem but also generating an original sudoku problem over an original clue
design. The system needs users to prepare an original picture, and it has lower interactivity to edit the design ofclues. Thus, in current, we added a function of painting tool, and we suggest and implement an automatic generator
system of sudoku problems that allows users to make a new sudoku problem from a user’s original painting.

数独は図 1 のような，世界的に有名なペンシルパズルの1.

一種である．数独に関しては様々な観点から研究が行われはじめにている．その代表的なものは，ヒント（数独の問題を解くために予め入っている数字のこと）の個数の下限に関するものや，解法アルゴリズム・作問アルゴリズムに関するもの，難易度評価に関するものである．
従来システム[1]では，数独のヒントのデザインへのユーザの反応について重点をおいて，システムを実装した．ここでは，ユーザが準備した画像を元にシステムが数独の問題を自動作成する．しかし，ユーザはまずデザインの元となる画像を自分で準備する必要があり，システムのインタラクティビティは高くなかった．
そこでユーザが求めるデザインをより容易にかつインタラクティブに実現可能にしたものが，本稿の Pict-Doku である．本システムには，ユーザがシステム付属のペイントツールで描いたイラストをそのまま数独の問題のヒントの図案に反映させるという機能を持たせた．さらに，ヒントの配置のみではなく，イラストに使用された色も問題図案に反映させることで，ユーザが数独の問題のヒントの図案
図1

Figure1数独の例をインタラクティブに楽しめるように実装した．

Example of sudoku† 明治大学 先端メディアサイエンス学科 Department of Frontier Media Science© 2017 Information Processing Society of Japan859

情報処理学会 インタラクション 2017
IPSJ Interaction 20173-405-58
2017/3/2

関連研究

2.

数独に関する研究はヒントの個数の下限に関する Gary
McGuire らの研究[2]や，作問アルゴリズムに関する座間らの研究[3]や，問題の難易度評価に関する土井らの研究[4]がある．これらの研究はいずれも数独を数理的な観点から評価したものである．
一方で従来システム[1]では，数独問題作成手法の既存研究を参考にしながら，ヒントのデザインとユーザにとっての数独の楽しさとの関係を研究のテーマとした．そのために，ユーザが準備したイラストをもとにしてヒントの図案を自動生成する数独問題作成システムの実装と検証を行った．本稿ではこの従来システムに機能を追加することにより，ユーザにとって数独の作問をより直観的に楽しめることの検証を目的とした．
本システムにおいて主に追加された機能は以下の 3 つである．
1)

ペイントツールを内蔵し，ペイントツ―ルに描かれた図案をもとにヒントの位置を自動生成する．
2)

ペイントツールで使用された色を数独の問題図案に反映させる．
3)

システムが自動作成する問題に難易度の指標を表示する．
これらの詳細については 3 章で説明する．

3.2 難易度判定
本システムにおいては，自動作問するときに作成された問題の難易度を表示する機能を設けた．難易度評価を実装するにあたって，本稿では，土出らの難易度判定[4]を参考に解法手段によって難易度を判定することとした．ただし本稿では，難易度評価が適切であるかどうかよりも問題が自動作成されたときに難易度指標が付与されることによるユーザビリティを問題にしたい．解法手段には様々な名称があるが，本稿では Hodoku[6]に記載されている名称を参考に以下のようなものを使用した．
・naked single: 特定のマスに入る数字の候補が 1 つしかないとき，その数字が入る．
・hidden single: ある行，列，3×3 のブロックごとに特定の数字の入るマスが１つしかないとき，その数字が入る．
・Locked Candidates type1(Pointing):

3×3 のブロック内においてある数字が特定の行，列に限定されるとき，その行，列でブロックの外に同じ数字が入らない．
・naked pair: ある行，列，3×3 のブロックにおいて，特定の 2 つの数字のみが候補であるマスが 2 つあるとき，その 2 つ以外のマスにその 2 つの数字は入らない．
・hidden pair: ある行，列，3×3 のブロックにおいて，特定の 2 つの数字が候補として入るマスが 2 つしかないとき，そのマスにはその 2 つの数字しか入らない．
・X-Wing: 特定の 2 つの行，列においてある数字が候補システムの実装

3.

提案システムは Processing2.2.1 を使用して実装した．以
下ではペイントツール，ヒントデザインの生成アルゴリズとして入るマスがそれぞれ 2 か所ずつしかないとき，その行，列における他のマスにはその数字が入らない．
以上の 6 つの手段を実装し，難易度レベルを設定した．

ム，難易度評価アルゴリズム，作問アルゴリズムについて
表 1 解法の難易度レベル

述べる．

Table1

3.1 ペイントツールとヒントデザインの生成アルゴリズ
ム

難易度
ペイントツールは越後らが提案した PomPom[5]を参考にレベル

Levels of solving techniques

解法実装した．ペイントツールにおいては，色は色相環から自由に選べるものとし，ペンの太さは一定で変えられないように設定した．ペイントツールによって作られたイラスト
から数独の問題におけるヒントのデザインの生成アルゴリ
ズムは以下の通りである．

レベル 1

naked single, hidden single

レベル 2

Locked Candidates type1

レベル 3

naked pair

レベル 4

hidden pair

レベル 5

X-Wing①ペイントツールで描かれたイラストを読み込み，ピクセル単位でグレースケールデータと RGB データの両方を保存する．
②グレースケールデータからフィルタリング処理によって，エッジ検出された画像に変換する．
③②の画像を 9×9 のマスに分割し，全体のヒント数が30~45 になるように閾値を設定し，ヒントの位置を決定する．
④③で決定したヒントのマスを①の RGB データで色付けする．

© 2017 Information Processing Society of Japan

3.3 作問アルゴリズム
作問アルゴリズムは従来システムと同様に，とん氏が述べているものを実装した[7]．作問する過程において一意的な回答を作成するが，その際に 3.2 節の方法により難易度を評価するようにした．

860

情報処理学会 インタラクション 2017
IPSJ Interaction 20173-405-58
2017/3/2

以下のアルゴリズムはとん氏が述べているもの[7]の[5,pp.105-106]から引用したもので，数字が決まらなかったマスの数を最小にするという方法である．
①ヒント配置を入力する．
②①で入力したヒント位置に，ルールに違反しないように 数字をランダムに入れる．
③ヒントの数字を変更する．
③-1 ヒントを 1 個選ぶ．
③-2 選んだヒントの数字を変更する．
③-3 解ける問題ならば終了．
③-4 ソルバーによって数字が決まらなかったマスの数 が減った場合，その変更を採用する．
④③へ戻る．ただし，どのヒントを変更しても上記のマスの数が減らない場合は②へ戻る．
3.4 提案システム
以上のような仕様のシステム全体を俯瞰すると以下の
図3

図 2 のようになる．

モニターによる作例図Figure3

Examples by monitors

意見を聞き取った（事後アンケート）．アンケート内容は以下の通りである．
①

事前アンケート・年齢はいくつか．
（10 代・20 代・30 代・40 代・50 代以上）
・数独でよく遊ぶか． （はい・いいえ）
・数独の問題を自分で作ったことがあるか．
（はい・いいえ）・もし数独の問題を自分で作ることができるとしたら解いてみたいと思うか．
（とても思う・少し思う・あまり思わない・全く思わない）
システムの概要図・数独の問題図案が絵になっていると楽しいと思うか．

Procedure of generating a sudoku（とても思う・少し思う・あまり思わない・全く思わない）

図2
Figure2

・数独の問題について，デザインと難易度のどちらかを選
図 2 ように，ユーザが本システムに付属するペイントツべるとすれば，どちらを重視するか． （デザイン・どちらールで描いたイラストをもとにヒントの配置・色を決定し，かと言えばデザイン・どちらかと言えば難易度・難易度）

数独の問題を自動作成する．ヒントの位置はマウスクリッ・ヒント（初めに数字が埋まっている場所）の個数の少なクにより容易に編集することができる．編集されたヒント

い数独の問題を作成することに興味があるか．の位置に応じて問題が自動作成される．また，点対称機能（とても興味がある・少し興味がある・あまり興味がない・及び線対称機能があり，ヒントの位置が点対称または線対全く興味がない）称である問題をユーザが容易に作成できるようにした．図・難易度の高い数独の問題を作成することに興味がある

3 はモニターによる作例である．

か． （とても興味がある・少し興味がある・あまり興味がない・全く興味がない）

4.

ユーザビリティ

4.1 ユーザビリティ検証と調査
本システムのユーザビリティの調査としてアンケートを・ヒントの位置が同じでいろいろな問題を作ることができるとしたら面白いと思うか．
（とても思う・少し思う・あまり思わない・全く思わない）
・ヒントの数が同じでいろいろな形の問題を作ることがで実施した．はじめに数独に関する経験や被験者の考え方をきるとしたら面白いと思うか．

聞き（事前アンケート），その後システムの説明をして実際（とても思う・少し思う・あまり思わない・全く思わない）にシステムを使ってもらい，その後に本システムに対する© 2017 Information Processing Society of Japan861

情報処理学会 インタラクション 2017
IPSJ Interaction 20173-405-58
2017/3/2

・数独の問題を自分で作ることができるソフトがあったと

また，新しい機能のうち，ペイントツール機能に対してしたらどのような使い方をしてみたいか． （自由回答）

は，「より自分の作りたいものを反映させられると思う」「よ②り創造性が増して作るのが楽しくなったと思う」といった事後アンケート

・Pict-Doku を使うと数独の問題が容易に作成できると思っ肯定的な意見が多かった．問題のヒントへの色付け機能にたか．

ついても「カラフルで気分が晴れやかになる」という意見（とても思う・少し思う・あまり思わない・全く思わない）があり，否定的な意見はほとんど見られなかった．しかし，・Pict-Doku でヒントの図案を編集する機能は使いやすいと難易度の設定機能に関しては，どの回答者も問題を作成す思ったか．

る段階でそこまで気にしていないように感じられた．

（とても思う・少し思う・あまり思わない・全く思わない）

ユーザの描いたイラストが問題のデザインに生かされた・Pict-Doku で絵をドラッグアンドドロップした結果、そこかどうかについては，「ペイントツールで描いたものが数独にあらわれたヒントの図案が元の絵を反映していると思っの問題図案に反映されていると思ったか」という質問に対たか．

して「9×9 という制約がある中で良く反映されていると感（とても思う・少し思う・あまり思わない・全く思わない）じる」という意見や「反映されているが自分の描きたかっ・前作の Pict-Doku に比べて、本作ではペイントツールをたものにはならない」といった両論が出された．

追加した．このことについての意見や感想はあるか． （自由回答）
・ペイントツールで描いたものが数独の問題図案に反映されていると思ったか． （自由回答）

5.

まとめと今後の課題
Pict-Doku ではペイントツールで描いたイラストを原画

・そもそもペイントツールは使いやすいと思ったか． （自とする数独の問題を自動作成するシステムを提案した．本由回答）

来，数独の問題を作成することは数理的な作業であるが，・ペイントツールにあったとしたらいいと思う機能はある

このシステムを用いることによって感覚的にアプローチをか．（ユーザインタフェースについて意見があればそれもすることができるようになった．イラストを描くことによ書くこと．） （自由回答）ってユーザのイメージに近い数独の問題を作成できたた・作ったファイル名． （作ったファイルを提供していただめ，従来システムよりもより楽しく数独の問題を作成できいた場合のみ．）

た．そのため，数独の楽しさをより多くの人に伝える一助

4.2 検証と調査の結果になることが考えられる．

アンケートの回答者は 19 名，年齢構成は次の通りであ今後，ユーザの描いたイラストをもとに数独の問題のヒる．10 代が 1 名，20 代が 17 名，30 代が 0 名，40 代が 0ントの配置を決定し実際に問題を作成するときに，システ名，50 代以上が 1 名である．

ムによって生成されたヒントの配置で数独のルールを満た

まず，事前アンケートでは「数独の問題を自分で作るこすように問題を作成することができるのかを自動で判定すとができるとしたら解いてみたいと思うか」「数独の問題図る機能や，「解き味」の良い問題を作成できるような工夫を案が絵になっていると楽しいと思うか」という質問に対し，していきたい．

19 名中 14 名が「とても思う，少し思う」と回答した．また，「ヒントの位置が同じでいろいろな問題を作ることができるとしたら面白いか」「ヒントの数が同じでいろいろな問謝辞本システムのアンケートにご協力頂いた皆様に，謹んで感謝の意を表する．

題を作ることができるとしたら面白いか」という質問に対しても 19 名中 14 名が「とても思う，少し思う」と回答し，参考文献

従来システムでのアンケートに比べて全体的に数独の問題[1] 谷尾祐香里，越後宏紀，上河恵理，阿原一志. Pict-を作ることに興味を示すような傾向にあった．
次に，事後アンケートでは「Pict-Doku を使うと数独の問題が容易に作成できると思うか」という質問に対して 19 名

Doku: 入力画像に基づく数独問題自動作成システムの提案. ゲームプログラミングワークショップ論文集,
2016, p.89-93.

全員が「とても思う，少し思う」と回答した．しかし，「Pict-[2] Gary McGuire, Bastian Tugemann, Gilles Civario. There isDoku で絵をドラッグアンドドロップした結果，ヒントの図

no 16- Clue Sudoku: Solving the Sudoku Minimum

案が元の絵を反映していると思うか」という質問に対して

Number of Clues Problem, 2012, p.1-40.

は「とても思う，少し思う」という回答が半分以上を占め[3] 座間翔，篠埜功. 初期配置が指定された場合に適したたものの，中にはこの機能を使用しなかったという回答も

数独問 題 生成手法の提案および実装, 情報処理学会

見られ，新機能を加えた分，従来システムの機能が生かさ

研究報告, Vol.2016-GI-35 No.1, 2016, p.1-7.

れなくなったということが分かった．

© 2017 Information Processing Society of Japan862

情報処理学会 インタラクション 2017
IPSJ Interaction 20173-405-58
2017/3/2[4] 土出智也，真貝寿明. 数独パズルの難易度推定―解法ロジックを用いた数値化の提案―. Memoirs of the
Osaka Institute of Technology, Series A Vol. 56, No. 1,
2011, p.1-18.
[5] 越後宏紀，宮下芳明. PomPom:紙巻きオルゴール漫画の制作支援システムの提案. 映像情報メディア学会技術報告, 2016, p.269-272.
[6] “HoDoKu”. http://hodoku.sourceforge.net/en/index.php, (参照 2016-12-26).
[7] とん. ナンプレの自動生成，岩波データサイエンス
Vol.2, 2016, p.101-109.

© 2017 Information Processing Society of Japan863