「世界で一番難しい数独」の難しい問題 38
ストーリー by hylom
難しい問題を作るのは難しい 部門より
難しい問題を作るのは難しい 部門より
あるAnonymous Coward 曰く、
東京大学の渡辺宙志助教が、スパコンを用いて「世界で一番難しい数独」を作る試みを行っている。この結果、氏が「2013年3月現在、おそらく世界で一番難しい問題」を発表したのだが、実はこれは人間が簡単に解くことができる問題だった模様。
「難易度の定義」は難しいが、数独の解法とされている「Pencil Marks法」や「Recursive Backtracking法」を使い、探索に必要となる深さを難易度の尺度にしたという。が、判定アルゴリズムにミスがあり、難しくない問題を「難しい」と誤判定していた模様。これを修正した「難しい数独」が再度公開されている。
楽しい問題 (スコア:2)
この手の話題で（たまに）ナンプレファンで話題にするのは「解いてて楽しい問題」を自動生成するアルゴリズムなんですが、この「楽しい問題」っていうのが定義がなかなか難しい。自動生成されたものだと、解いてて確かにつまらない問題っていうのがあって、面白さも数値化できそうな気はするんですけどねー。
#オフトピだけどID
LIVE-GON(リベゴン)
Re:楽しい問題 (スコア:2)
難しすぎると途中で挫折。簡単すぎるとつまらない。
ニコリって本当にすごいと思う。
Copyright (c) 2001-2014 Parsley, All rights reserved.
Re:楽しい問題 (スコア:1)
Recursive Backtrackingを採用してしまっているので
最終的に修正を重ねてでてきた問題が
解いていて楽しくない問題に出来上がっていますね
最終的に絞られた候補の中から
投機的に数値を仮定して解き進めて
矛盾が出た段階で投機実行時点まで戻る
（実際といてみたら確かにそうでした）
という解法を強いられるのでじゃあ計算機で総当りで解くのを
人間が肩代わりしてるだけじゃねぇか
という感情に襲われる数独問題の典型だと思います
Re: (スコア:0)
それ言ったらパズルなんてみんな基本はそんなもんだぞ。人間は直感で枝刈りできるけど、無意識に似たようなこと
やってる(パターンを用いた先読み結果の連想キャッシュってのが表現としては近いか？)。
難しいってのは枝刈りに使えるデータを減らすことだから(安易に決定できなくなるから難しい=その分先読みが必要)。
投機的に数値を実行してみなきゃいけない、というのも脳内で一度に処理するには組み合わせが膨大すぎるから、
投機的な判断を下すことで矛盾に突き当たるまでのステップ数を擬似的に減らしてるだけ。当然このラインも個人に
依存する。だ
Re:楽しい問題 (スコア:1)
楽しさは難しさとかとはちょっと違いますよ。最初に埋められる数字を1から探していってそれが9だと「なんだかなあ」って思う。別に1から埋めるように作る必要はないがかといって9876という順番で埋めるように作る必要もない。ほか、必然的に埋められる場所が1個ずつしか現れないナンプレだと、難しいっていうよりつまらないわけで、解いていく過程での緩急が楽しさに繋がってたりする。
LIVE-GON(リベゴン)
Re: (スコア:0)
申し訳ない、同じように楽しさと難しさはまた別のものであると言うことを言っているつもりでた。
だから「一番難しい問題を作りました」の結果出てくるものはどのような手法を使って求めた
にしても「つまらない問題」になると言いたかった。
# 「楽しい」のは先に書いたとおりギリギリ読み切れるライン、だと思うので人ごとに違う。
# だからこそ、パズル集では初級とかのランク分けされてるんだと思う。
ちなみに自分のやり方はその局面ごとに一番埋まっている列や数字など自由度の
少ないものからトライするので1から順とか考えたことないし、最初に埋まるのが9で
も「なんだかな」というのはないですね。
そもそも数字の大小は解放となんの関係もないと思ってますし。
# もちろん、最初にトライしたからと言って最初に埋まるわけでもない。
# 列やブロック、数字ごとの盤面状況で重みつけて投機実行ですね。
Re:楽しい問題 (スコア:1)
>難しい数独作りました、ってのはどんな手法で作っても同じ感想を抱くことになると思う。
これはBack Tracking解法に関しては全く違うと思います
そこにはパズルとしての超えられない境界が存在します
現時点で盤上で得られる情報のみをヒントに使用することにより
最低どこかひとつのマスは一意に数値を決められ
その謎解きを繰り返しとくことによって
最終的に盤面の数値をすべて埋められるのは確かに「パズル」ですが
現時点で盤上で得られる情報ではどのマスも
一意には数値を埋められない局面が存在し
そこから先の局面に進むには選択肢の一番少ないマスに対して
投機的に数値を埋めて無理やり局面を進める必要がある
というのはパズルではなくただの組み合わせ試行問題で
「パズル」としての面白さはないと思います
あなたと私で同じパズルの早解き競争をしました
結果私が勝ちました勝負の分かれ目は二択投機実行局面で
たまたま私は正解を先に実行し
あなたははずれのほうを先に投機実行したからです
ではつまらんでしょ？
Re: (スコア:0)
どうなんだろう。詰め将棋とかだとありがちな状況だと思うんだけど、
これはパズルに入らないって事かな。
競争するシチュエーションにおいて出題するには向いてないのかもしれないね。
ただ、投機実行にしても盤面からの枝刈りとか工夫できる部分もあるから
つまらないか、と言われるとそれはそれで有りかなぁ、実際高難度の数独
だとそういう問題にも普通に出会うし。あれはパズルじゃなかったんだろうか?
次にトライする数値を決めるにも普通に枝刈りするし、そもそも一つしかな
い状況だと作業になるから自分はむしろおもしろくないんだよね。
# そもそも回答速度を競争するというのをあまり
Re: (スコア:0)
実際高難易度の問題には存在しますが
私はあれはパズルとは感じませんね
>「縦横3x3の3つをチェックすれば必ず1つの数字が判明する」事でそれを繰り返すこと
>で手戻りなく全部埋まると言うことを意味して、これだと確認作業になるって事ね。
>自分はこのレベルは機械的にすすめるので特に楽しいって事はないなぁ。
私はbacktrackingが入った時点で人の手で解いて面白いパズルだとは思わないですね
http://www.sudokugame.org/solv/
少なくとも上記の解き方の中で紹介されている手法を複合的に
Re: (スコア:0)
出てきた問題がbacktraking必須だから
手でやるだけ時間の無駄とか話題になってましたね
http://games.slashdot.org/comments.pl?sid=2956211&cid=40540437
I've tried my own sudoku solver on it which puposefuly doesn't do the guessing/backtracking stuff. It didn't solve one single number. So, you might not want to waste time on trying by hand.
バックトラッキングが必須な時点で
人の手で解いて面白い問題じゃないよ
というのは割りと万国共通なようで
Re: (スコア:0)
詰め将棋の喩えはかなり近いと思う。
長くて難しいのが楽しいかと言われると違うと思うし、それでもすごいとは思う。
問題のヒントが意外なところに隠されていて、それを発見できたときの瞬間の歓びが大きい。
「これ、ここに気が付くと一気に片付くぞ～」とかね。
一種のAha体験。
Re: (スコア:0)
開始時の配置がきれいな模様になっていたりとか楽しいですよね。
Re: (スコア:0)
ナンプレといわれるとやはり違和感があるなぁ。世間的には同じなのかも、いや、国内じゃそっちのほうが知られているのかもしれないが
Re:楽しい問題 (スコア:1)
数独はニコリの商標ですから、ナンプレと発言するのが礼儀なのです。
Re: (スコア:0)
全てのパズルに当てはまると思うんだけど、
「あれ？もしかしてあのピースをはめると全部解けるんじゃないか？」
というような、難しさの中にある発見、があると楽しさを感じる。
それを予め用意しておくパズル製作者は天才だと思う。
回答は簡単 (スコア:2)
問題を作るのは大変・スパコンが必要なんでしょうが、回答はやっぱり簡単ですね。
昔作った解法プログラムで計算してみたら、サクッと回答が出てきました。
# そりゃ人が挑戦すると大変でしょうけどね
答え：
146285793
725963814
398741256
851634927
932178645
467529138
683492571
579316482
214857369
Re:回答は簡単 (スコア:3, 興味深い)
回答にかかる時間を比較してみた。
使ったのはこれ [srad.jp]（深さ優先探索（Recursive Backtrackingと同じかな）だけで解を全部探すし、遅い）。
「失敗」というやつがいちばん時間がかかった。
究極のアルゴリズム 対 究極の難問 を見てみたい。
love && peace && free_software
t-nissie
Re: (スコア:0)
最近ではGoogle先生が回答してくれます。
Re: (スコア:0)
カメラでとれば、解いてくれるものなかったかな
Re: (スコア:0)
理詰めで正解だけ確実に埋めていくには大変だけれども、まずは埋めて間違っていたらやり直しみたいな投機実行的なやり方だとあっさりとけるとかなのかなあ。
Re: (スコア:0)
回答が１つ問題だと結構あっさり解けますよ
その方法、次にどの枠を埋めるかって選び方によってずいぶんと時間がかわるんですよ
その時点の枠で一種類の数字しか置けない枠があればもちろんおくが、
なければ置ける数字の数が少ない方、同じならどれだけ、周りに影響をあたえられるで選ぶ。（多分）
（但し、少ない方がいいことが多いけど、そうでない場合もあるようでなかなか難しい。あまり枠選びに時間がけてもね）
１つも数字が置いてない白紙の問題で全回答を出すってのをすると我がＰＣでは終わりそうもなかった。
Re: (スコア:0)
むしろ一意に解けないものはできそこないではないかと。
わざわざスパコン使わなくても (スコア:0)
論理型言語のAlloy使って一番難しい問題を簡単に解けたはず
Re: (スコア:0)
いいなー。 (スコア:0)
東大暇そうだね。
Re:いいなー。 (スコア:2)
欧米ではチェスプログラムは人工知能研究の一環として認められるけど、
日本では将棋プログラムはゲームや遊びとしてしか認められず、
研究として行うのは難しいと聞いたことがある。
Re: (スコア:0)
> 欧米ではチェスプログラムは人工知能研究の一環として認められるけど、
研究者の努力で認めさせただけのことですし、日本でも(たぶん世界のどこでも)事情は同じです
Re: (スコア:0)
落としどころ：
学術研究の応用分野を広げるために、やはり日本も軍隊を持とう(笑)
Re: (スコア:0)
手段のためなら目的を選びません。(ｷﾘｯ)
Re: (スコア:0)
＞学術研究の応用分野を広げるために、やはり日本も軍隊を持とう(笑)
どういう部隊をどれくらい編成すると有効か研究するために
部隊編成、移動、戦闘をシミュレートする物を作ろう！
# バグのほとんど無い（比較的最近の）大戦略が欲しい・・・
Re: (スコア:0)
ご冗談を。
人の話を聞く人達と、聞かない人達では前提条件が異なります。
「オレを説得してみろ。説得できれば金を出してやる。」
「ただし説得されるつもりも、話を聞くつもりもない。そもそもお前の言ってることは難しすぎてよく分からん。」
こんな状況で説得しろと言われてもねえ？
Re: (スコア:0)
黙ってても金降ってくるし
Re: (スコア:0)
黙ってるわけじゃないんじゃない？ 勢い余って役に立たない研究してるだけで。
c.f. 業績リスト [u-tokyo.ac.jp]
Re: (スコア:0)
黙ってても金が降ってくるポストなら誰だって欲しい。
壮絶な奪い合いの末に努力で勝ち取ったポストなんじゃないのかな
Re: (スコア:0)
そりゃそうだ、才能あるやつは暇なもんだ
無能なやつほど忙しいフリしてるしな
Re: (スコア:0)
リンク先の解説の後半見たら、数独はNP完全問題であるとか、
スピングラス系との類似性も指摘されているとか色々書いてありますね。
要は物性物理の手法が応用できるらしいとやってみたら失敗したと。
最新の数学、物理に密接に関連しているんだと感心したが、同時に
最近の東大助教は「〜だった件」という言い回しをタイトルに
使うんだということも分かった。
絶望した！ (スコア:0)
ここまで、未踏スーパークリエータにも、物理の詩人にも言及がないスラドに絶望した！