ホームページへ戻る  書き込みリストへ戻る
プログラミングパズル雑談コーナー

プログラミングパズルに関心のある人は雑談しましょう!


Re:N Queens Problem 投稿者:高橋謙一郎  投稿日:04月23日(水)22時33分48秒

人の書いたプログラムを解析するだけに留まっていますが面白いです。

Jeff Somers さんのプログラムは結局、ビット処理で高速化している
だけでした。ただ、効き筋の扱い方とビット演算方法はみごとです。

彼は再帰関数を書けないのでしょうか。再帰で書けば簡単なプログラム
をスタックを自己管理して非再帰で書いているので彼のプログラムは
解読しにくかったようです。そこで一般的というか自分流に再帰で書き
直したプログラムを下に置きます。
注意:このプログラムは対称性を考慮しない解を求めます。

N=15 -> 2279184 2sec
N=16 -> 14772512 12sec
N=17 -> 95815104 84sec
N=18 -> 666090624 628sec

  CPU = Athlon 2100++(1.73GHz)

../temp/queenbit1.c


Re:N Queens Problem 投稿者:塗り壁  投稿日:04月23日(水)01時11分20秒

御無沙汰しています。相互リンクさせてもらっている
「点と線の部屋」の塗り壁です。工学社から出ている雑誌
「I/O」に「数学的プログラミング」という連載を
今月号から始めました。発売は毎月18日です。
で、何と言う偶然か1回目のテーマが「N−クイーン
問題」です。順列や組合せの観点から問題を多方面に解析
していきたいと思っています。
よろしければ、見て下さい。


Re:N Queens Problem 投稿者:高橋謙一郎  投稿日:04月23日(水)00時11分49秒

 Jeff Somers さんのプログラムはまだ解析していませんが、
藤原さんの queen4.c はグッドアイデアが集積していて勉強
になります。ちょっと思い付いた枝刈りを追加してqueen4a.c
を作ってみました。(ソースは下)

**** queen4.c (オリジナル)
N=15 -> Total count 285053 5sec
N=16 -> Total count 1846955 37sec
N=17 -> Total count 11977939 247sec

**** queen4a.c (修正版)
N=15 -> Total count 285053 3sec
N=16 -> Total count 1846955 22sec
N=17 -> Total count 11977939 150sec
N=18 -> Total count 83263591 1107sec

  CPU = Athlon 2100++(1.73GHz)

Jeff Somers さんのプログラムはビット処理で高速化している
だけなのか、それともグッドアイデアが潜んでいるのか、解析
に手間取りそうな感じです。

../temp/queen4a.c


Re:N Queens Problem 投稿者:あら  投稿日:04月22日(火)21時33分53秒

どうもお久しぶりです。
興味があったのでWebでちょっと調べてみました。
世界記録はN=23のようです。
http://www.durangobill.com/N_Queens.html
詳しいことは不明ですが、多分分散コンピュータとかの世界なんでしょうね。

アルゴリズムについてはあまり調べていませんが、
http://www.jsomers.com/nqueen_demo/nqueens.html
のソースが参考になりそうです。


N Queens Problem 投稿者:deepgreen  投稿日:04月21日(月)23時39分36秒

ご無沙汰しております。deepgreenです。
静かなので、ちょっと落書きです。

今度の連休をあてこんで、N Queens Problem(すべての解を求めるもの)
を高速に解くSolverを検討しています。
N=18までは、解が求められているのをみつけました。
その先はどこまでいけるのでしょうか?
当面の目標は、以下のURLに公開されている queen4.c というSolverを
超えることですが、問題が単純なだけに、ちょっとてこずるかも知れません。

  http://www.pro.or.jp/~fuji/puzzlestudy/8queen.html

興味のある方は、一緒にチャレンジしてください。


re:倉庫番解答ソフトで 投稿者:高橋謙一郎  投稿日:02月12日(水)23時39分19秒

倉庫番 for Windowsは倉庫番Perfectと同じ内容なので、レベル16のステージ6は、
Perfectの276面ということになります。(レベル−1)×18+ステージ

私の作ったSolverでは解けませんでしたが、deepgreenさんの作った、DGsoko#2.1
では 341moves 60pushes で解けているようです。

ちなみに、この掲示板ではこういう質問には応対していませんのであしからず。


倉庫番解答ソフトで 投稿者:まお  投稿日:02月10日(月)17時37分16秒

はじめまして、まおと言います。
以下のようにステージを真似て作ったのですが。   
  
     #####
     #   #
     # $$#
  #### . ####
  # $ *.*   #
  # $.....$ #
  #   *.* $ #
  #### . ####
     #$$$#
     # @ #
     #####
ソフトでも解けません^^;;
図は間違ってないと思います。

倉庫番のソフトは
THINKING RABBITの倉庫番 for Windowsです
↑のステージはレベル16のステージ6です。
解けるのでしょうか??
よろしくお願いします。m(__)m


8番目のN=17問題図 投稿者:あら  投稿日:02月07日(金)13時32分16秒

私も2つ目を見つけました。
特に目新しいことはやっていません。

- 9 8 - - - - - - 
- - - - 7 - - - - 
- - - - 1 5 - - - 
1 - - - - - - - - 
- - - 2 - - - - 9 
- - - 9 - 6 - 8 2 
- - - - - - - 3 - 
5 - 1 - - - - - - 
- - - 4 - - - 2 - 

http://www8.plala.or.jp/ara3/


7番目のN=17問題図 投稿者:浅海 焔  投稿日:01月27日(月)00時07分53秒

ヒント数17の問題図、また見つかりました。

 - - 1 - 2 - 7 - -
 - 5 - - - - - 9 -
 - - - 4 - - - - -
 - 8 - - - 5 - - -
 - 9 - - - - - - -
 - - - - 6 - - - 2
 - - 2 - - - - - -
 - - 6 - - - - - 5
 - - - - - 9 - 8 3


実は前から3つの数字による閉所を探すことは試しています。
今のところ、盤面が9x9であることに依存している上に
すべての閉所を探せているわけでもないという怪しげな方法だったりしますが。
とりあえず以下のような閉所を探します。

6マスで閉じている例
A口□ B口口 C口口     A口□ C口口 口口口
B口口 C口口 A口口 または B口□ A口口 口口口
口口口 口口口 口口口     C口□ B口口 口口口

7マスで閉じている例(左右2つの例は性質が微妙に違います)
A口□ B口口 C口口     A口□ B口口 口■■
B口口 A口口 口●● または B口□ A口口 C口口(■のどちらかにC
C口口 口■■ A口口     C口□ 口●● A口口 ●のどちらかにB)

8マスで閉じている例
A口□ C口口 B口口
B口口 A口口 C口口
C口口 B口口 口■■(■のどちらかにA)

9マスで閉じている例
A口□ C口口 B口口
B口口 A口口 C口口
C口口 B口口 A口口

不完全な手法ながら、効果はあるんじゃないかと思っています。


6番目のN=17問題は副産物 投稿者:高橋謙一郎  投稿日:01月26日(日)22時20分23秒

浅海さんが最初に見つけたN=17の問題から副産物が出てきました。
ヒント位置を1ケ所変更することでもN=17の問題として成立する
パターンがあったのです。(解答図も同じです)
尚、このようなものを他の4つで見つけることは出来ませんでした。

#3
 1 - - - - - - - -
 - - 2 7 4 - - - -
 - - - 5 - - - - 4
 - 3 - - - - - - -
 7 5 - - - - - - -
 - - - - - 9 6 - -
 - 4 - - - 6 - - -
 - - - - - - - 7 1
 - - - - - 1 - 3 -
Hints: 17
Author: 浅海 焔

#6
 1 - 4 - - - - - -
 - - 2 7 4 - - - -
 - - - 5 - - - - -
 - 3 - - - - - - -
 7 5 - - - - - - -
 - - - - - 9 6 - -
 - 4 - - - 6 - - -
 - - - - - - - 7 1
 - - - - - 1 - 3 -
Hints: 17
Author: 浅海 焔 + 高橋謙一郎


 ホームページへ戻る 書き込みリストへ戻る