パズルを出題しあうスレ

パズルを出題してそれを解くプログラムを作るスレです。
みんなで楽しくアルゴリズムを考えましょう。

ずるしてらくしてかれいに２げっと

では数学板で見かけた問題。

ネズミが一匹、無限の広さをもつ碁盤の上に居る。
プレーヤーは一ターンの間にネズミの居ない任意の座標にブロックを一つおくことができる。
ネズミは一ターンの間に上下左右のいずれかの方向に一歩動くことができる。
ただし、ブロックのある座標には移動できない。

ネズミの四方がブロックで囲まれ、一歩も動けない状態になればプレーヤーの勝ち。
ネズミがいつまでも逃げることができればネズミの勝ち。
プレイヤーの先行として、ゲームはどちらが勝つか。

このゲームはプレイヤーが勝つことが数学板で証明されていたので
最短手数を求めてください。

数学板の面白い問題おしえて〜な 11問目の381に載ってました。

もう一問だしときますね。

ｎ個の異なる文字を並べてできる長さnの文字列を考える。
このような文字列はn!個あるがこのn!個の文字列を
一列に並べ、隣り合う文字列がちょうど2文字だけ異なるように
するアルゴリズムを作れ。

たとえば3文字なら
abc
acb
bca
bac
cab
cba
と並べれば隣り合う文字列がちょうど2文字違うようになります。

>>5
それって任意のnに対して可能なの？

グレイ符号が応用できそうな予感

スマソ
意味が分からん

n = 4 で普通に並べてみた

abcd
abdc
acbd ↑ ここがだめ
acdb
adbc ↑ ここがだめ
adcb
bacd ↑ ここがだめ
badc
bcad ↑ ここがだめ
bcda
bdac ↑ ここがだめ
bdca
cabd ↑ ここがだめ
cadb
cbad ↑ ここがだめ
cbda
cdab ↑ ここがだめ
cdba
dabc ↑ ここがだめ
dacb
dbac ↑ ここがだめ
dbca
dcab ↑ ここがだめ
dcba

こういう意味か

確かにグレイコードで置き換えたらうまくいくと思う

普通に全通りの並べ方をしらみつぶしにやればいいんじゃね？
計算時間？しらね。

単純に、隣り合う二文字を入れ替えた。

#include <stdio.h>
#include <string>
using namespace std;

int factorial(int i) {
　if(i==0) {
　　return 1;
　}
　else if(i>0) {
　　return i*factorial(i-1);
　}
　else {
　　exit(1);
　}
}

void main() {
　int i,n;
　string s;
　char t;

　printf("enter the number of sequence\n");
　scanf("%d",&n);
　for(i=0;i<n;i++) s+=(char)(i+'a');
　for(i=0;i<factorial(n);i++) {
　　printf("%d: %s\n",i,s.c_str());
　　t=s[i%n]; s[i%n]=s[(i+1)%n]; s[(i+1)%n]=t;
　}
}

誰かこれ解くプログラム書いて。
http://yoshimaruxxx.web.fc2.com/sentunagi.html

>>11
実行してみたけど重複する文字列があるみたい。

これって結局階乗を出す問題だよね。
交換だけで階乗が出せればかなり有名になっているはずだから、スマートな解法はないと思う。

>>14
階乗を出すってどういうこと？

順列ですた。
という事で、順列を交換だけで出せるのって話です。

文字列を頂点として２文字違う文字列に辺があるグラフを考えれば
ハミルトン閉路問題に帰着される。
辺の数は結構多いし、ハミルトン閉路はありそうにも思えるがさて。

グラフの作成に O(n!) かかるのでは。
結局しらみつぶしと同じ予感。

もともと出力のサイズがn!なんだからそれは気にすること無い。
しらみつぶしの計算量は(n!)!なんだから全然違う。

普通出力ってひとまとめで一処理とみなす気が

出力の大きさがO(n!)なんだからどんなにがんばったって計算量がO(n!)を下回ることはない。
出力をひとまとめで一処理なんておかしいよ。

n文字の場合の結果をつかってn+1文字の場合を解けないものか。

　　　　　　　, -: ':　:　:　:　:　:　:"⌒:￣:` : ､
　　　　　 ／:　:　:　: へ._　:　:　:　:へ、:　:　: ＼
　　　 __,く;へ＿:　: :|　:　:　:　:　:　:　: ＼￣:ヽ、＼
.　　 /:__/:　:　:/:　: |: :ｌ:　:　:　:　:　:　:　: ＼.:　:ヽ: ヽ
　　/_//:　:　:/:　/ :|:　ｌ:　:　:ヽ:　ヽ:　:　:　: ヽ:　: ヽﾊ
／/: /: : : : : |: : ｌ: : |: : |: : ヽ: :ヽ: : ヽ: : : : : : :ヽ: : ヽﾊ
. /:/: /: /: ｌ: |: :,|: : ﾊ: : |: : : ヽ: :ヽ: : ヽ: : : : : : :ヽ : ヽ|
//: : ｌ: :ｌ: ::|: :|: :|: : :| ヽ ｌヽ : : :＼: ヽ.: :＼: : : ヽ:ﾊ: : : |
| ｌ: : |: :|: : |: :|: ハ__,L. ヽ　＼"￣｢ T ト- ､;_: : : : :|: : :.|
| |: : |: :|: : |: ;|イ｢ ヽ|　　 ＼´＼ヽ __｣__ｉ.＼ ＼ : : |: : :|　　もう・・・仕方の無いことばかり言って・・・
| |: : |: :|: : くｖ'　_｣＝ｉ　　　　ヽ ／｢ ｉ::::::o｢＼|ヽﾄ: |: :/|
ｉ ｌ: : ﾊ: ｌ: : :.ト / {:::::::〉　　　　　　 ﾚﾍ:.::::}ﾟｉ|/|: ::| .}ﾚ': :|
　∨:| Ｖﾍ: ::ﾍヽ　ｖﾍ:ﾊ　　　　　　 ..く_二ｉつ|: :.:ﾚ: :| : :|
　　ヽヽ∨へ:ﾊ　　ヾツ　　　 　　　　/／//ﾊ:/::|: :|: : :|
　　　　　 ∧: :ｉ:ﾍ.ｌ // 　　`　　　　　　　　/: {:::::|: :ｌ: : ﾊ
　　　　　/:/: ∧: ＼　　　　　｡　　　　　,.ｲ:|: :|::ｉ:::|: :ｌ: ::∧
　　　　 //:　:　:}:　ヽ`ｉ:: ､. 　　　　　／　.|::| :|:::ｉ::::|: ｉ:: : ∧
　　 　://:　:　: ハ:　ヽ::::::ノＴ ' ‐ '　　　　|::|: :Ｖ::::ｉ∧: : : : ﾍ
　　 /／:　:　ノ二 ヽ:　:＼ 〈ｰ ､ ＿＿___,ﾄﾍ: :∨::ｉ::∧: : : :.∧
　／/:/　/⌒ ＼　 ヽト､: :ヽ＼__＿＿___ハ ＼:∨ﾊ:::∧: : : :} ＼

>>3
ネズミの問題は２３手詰めと出た。この手順はピンとこないけど、うまく収束している。

┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼┼┼┼　┼┼●┼┼　┼┼●○┼　┼┼●○┼　┼┼●┼┼　┼┼●┼┼
┼┼┼○┼　┼┼┼○┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼○┼　┼┼┼○┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼●
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼

┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●●┼　┼┼●●┼　┼┼●●┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼○┼　┼┼┼○┼　┼┼○┼┼　┼●○┼┼
┼┼┼○●　┼┼┼○●　┼┼┼┼●　┼┼┼┼●　┼┼┼┼●　┼┼┼┼●
┼┼┼┼┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼

┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼
┼●┼┼┼　┼●┼┼┼　┼●┼┼┼　┼●┼┼┼　┼●┼┼┼　┼●●┼┼
┼┼○┼●　┼┼○┼●　┼┼┼┼●　┼┼┼┼●　┼┼○┼●　┼┼○┼●
┼┼┼●┼　┼●┼●┼　┼●○●┼　┼●○●┼　┼●┼●┼　┼●┼●┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼

┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼
┼●●┼┼　┼●●┼┼　┼●●┼┼　┼●●●┼　┼●●●┼　┼●●●┼
┼○┼┼●　●○┼┼●　●┼○┼●　●┼○┼●　●┼┼┼●　●┼●┼●
┼●┼●┼　┼●┼●┼　┼●┼●┼　┼●┼●┼　┼●○●┼　┼●○●┼
┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼

自己レス>>24
ただし、ブロックの置き方はネズミの八方のみしか探索していないので。

正解なのかどうかすらわからん

テストケースの組み合わせを自動生成してくれるプログラム作ってくれんか？
たとえば入力を2,3,3としたら以下のような文字を出力してくれるような。
言葉ではうまく言えないが全ての組み合わせを生成してくれるやつ。

○、○、○、○、○、○、○、○、○、　、　、　、　、　、　、　、　、　
　、　、　、　、　、　、　、　、　、○、○、○、○、○、○、○、○、○
○、○、○、　、　、　、　、　、　、○、○、○、　、　、　、　、　、　
　、　、　、○、○、○、　、　、　、　、　、　、○、○、○、　、　、　
　、　、　、　、　、　、○、○、○、　、　、　、　、　、　、○、○、○　
○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　
　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　
　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○

ちょっとずれた。
でも雰囲気はわかるよね。

>>26
それでは、実際にやってみましょう。必ず２３手以内に詰ませてみせます。

一手目
┼┼┼
●○┼
┼┼┼

誰でもいいです。どうぞ

>>24
それ、探索にどのくらい時間かかるんだ？
ネズミの移動方向を入力できるようにして up してくれよ。
面白いゲームになりそうじゃね？ｗ

┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼●┼┼　┼┼●┼┼
┼┼┼○┼　┼┼┼○┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼○┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼

脱出成功

>>31
実はそれでも詰みますが、変化が複雑（時間がかかる）なので
>>29からどうぞ

┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼
●○┼┼┼　●┼○┼┼
┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼

>>30
Javaで書いてしまいましたが、１時間ぐらいで解けました。

３手目
┼┼┼┼┼
┼┼┼●┼
●┼○┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

書き込みを楽にする為、最後の局面のみにしましょう。

┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼┼┼┼
┼┼┼┼┼


でもさ、>>31 のが時間かかるってことは23手で詰まないっていう意味じゃないの？

３手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼●┼┼
┼┼┼┼┼

いえ、探索に時間がかかります。

そういえばアレニウスの円っていう問題もあったね

┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼┼
┼┼┼┼┼

ジダンの華麗なダンス炸裂してほしい

>>34
１時間は長いな。
最初の数手をテーブルにしたらインタラクティブな待ち時間にならんかな。
ネズミ側だけでいいんだけど。

既に２手サバ読まれてるし

７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼●
┼┼┼┼┼

じつは４手目は最善手ではありません。

ほっほー

ネズミは曲がるとかなり手数損しそうですね


┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼┼┼
┼┼●┼●
┼┼┼○┼

ジダン突破

４手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

>>40
ばれましたか。

５手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

４手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

>>44は最善手の一つですがこちらは違います。

６手目
┼┼┼┼┼
┼┼┼●○
●┼┼┼●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼●┼┼┼
┼┼┼┼┼
┼┼┼┼┼

┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼┼┼
┼┼┼┼┼

７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼●┼
┼┼┼┼┼

┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼┼○
┼┼┼●┼
┼┼┼┼┼

┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼┼┼
┼┼┼●┼┼┼　┼┼┼●┼┼┼　┼┼┼●┼┼┼　┼┼┼●┼┼┼
●┼┼┼●┼┼　●┼┼┼●┼┼　●┼┼┼●┼┼　●┼┼┼●┼┼
┼┼┼┼○┼┼　┼┼┼┼○┼┼　┼┼┼┼┼○┼　┼┼┼┼┼○●
┼┼┼●┼┼┼　┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼

┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼●┼
┼┼┼●┼┼┼　┼┼┼●┼┼●　┼┼┼●┼○●　┼┼┼●┼○●
●┼┼┼●○┼　●┼┼┼●○┼　●┼┼┼●┼┼　●┼┼┼●┼┼
┼┼┼┼┼┼●　┼┼┼┼┼┼●　┼┼┼┼┼┼●　┼┼┼┼┼┼●
┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼

┼┼┼┼┼●┼　┼┼┼┼┼●┼　┼┼┼┼┼●┼　┼┼┼┼┼●┼
┼┼┼●┼┼●　┼┼┼●●┼●　┼┼┼●●┼●　┼┼┼●●┼●
●┼┼┼●○┼　●┼┼┼●○┼　●┼┼┼●┼┼　●┼┼┼●┼┼
┼┼┼┼┼┼●　┼┼┼┼┼┼●　┼┼┼┼┼○●　┼┼┼┼●○●
┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼

┼┼┼┼┼●┼　┼┼┼┼┼●┼　┼┼┼┼┼●┼　┼┼┼┼┼●┼
┼┼┼●●┼●　┼┼┼●●┼●　┼┼┼●●○●　┼┼┼●●○●
●┼┼┼●○┼　●┼┼┼●○●　●┼┼┼●┼●　●┼┼┼●●●
┼┼┼┼●┼●　┼┼┼┼●┼●　┼┼┼┼●┼●　┼┼┼┼●┼●
┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼

これで終わりにします。ちょいとでしゃばりすぎた感がありますので

明らかに勝負が見えたあとの収束が遅いように思います

>>27

意味が分からないんですけど
解説してください

うーん俺がアホなせいでなかなかうまく説明できないんだが。
テストというのは入力がいくつかあってその選択肢の組み合わせを考える。
>>27の例は入力が３つあって、一番目は選択肢が２つ、２番目、３番目は選択肢が３つあると思って。
で、１行目、２行目は一番目の入力の選択肢をどちらを選ぶかを表している。
３，４，５行目は２番目の入力の選択肢のうちどれを選ぶかを表している。
６，７，８行目は３番目の入力の選択肢のうちどれを選ぶかを表している。
各列はひとつのテストケースを表している。
たとえば一行目は一番目の入力＝１、２番目の入力＝１、３番目の入力＝１
５行目は一番目の入力＝１、２番目の入力＝２、３番目の入力＝２といった感じ。
で、選択肢の組み合わせを網羅的に生成してほしい。出力は>>27のフォーマットで。

うまく説明できたかわからんがこんな感じです。

>>56
こんなんでいいかな、
http://www.uploda.org/uporg455626.cpp.html

>>27は1列ごとにテストケース1パターンを表してるようだけど、
それもフォーマット？
めんどいから、1行1ケース表示にしたけど。

つか、パズルじゃないだろ

#include <string>忘れてた

修正
http://www.uploda.org/uporg455638.cpp.html

そうそう。そんな感じなんですが、何とか１列１テストケースになりませんかね。
そのほうが何かとありがたいんですが。

>>56

主語や目的語を省略しすぎなんだよ

自分だけが分かってて相手が分かってないときに説明するんだから

>>61
精進します。

ネズミが８方向に動けたら、つかまんなくなりそう。
どうなんだろ。

>>63
それじゃパズルとして綺麗じゃないような気がする（移動距離が長いものと短いものがあってイヤ）
どうせならヘックスでやってみるとおもしろいかもしれない。

>>60
１列１テストケースにしたよ。
http://www.uploda.org/uporg455761.cpp.html

ところで、どうしてここで質問？質問スレ行くといいよ。

>>65
いや、考えようによってはパズルといえなくもないかなーと。
これからは注意します。
ありがとうございました。

あのな、パズルってのは（ｒｙ

HEXのねずみ捕り面白そうだけど

ここで表現するの自体が難しそう

3x3のマス目で行なうマスターマインド（値は重複しない1〜9）の解答を得る
アルゴリズムってできないでしょうか？
3手で正解を得られるようなんですが。

難しくてｻﾊﾟｰﾘわからん。

最低限ルールぐらい書いてもらおうか

どんなルールか知らんが３ｘ３ならしらみつぶしで終わりそうな予感。

○○○
○○○
○○○

１２３
４５６
７８９

場所 1
数字 9

７８９
４５６
１２３


場所 1
数字 9

９８７
６５４
３２１

場所 4
数字 9

９７８
６４５
３１２

場所 8
数字 9

糞スレ化している・・・

　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋
　○＋＋○＋＋○＋＋○＋＋○＋＋
＋＋○＋＋○＋＋○＋＋○＋＋

HEXなってないかな・・・

盤だけ表示できても駒が

　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋

どぞ

六角形の碁盤
http://game9.2ch.net/test/read.cgi/gamestones/1071768398/l50
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘

＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘

＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘

これ対称性を考えると意外とパターン少ないな

ＨＥＸだとつかまんない予感。

オセロのパーフェクト決着の最短推移と最長推移をそれぞれ一種類ずつ求めよ。
盤面の左下のマスを [0,0] とし、はじめ [3,3] に置いてある色のプレイヤーが先攻とする。
ゲームの推移の記法は [3,5] [4,6] ... とする。

・・・こういうのはパズルとは言わないかも

>>5
こんなかんじか。
http://www.uploda.org/uporg457304.cpp.html

この問題って、始めの文字列と終わりの文字列も「ちょうど2文字だけ異なる」っていう条件を満たさなければならない？

多分可能だが、まだやっていない。

満たすべきだろうね

グレイコードから作る方法なら満たせるでしょう

>>85
NP問題の予感

ところでＨＥＸの座標ってどう表すの？

>>88
むしろＰＳＰＡＣＥ問題の予感。

>>89
普通の表の片方の斜めだけに進めるようにする。
■■□
■☆■
□■■
■：進めるマス
□：進めないマス

--■■□
-■☆■
□■■

表示はこう

いや、俺の勘違い。やっぱＰＳＰＡＣＥじゃなくてＮＰかも。

>>5の問題にグレイコードを応用するのは言うほど簡単じゃないとおも。
なかなか手ごわい。

>>92
感動した

>>5
最初と最後を合わせなくていいのなら

#!perl
$max=shift||die"pls spec len\n";$max<1&&die"too small len\n";
($len,@list,@old,$newchar)=(1,'a');
while($len++<$max){($n,@old,@list)=(chr(0x60+$len),@list);
for($i=length($old[0]);$i>=0;--$i){
for(@old){$v=$_;substr($v,$i,0,$n);push@list,$v;}
@old=reverse@old;}}print"$_\n"for@list;

新しい問題キボン。

>>5
一応、始めと終わりもつなぐようにはできたが。。。
http://www.uploda.org/uporg458911.cpp.html

まず単純な並びをつくって、規則性のある並びに並び替える。
文字数n=4なら
00:abcd　06:bacd　12:cabd　18:dabc
01:abdc　07:badc　13:cadb　19:dacb
02:acbd　08:bcad　14:cbad　20:dbac
03:acdb　09:bcda　15:cbda　21:dbca
04:adbc　10:bdac　16:cdab　22:dcab
05:adcb　11:bdca　17:cdba　23:dcba
という並びから、
00:abcd　01:bacd　02:cabd　03:dabc
04:abdc　05:badc　06:cadb　07:dacb
08:acbd　09:bcad　10:cbad　11:dbac
12:acdb　13:bcda　14:cbda　15:dbca
16:adbc　17:bdac　18:cdab　19:dcab
20:adcb　21:bdca　22:cdba　23:dcba
という並びにする。このとき横の並びは互いに２文字異なっている。
次に00の行、04の行・・・20の行を互いに２文字異なるように並び替えるために、
先頭の'a'を除いて、n=3の時を応用する。
あと適当にreverseする。
グレイ符号のやり方は知らん

01:bacd　02:cabd

なってないですよ？

>>99
「互いに２文字異なっている」に「なってないですよ？」と言いたいのかな？

01:bacd　
02:cabd

b,cを入れ替えた2文字違いだね。
ソースみると検算までしてるみたいだし、いいんでは。

5文字の時になんで始めと終わりが揃うのかフシギ

ああ、なってますね。すみません。

A) 00:abcd　06:bacd　12:cabd　18:dabc
B) 01:abdc　07:badc　13:cadb　19:dacb
C) 02:acbd　08:bcad　14:cbad　20:dbac
D) 03:acdb　09:bcda　15:cbda　21:dbca
E) 04:adbc　10:bdac　16:cdab　22:dcab
F) 05:adcb　11:bdca　17:cdba　23:dcba

番号を付け替える必要性は良く分からないのですが、
縦方向から横方向にスキャンを変える発想はよさそうですね。

さらに、

A) を左から右
C) を右から左
E) を左から右

B) を右から左
D) を左から右
F) を右から左

で A) に戻ればうまく循環できますね。

横方向に左右逆転しながら１行とびにスキャンすると循環という
規則性ありそうです。

0)0000 8)1000
1)0001 9)1001
2)0010 A)1010
3)0011 B)1011

4)0100 C)1100
5)0101 D)1101
6)0110 E)1110
7)0111 F)1111

0) -> 8) -> C) -> 4) -> 6) -> E) -> A) -> 2) -> 3) -> B) -> F) -> 7) -> 5) -> D) -> 9) -> 1) ->

とかで戻ってこれるのですが
これでグレイコードになってるのかどうか不明

0 - 8 - A - 2 - 6 - E - C - 4 - 5 - D - F - 7 - 3 - B - 9 - 1
の方が規則性あるかな

Ｎ*Nの格子状のグラフの部分グラフのうち連結なものの個数を数えよ。
エレガントな解法があるのかどうかは知りません。

さめがめとかマインスイーパーみたいなアルゴリズムかな

数学者のオナニーみたいな問題だな

塗りつぶしのアルゴリズム使えば超簡単だな

>>107
詳しく。

ノードと方眼紙の各マスが対応するから
ノードの連結＝マスの隣接 → 塗りつぶしで区分け可能

おもしろい問題くれよ！

D言語用のFrameWorkを作れ

>>111
乞食は死ね

>>111
それ何てパズル？

数独ってＮＰ完全なんだってね。
数学板でやってた。

他のどんなＮＰ問題を数独に帰着させられるんだろうな

　　 SEND
+)　MORE
----------
　 MONEY

なるほど、確かに数独と似ている・・・。

FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY = SEVENTY

SEND+MORE=MONEYは一意に解けてしまうからプログラムのネタにならなくて詰まらん。
語呂合わせにはなってないけど、A*BCDE=FGHIJを解く方が(個人的には)余程面白い。

答えあるのか？

>>119
数学的には(漏れには)解けなかったけど、単一解があるよ。
#記憶に間違いがなければw

一意に解けてしまうのはつまんないのではなかったのか

禿和露酢

んにゃ、数学的に解けなかったところに意味を見出しているだけだから。
例えば、SEND+MORE=MONEYだとS=9, M=1から始まって式を展開していけばすぐに求まってしまうから。
#まぁ、笑う前にやって味噌。

>>117 のはなしは？

覆面算と数独が本質的に同じって話だが、何か？

>>118 がNP完全で >>116 はNP完全ではないという意味でよろしかったでしょうか？

そんな話はしていないのでは・・・

>>12
空いてる枡を─│└┘┌┐のいずれかで埋めて
全パターンやれば解けそう。
バックトラックでどこまで計算量削れるか？

>>12はナンリン（ナンバーリンク）という同じルールのパズルがあって
下のスレでそれを解くプログラムが既に作られている。

【解答】パズルのプログラミング【作成】
http://hobby8.2ch.net/test/read.cgi/puzzle/1092459010/

だれか次の言語をBrainFuckにコンパイルするコンパイラ作って。
　　> ポインタをインクリメント
　　< ポインタをデクリメント
　　+ ポインタが示すメモリ位置のデータをインクリメント
　　- ポインタが示すメモリ位置のデータをデクリメント
　　. ポインタが示すメモリ位置のデータを出力
　　, ポインタが示すメモリ位置のデータに入力
　　[ ポインタが示すメモリ位置のデータがヌルなら対応する]までジャンプ
　　] ポインタが示すメモリ位置のデータがヌルじゃないなら対応する[までジャンプ
　　@n (nは整数)ポインタをn番地に設定

BrainFuckのスレ
http://pc8.2ch.net/test/read.cgi/tech/1036013915/l50

単位円周上にＮ個の点が与えられたときに、
そのうちのＭ個の点を頂点とする多角形の取りうる最大面積の値を求めよ。

仕様：
入力データは、最初の行はＮとＭの値が半角空白で区切られており、
直後に単位円周上の点のＸ座標とＹ座標の値が半角空白で区切られた行がＮ行続く。
解は小数点以下３桁以上の精度で１行に出力。

入力例：
4 3
1.0 0.0
0.7071 0.7071
0.0 1.0
-1.0 0.0

解答例：
1.000

漏れは４時間考えたが結局ヒントもらうまで解けなかったorz

>>131
超典型 DP

どうやって小問題に分割するか

素数が無限個存在することを1行で証明せよ

(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数

>>136
3*5+1=16

(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数の倍数

何の証明にもなってないという事実は伏せておこう

望むだけ長く区間素数が現れないような条件を求めよ。

ここは数学のスレではありません＞＜

>>136
(ある素数Ｎ以下の全素数の積)+1 = 左辺の素数の集合に含まれない素数

それが何故なのかを説明しないと証明にならんっつーの

素数の定義より明らか