トップページ⇒tech
144コメント50KB

パズルを出題しあうスレ

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2006/07/21(金) 19:10:18
パズルを出題してそれを解くプログラムを作るスレです。
みんなで楽しくアルゴリズムを考えましょう。
0002デフォルトの名無しさん2006/07/21(金) 19:13:50
ずるしてらくしてかれいに２げっと
000312006/07/21(金) 19:24:30
では数学板で見かけた問題。

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

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

このゲームはプレイヤーが勝つことが数学板で証明されていたので
最短手数を求めてください。
000412006/07/21(金) 19:27:35
数学板の面白い問題おしえて〜な 11問目の381に載ってました。
000512006/07/21(金) 21:40:58
もう一問だしときますね。

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

たとえば3文字なら
abc
acb
bca
bac
cab
cba
と並べれば隣り合う文字列がちょうど2文字違うようになります。
0006デフォルトの名無しさん2006/07/22(土) 00:05:28
>>5
それって任意のnに対して可能なの？
0007デフォルトの名無しさん2006/07/22(土) 02:33:58
グレイ符号が応用できそうな予感
0008デフォルトの名無しさん2006/07/22(土) 04:39:25
スマソ
意味が分からん
0009デフォルトの名無しさん2006/07/22(土) 04:46:26
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

こういう意味か

確かにグレイコードで置き換えたらうまくいくと思う
0010デフォルトの名無しさん2006/07/22(土) 14:57:08
普通に全通りの並べ方をしらみつぶしにやればいいんじゃね？
計算時間？しらね。
0011デフォルトの名無しさん2006/07/22(土) 15:54:30
単純に、隣り合う二文字を入れ替えた。

#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;
　}
}
0012デフォルトの名無しさん2006/07/22(土) 16:13:31
誰かこれ解くプログラム書いて。
http://yoshimaruxxx.web.fc2.com/sentunagi.html
0013デフォルトの名無しさん2006/07/22(土) 16:28:00
>>11
実行してみたけど重複する文字列があるみたい。

0014デフォルトの名無しさん2006/07/22(土) 16:34:32
これって結局階乗を出す問題だよね。
交換だけで階乗が出せればかなり有名になっているはずだから、スマートな解法はないと思う。
0015デフォルトの名無しさん2006/07/22(土) 16:41:16
>>14
階乗を出すってどういうこと？
0016デフォルトの名無しさん2006/07/22(土) 17:06:32
順列ですた。
という事で、順列を交換だけで出せるのって話です。
0017デフォルトの名無しさん2006/07/22(土) 17:12:59
文字列を頂点として２文字違う文字列に辺があるグラフを考えれば
ハミルトン閉路問題に帰着される。
辺の数は結構多いし、ハミルトン閉路はありそうにも思えるがさて。
0018デフォルトの名無しさん2006/07/22(土) 17:29:42
グラフの作成に O(n!) かかるのでは。
結局しらみつぶしと同じ予感。
0019デフォルトの名無しさん2006/07/22(土) 17:45:15
もともと出力のサイズがn!なんだからそれは気にすること無い。
しらみつぶしの計算量は(n!)!なんだから全然違う。
0020デフォルトの名無しさん2006/07/22(土) 18:10:52
普通出力ってひとまとめで一処理とみなす気が
0021デフォルトの名無しさん2006/07/22(土) 20:13:02
出力の大きさがO(n!)なんだからどんなにがんばったって計算量がO(n!)を下回ることはない。
出力をひとまとめで一処理なんておかしいよ。
0022デフォルトの名無しさん2006/07/22(土) 21:07:22
n文字の場合の結果をつかってn+1文字の場合を解けないものか。
0023デフォルトの名無しさん2006/07/22(土) 23:37:12
　　　　　　　, -: ':　:　:　:　:　:　:"⌒:￣:` : ､
　　　　　 ／:　:　:　: へ._　:　:　:　:へ、:　:　: ＼
　　　 __,く;へ＿:　: :|　:　:　:　:　:　:　: ＼￣:ヽ、＼
.　　 /:__/:　:　:/:　: |: :ｌ:　:　:　:　:　:　:　: ＼.:　:ヽ: ヽ
　　/_//:　:　:/:　/ :|:　ｌ:　:　:ヽ:　ヽ:　:　:　: ヽ:　: ヽﾊ
／/: /: : : : : |: : ｌ: : |: : |: : ヽ: :ヽ: : ヽ: : : : : : :ヽ: : ヽﾊ
. /:/: /: /: ｌ: |: :,|: : ﾊ: : |: : : ヽ: :ヽ: : ヽ: : : : : : :ヽ : ヽ|
//: : ｌ: :ｌ: ::|: :|: :|: : :| ヽ ｌヽ : : :＼: ヽ.: :＼: : : ヽ:ﾊ: : : |
| ｌ: : |: :|: : |: :|: ハ__,L. ヽ　＼"￣｢ T ト- ､;_: : : : :|: : :.|
| |: : |: :|: : |: ;|イ｢ ヽ|　　 ＼´＼ヽ __｣__ｉ.＼ ＼ : : |: : :|　　もう・・・仕方の無いことばかり言って・・・
| |: : |: :|: : くｖ'　_｣＝ｉ　　　　ヽ ／｢ ｉ::::::o｢＼|ヽﾄ: |: :/|
ｉ ｌ: : ﾊ: ｌ: : :.ト / {:::::::〉　　　　　　 ﾚﾍ:.::::}ﾟｉ|/|: ::| .}ﾚ': :|
　∨:| Ｖﾍ: ::ﾍヽ　ｖﾍ:ﾊ　　　　　　 ..く_二ｉつ|: :.:ﾚ: :| : :|
　　ヽヽ∨へ:ﾊ　　ヾツ　　　 　　　　/／//ﾊ:/::|: :|: : :|
　　　　　 ∧: :ｉ:ﾍ.ｌ // 　　`　　　　　　　　/: {:::::|: :ｌ: : ﾊ
　　　　　/:/: ∧: ＼　　　　　｡　　　　　,.ｲ:|: :|::ｉ:::|: :ｌ: ::∧
　　　　 //:　:　:}:　ヽ`ｉ:: ､. 　　　　　／　.|::| :|:::ｉ::::|: ｉ:: : ∧
　　 　://:　:　: ハ:　ヽ::::::ノＴ ' ‐ '　　　　|::|: :Ｖ::::ｉ∧: : : : ﾍ
　　 /／:　:　ノ二 ヽ:　:＼ 〈ｰ ､ ＿＿___,ﾄﾍ: :∨::ｉ::∧: : : :.∧
　／/:/　/⌒ ＼　 ヽト､: :ヽ＼__＿＿___ハ ＼:∨ﾊ:::∧: : : :} ＼
0024デフォルトの名無しさん2006/07/23(日) 00:17:11
>>3
ネズミの問題は２３手詰めと出た。この手順はピンとこないけど、うまく収束している。

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

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

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

┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼　┼┼┼●┼
┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼　┼┼●●┼
┼●●┼┼　┼●●┼┼　┼●●┼┼　┼●●●┼　┼●●●┼　┼●●●┼
┼○┼┼●　●○┼┼●　●┼○┼●　●┼○┼●　●┼┼┼●　●┼●┼●
┼●┼●┼　┼●┼●┼　┼●┼●┼　┼●┼●┼　┼●○●┼　┼●○●┼
┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼　┼┼●┼┼
0025デフォルトの名無しさん2006/07/23(日) 00:22:09
自己レス>>24
ただし、ブロックの置き方はネズミの八方のみしか探索していないので。
0026デフォルトの名無しさん2006/07/23(日) 02:40:48
正解なのかどうかすらわからん
0027デフォルトの名無しさん2006/07/23(日) 09:05:40
テストケースの組み合わせを自動生成してくれるプログラム作ってくれんか？
たとえば入力を2,3,3としたら以下のような文字を出力してくれるような。
言葉ではうまく言えないが全ての組み合わせを生成してくれるやつ。

○、○、○、○、○、○、○、○、○、　、　、　、　、　、　、　、　、　
　、　、　、　、　、　、　、　、　、○、○、○、○、○、○、○、○、○
○、○、○、　、　、　、　、　、　、○、○、○、　、　、　、　、　、　
　、　、　、○、○、○、　、　、　、　、　、　、○、○、○、　、　、　
　、　、　、　、　、　、○、○、○、　、　、　、　、　、　、○、○、○　
○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　
　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　
　、　、○、　、　、○、　、　、○、　、　、○、　、　、○、　、　、○
0028272006/07/23(日) 09:07:13
ちょっとずれた。
でも雰囲気はわかるよね。
0029242006/07/23(日) 09:24:01
>>26
それでは、実際にやってみましょう。必ず２３手以内に詰ませてみせます。

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

誰でもいいです。どうぞ
0030デフォルトの名無しさん2006/07/23(日) 09:25:34
>>24
それ、探索にどのくらい時間かかるんだ？
ネズミの移動方向を入力できるようにして up してくれよ。
面白いゲームになりそうじゃね？ｗ
0031デフォルトの名無しさん2006/07/23(日) 09:26:21
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼●┼┼　┼┼●┼┼
┼┼┼○┼　┼┼┼○┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼○┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼　┼┼┼┼┼

脱出成功
0032242006/07/23(日) 09:28:47
>>31
実はそれでも詰みますが、変化が複雑（時間がかかる）なので
>>29からどうぞ
0033デフォルトの名無しさん2006/07/23(日) 09:38:49
┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼
●○┼┼┼　●┼○┼┼
┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼
┼┼┼┼┼　┼┼┼┼┼
0034242006/07/23(日) 09:40:46
>>30
Javaで書いてしまいましたが、１時間ぐらいで解けました。

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

書き込みを楽にする為、最後の局面のみにしましょう。
0035デフォルトの名無しさん2006/07/23(日) 09:43:10
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼┼┼┼
┼┼┼┼┼


でもさ、>>31 のが時間かかるってことは23手で詰まないっていう意味じゃないの？
0036242006/07/23(日) 09:44:12
３手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼○┼┼
┼┼●┼┼
┼┼┼┼┼

いえ、探索に時間がかかります。
0037デフォルトの名無しさん2006/07/23(日) 09:44:34
そういえばアレニウスの円っていう問題もあったね
0038デフォルトの名無しさん2006/07/23(日) 09:45:22
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼┼
┼┼┼┼┼

ジダンの華麗なダンス炸裂してほしい
0039デフォルトの名無しさん2006/07/23(日) 09:46:22
>>34
１時間は長いな。
最初の数手をテーブルにしたらインタラクティブな待ち時間にならんかな。
ネズミ側だけでいいんだけど。
0040デフォルトの名無しさん2006/07/23(日) 09:46:54
既に２手サバ読まれてるし
0041242006/07/23(日) 09:47:04
７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼┼
┼┼┼○┼
┼┼●┼●
┼┼┼┼┼

じつは４手目は最善手ではありません。
0042デフォルトの名無しさん2006/07/23(日) 09:48:23
ほっほー
0043デフォルトの名無しさん2006/07/23(日) 09:51:10

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


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

ジダン突破
0044デフォルトの名無しさん2006/07/23(日) 10:00:19
４手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
0045242006/07/23(日) 10:05:00
>>40
ばれましたか。

５手目
┼┼┼┼┼
┼┼┼●┼
●┼┼○●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
0046デフォルトの名無しさん2006/07/23(日) 10:06:14
４手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
0047242006/07/23(日) 10:08:02
５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼

>>44は最善手の一つですがこちらは違います。
0048デフォルトの名無しさん2006/07/23(日) 10:08:11
６手目
┼┼┼┼┼
┼┼┼●○
●┼┼┼●
┼┼┼┼┼
┼┼┼┼┼
┼┼┼┼┼
0049242006/07/23(日) 10:08:53
５手目
┼┼┼┼┼
┼┼┼●┼
●○┼┼┼
┼●┼┼┼
┼┼┼┼┼
┼┼┼┼┼
0050デフォルトの名無しさん2006/07/23(日) 10:11:27
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼┼┼
┼┼┼┼┼
0051242006/07/23(日) 10:12:54
７手目
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼○┼
┼┼┼●┼
┼┼┼┼┼
0052デフォルトの名無しさん2006/07/23(日) 10:28:22
┼┼┼┼┼
┼┼┼●┼
●┼┼┼●
┼┼┼┼○
┼┼┼●┼
┼┼┼┼┼
0053242006/07/23(日) 10:38:19
┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼┼┼　┼┼┼┼┼┼┼
┼┼┼●┼┼┼　┼┼┼●┼┼┼　┼┼┼●┼┼┼　┼┼┼●┼┼┼
●┼┼┼●┼┼　●┼┼┼●┼┼　●┼┼┼●┼┼　●┼┼┼●┼┼
┼┼┼┼○┼┼　┼┼┼┼○┼┼　┼┼┼┼┼○┼　┼┼┼┼┼○●
┼┼┼●┼┼┼　┼┼┼●┼●┼　┼┼┼●┼●┼　┼┼┼●┼●┼

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

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

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

これで終わりにします。ちょいとでしゃばりすぎた感がありますので
0054デフォルトの名無しさん2006/07/23(日) 11:03:33
明らかに勝負が見えたあとの収束が遅いように思います
0055デフォルトの名無しさん2006/07/23(日) 11:05:27
>>27

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

うまく説明できたかわからんがこんな感じです。
0057デフォルトの名無しさん2006/07/23(日) 16:32:42
>>56
こんなんでいいかな、
http://www.uploda.org/uporg455626.cpp.html

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

つか、パズルじゃないだろ
0058デフォルトの名無しさん2006/07/23(日) 16:35:53
#include <string>忘れてた
0059デフォルトの名無しさん2006/07/23(日) 16:37:40
修正
http://www.uploda.org/uporg455638.cpp.html
0060272006/07/23(日) 16:47:41
そうそう。そんな感じなんですが、何とか１列１テストケースになりませんかね。
そのほうが何かとありがたいんですが。
0061デフォルトの名無しさん2006/07/23(日) 16:49:19
>>56

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

自分だけが分かってて相手が分かってないときに説明するんだから
0062272006/07/23(日) 16:55:52
>>61
精進します。
0063デフォルトの名無しさん2006/07/23(日) 17:03:17
ネズミが８方向に動けたら、つかまんなくなりそう。
どうなんだろ。
0064デフォルトの名無しさん2006/07/23(日) 18:05:30
>>63
それじゃパズルとして綺麗じゃないような気がする（移動距離が長いものと短いものがあってイヤ）
どうせならヘックスでやってみるとおもしろいかもしれない。
0065デフォルトの名無しさん2006/07/23(日) 18:24:24
>>60
１列１テストケースにしたよ。
http://www.uploda.org/uporg455761.cpp.html

ところで、どうしてここで質問？質問スレ行くといいよ。
0066272006/07/23(日) 18:29:29
>>65
いや、考えようによってはパズルといえなくもないかなーと。
これからは注意します。
ありがとうございました。
0067デフォルトの名無しさん2006/07/23(日) 18:31:13
あのな、パズルってのは（ｒｙ
0068デフォルトの名無しさん2006/07/23(日) 18:34:46

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

ここで表現するの自体が難しそう
0069デフォルトの名無しさん2006/07/23(日) 19:22:03
3x3のマス目で行なうマスターマインド（値は重複しない1〜9）の解答を得る
アルゴリズムってできないでしょうか？
3手で正解を得られるようなんですが。

難しくてｻﾊﾟｰﾘわからん。
0070デフォルトの名無しさん2006/07/23(日) 19:29:06
最低限ルールぐらい書いてもらおうか
0071デフォルトの名無しさん2006/07/23(日) 19:53:08
どんなルールか知らんが３ｘ３ならしらみつぶしで終わりそうな予感。
0072デフォルトの名無しさん2006/07/23(日) 22:11:20
○○○
○○○
○○○

１２３
４５６
７８９

場所 1
数字 9

0073デフォルトの名無しさん2006/07/23(日) 22:14:37
７８９
４５６
１２３


場所 1
数字 9
0074デフォルトの名無しさん2006/07/23(日) 22:15:38
９８７
６５４
３２１

場所 4
数字 9
0075デフォルトの名無しさん2006/07/23(日) 22:17:46
９７８
６４５
３１２

場所 8
数字 9
0076デフォルトの名無しさん2006/07/23(日) 22:18:44
糞スレ化している・・・
0077デフォルトの名無しさん2006/07/23(日) 22:25:33

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

HEXなってないかな・・・
0078デフォルトの名無しさん2006/07/23(日) 23:38:46
盤だけ表示できても駒が
0079デフォルトの名無しさん2006/07/23(日) 23:53:55
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋
　　＋＋　＋＋　＋＋　＋＋　＋＋
＋＋　＋＋　＋＋　＋＋　＋＋　＋＋

どぞ
0080デフォルトの名無しさん2006/07/24(月) 07:13:27
六角形の碁盤
http://game9.2ch.net/test/read.cgi/gamestones/1071768398/l50
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘

0081デフォルトの名無しさん2006/07/24(月) 07:34:18
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
0082デフォルトの名無しさん2006/07/24(月) 13:34:38
＿＿＿＿＿┌─┬─┬─┬─┬─┬─┐
＿＿＿＿＿｜ 　｜　 ｜ 　｜ 　｜　 ｜　 ｜
＿＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿＿｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
＿｜　 ｜　 ｜　 ｜　 ｜○｜　 ｜　 ｜　 ｜　 ｜　 ｜
┌┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┐
｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿｜　 ｜　 ｜　 ｜　 ｜　 ｜●｜　 ｜　 ｜　 ｜　 ｜
＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿└┬┴┬┴┬┴┬┴┬┴┬┴┬┘
＿＿＿＿＿｜　 ｜　 ｜　 ｜　 ｜　 ｜　 ｜
＿＿＿＿＿└─┴─┴─┴─┴─┴─┘
0083デフォルトの名無しさん2006/07/24(月) 13:36:11
これ対称性を考えると意外とパターン少ないな
0084デフォルトの名無しさん2006/07/24(月) 17:49:24
ＨＥＸだとつかまんない予感。
0085デフォルトの名無しさん2006/07/25(火) 02:00:43
オセロのパーフェクト決着の最短推移と最長推移をそれぞれ一種類ずつ求めよ。
盤面の左下のマスを [0,0] とし、はじめ [3,3] に置いてある色のプレイヤーが先攻とする。
ゲームの推移の記法は [3,5] [4,6] ... とする。

・・・こういうのはパズルとは言わないかも
0086デフォルトの名無しさん2006/07/25(火) 02:08:54
>>5
こんなかんじか。
http://www.uploda.org/uporg457304.cpp.html

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

多分可能だが、まだやっていない。
0087デフォルトの名無しさん2006/07/25(火) 03:06:56
満たすべきだろうね

グレイコードから作る方法なら満たせるでしょう
0088デフォルトの名無しさん2006/07/25(火) 16:28:49
>>85
NP問題の予感
0089デフォルトの名無しさん2006/07/25(火) 18:05:54
ところでＨＥＸの座標ってどう表すの？
0090デフォルトの名無しさん2006/07/25(火) 18:08:35
>>88
むしろＰＳＰＡＣＥ問題の予感。
0091デフォルトの名無しさん2006/07/25(火) 18:17:48
>>89
普通の表の片方の斜めだけに進めるようにする。
■■□
■☆■
□■■
■：進めるマス
□：進めないマス
0092デフォルトの名無しさん2006/07/25(火) 18:19:40
--■■□
-■☆■
□■■

表示はこう
0093902006/07/25(火) 20:35:07
いや、俺の勘違い。やっぱＰＳＰＡＣＥじゃなくてＮＰかも。
0094デフォルトの名無しさん2006/07/25(火) 21:36:03
>>5の問題にグレイコードを応用するのは言うほど簡単じゃないとおも。
なかなか手ごわい。
0095デフォルトの名無しさん2006/07/26(水) 02:21:43
>>92
感動した
0096デフォルトの名無しさん2006/07/26(水) 09:07:41
>>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;
0097デフォルトの名無しさん2006/07/26(水) 17:19:44
新しい問題キボン。
0098デフォルトの名無しさん2006/07/26(水) 17:29:01
>>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する。
グレイ符号のやり方は知らん
0099デフォルトの名無しさん2006/07/26(水) 23:08:13
01:bacd　02:cabd

なってないですよ？
0100デフォルトの名無しさん2006/07/27(木) 02:48:41
>>99
「互いに２文字異なっている」に「なってないですよ？」と言いたいのかな？

01:bacd　
02:cabd

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

5文字の時になんで始めと終わりが揃うのかフシギ
0101デフォルトの名無しさん2006/07/27(木) 05:09:13
ああ、なってますね。すみません。

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) に戻ればうまく循環できますね。

横方向に左右逆転しながら１行とびにスキャンすると循環という
規則性ありそうです。
0102デフォルトの名無しさん2006/07/27(木) 05:18:02
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) ->

とかで戻ってこれるのですが
これでグレイコードになってるのかどうか不明
0103デフォルトの名無しさん2006/07/27(木) 05:35:00
0 - 8 - A - 2 - 6 - E - C - 4 - 5 - D - F - 7 - 3 - B - 9 - 1
の方が規則性あるかな
0104デフォルトの名無しさん2006/07/28(金) 18:32:45
Ｎ*Nの格子状のグラフの部分グラフのうち連結なものの個数を数えよ。
エレガントな解法があるのかどうかは知りません。
0105デフォルトの名無しさん2006/07/28(金) 18:39:42
さめがめとかマインスイーパーみたいなアルゴリズムかな
0106デフォルトの名無しさん2006/07/28(金) 19:11:13
数学者のオナニーみたいな問題だな
0107デフォルトの名無しさん2006/07/28(金) 23:07:03
塗りつぶしのアルゴリズム使えば超簡単だな
0108デフォルトの名無しさん2006/07/29(土) 00:17:47
>>107
詳しく。
0109デフォルトの名無しさん2006/07/29(土) 01:07:55
ノードと方眼紙の各マスが対応するから
ノードの連結＝マスの隣接 → 塗りつぶしで区分け可能
0110デフォルトの名無しさん2006/07/29(土) 06:36:22
おもしろい問題くれよ！
0111デフォルトの名無しさん2006/07/29(土) 06:44:41
D言語用のFrameWorkを作れ
0112デフォルトの名無しさん2006/07/29(土) 11:35:21
>>111
乞食は死ね
0113デフォルトの名無しさん2006/07/29(土) 14:28:25
>>111
それ何てパズル？
0114デフォルトの名無しさん2006/07/29(土) 21:35:32
数独ってＮＰ完全なんだってね。
数学板でやってた。
0115デフォルトの名無しさん2006/07/29(土) 22:42:07
他のどんなＮＰ問題を数独に帰着させられるんだろうな
0116デフォルトの名無しさん2006/07/29(土) 23:10:13
　　 SEND
+)　MORE
----------
　 MONEY
0117デフォルトの名無しさん2006/07/29(土) 23:24:22
なるほど、確かに数独と似ている・・・。

FIVE + SEVEN + ELEVEN + TWELVE + FIFTEEN + TWENTY = SEVENTY
0118デフォルトの名無しさん2006/07/29(土) 23:40:49
SEND+MORE=MONEYは一意に解けてしまうからプログラムのネタにならなくて詰まらん。
語呂合わせにはなってないけど、A*BCDE=FGHIJを解く方が(個人的には)余程面白い。
0119デフォルトの名無しさん2006/07/29(土) 23:41:12
答えあるのか？
01201182006/07/29(土) 23:45:22
>>119
数学的には(漏れには)解けなかったけど、単一解があるよ。
#記憶に間違いがなければw
0121デフォルトの名無しさん2006/07/29(土) 23:55:33
一意に解けてしまうのはつまんないのではなかったのか
0122デフォルトの名無しさん2006/07/29(土) 23:57:09
禿和露酢
01231182006/07/30(日) 01:28:13
んにゃ、数学的に解けなかったところに意味を見出しているだけだから。
例えば、SEND+MORE=MONEYだとS=9, M=1から始まって式を展開していけばすぐに求まってしまうから。
#まぁ、笑う前にやって味噌。
0124デフォルトの名無しさん2006/07/30(日) 03:40:29
>>117 のはなしは？
0125デフォルトの名無しさん2006/07/30(日) 05:12:59
覆面算と数独が本質的に同じって話だが、何か？
0126デフォルトの名無しさん2006/07/30(日) 11:39:00
>>118 がNP完全で >>116 はNP完全ではないという意味でよろしかったでしょうか？
0127デフォルトの名無しさん2006/07/30(日) 18:12:30
そんな話はしていないのでは・・・
0128デフォルトの名無しさん2006/08/10(木) 21:49:28
>>12
空いてる枡を─│└┘┌┐のいずれかで埋めて
全パターンやれば解けそう。
バックトラックでどこまで計算量削れるか？
0129デフォルトの名無しさん2006/08/11(金) 09:21:09
>>12はナンリン（ナンバーリンク）という同じルールのパズルがあって
下のスレでそれを解くプログラムが既に作られている。

【解答】パズルのプログラミング【作成】
http://hobby8.2ch.net/test/read.cgi/puzzle/1092459010/
0130デフォルトの名無しさん2006/10/25(水) 21:04:39
だれか次の言語をBrainFuckにコンパイルするコンパイラ作って。
　　> ポインタをインクリメント
　　< ポインタをデクリメント
　　+ ポインタが示すメモリ位置のデータをインクリメント
　　- ポインタが示すメモリ位置のデータをデクリメント
　　. ポインタが示すメモリ位置のデータを出力
　　, ポインタが示すメモリ位置のデータに入力
　　[ ポインタが示すメモリ位置のデータがヌルなら対応する]までジャンプ
　　] ポインタが示すメモリ位置のデータがヌルじゃないなら対応する[までジャンプ
　　@n (nは整数)ポインタをn番地に設定

BrainFuckのスレ
http://pc8.2ch.net/test/read.cgi/tech/1036013915/l50
0131デフォルトの名無しさん2006/10/31(火) 20:58:56
単位円周上にＮ個の点が与えられたときに、
そのうちのＭ個の点を頂点とする多角形の取りうる最大面積の値を求めよ。

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

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

解答例：
1.000
0132デフォルトの名無しさん2006/10/31(火) 20:59:45
漏れは４時間考えたが結局ヒントもらうまで解けなかったorz
0133デフォルトの名無しさん2006/11/01(水) 02:43:26
>>131
超典型 DP
0134デフォルトの名無しさん2006/11/02(木) 01:15:21
どうやって小問題に分割するか
0135デフォルトの名無しさん2006/11/02(木) 02:00:39
素数が無限個存在することを1行で証明せよ
0136デフォルトの名無しさん2006/11/02(木) 11:15:53
(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数
0137デフォルトの名無しさん2006/11/03(金) 00:04:17
>>136
3*5+1=16
0138デフォルトの名無しさん2006/11/03(金) 01:34:36
(有限個の互いに異なる素数の積)+1 = 左辺の素数の集合に含まれない素数の倍数
0139デフォルトの名無しさん2006/11/03(金) 01:41:24
何の証明にもなってないという事実は伏せておこう
0140デフォルトの名無しさん2006/11/03(金) 02:06:37
望むだけ長く区間素数が現れないような条件を求めよ。
0141デフォルトの名無しさん2006/11/03(金) 02:34:35
ここは数学のスレではありません＞＜
0142デフォルトの名無しさん2006/11/05(日) 04:03:11
>>136
(ある素数Ｎ以下の全素数の積)+1 = 左辺の素数の集合に含まれない素数
0143デフォルトの名無しさん2006/11/08(水) 21:13:38
それが何故なのかを説明しないと証明にならんっつーの
0144デフォルトの名無しさん2006/11/09(木) 09:45:36
素数の定義より明らか
■ このスレッドは過去ログ倉庫に格納されています