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

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


ルービックキューブの解読プログラム 投稿者:tsuyoshik 投稿日:03月10日(月)21時47分34秒


1.初めての書き込みです。宜しくお願いいたします。
 パズルの解読プログラムの作成を趣味とし、そのいくつかをHP公開している者です。
 プログラム手法の多くは本講座で習得させていただいております。
 WATTA君を含め、このサイトの熱烈なファンの一人です。
2.先頃、解読プログラムを搭載したRubikcubeをHP公開しました。
 今思えば、無謀ながら取り組み当初の目標は、スクランブルされた状態から完成体まで 一気に導く最短手順の追求でした。それは成らず、今のプログラムは第一ステップで
 一段目、次を二段目と都合4ステップから成り立っております。もう一段の工夫が成され れば、3ないし2ステップの組み立てが可能との感触を抱いております。
 工夫とは、例えばメモリーの有効化、検索スピードの向上です。
3.高橋さん始めここに登場される方の中で、どなたかが興味を持ち、何がしかのヒントを 与えてくださるなら大変うれしいです。
4.ここに書き込む前に「ルービック、解、最短手数」でネット検索を行いました。「スパ コンにて、26手以内でルービックを復元できることを証明」とのトピックスが2007/7に あったことを知りました。スパコンとパソコンで何がどのくらい異なるのか自分にはわ かりません。ただ、速度が極めて速ければ、あるいはメモリーが無限にあるならば26手 以内どころか本当の最短手数も容易に求められるはずと思いました。
5.「簡易ナンプレ自動作成」すごいですね!トレースしました。確かに完全問題を数秒で
 次から次へ作成してくれました。数独の解読プログラムを公開している身としてはより 驚きです。技量不足の為、中身は読み解けておりません。後日勉強させていただきます

http://www.geocities.jp/tsuyoshik1942/rubikcube2.html


簡易ナンプレ自動生成 投稿者:稲葉直貴 投稿日:03月01日(土)17時35分52秒


お久しぶりです。

最近どれだけ簡単な仕組みでナンプレを自動生成させられるかに挑戦してます。
ヒント数が25以下で90度回転対称のナンプレを10秒程度で作るという条件で
かなりシンプルなものができたので紹介させてください。※JAVAです。

class Q{static int e=81,x,y,z,s,k,l,m,n,v,c[];public static void main(String[]a
){for(;s<e;){for(c=new int[3*e];n>1;n/=3)c[m=(int)(Math.random()*e)]=m;for(c[40
]=m%2;n<e*9;++n)if(c[n/9%9*9-n/e+8]>0){for(l=3*e;l>e;s=0)c[--l]=511;for(++c[n/9
];l>0;)if(c[--l+2*e]>e&((k=1<<(c[l]-1)%9)>0|((v=c[x=l/9+90]&c[y=99+l%9]&c[z=l%9
/3+l/27*3+e])&v-1)<1)){s=(k>(k&v)|v<1)?0:++s;c[x]&=v=k>0?~k:~v;c[y]&=v;c[z]&=v;
for(c[l+2*e]=l=e;m<s;m=s)n=-1;}}}for(;e-->0;)System.out.print(--c[e]%9+1+(e%9<1
?"\n":" "));}}

出力例:

0 4 0 0 0 2 0 1 0
5 0 3 0 0 0 2 0 4
0 6 0 0 0 0 0 3 0
8 0 0 0 4 0 0 0 0
0 0 0 5 6 3 0 0 0
0 0 0 0 8 0 0 0 1
0 7 0 0 0 0 0 2 0
4 0 2 0 0 0 7 0 5
0 3 0 1 0 0 0 6 0

http://puz.hp.infoseek.co.jp/


re:10x10のライツアウト 投稿者:高橋謙一郎 投稿日:01月31日(木)21時41分29秒


ミレイさん、こんにちは

ライツアウトは総てのNxMについて既に解決された問題という認識を持っています。
ミレイさんの報告はプログラムを使わずに自力で調べたということなのでしょうか。
ライツアウトには組み合せ探索を一切する事なく一発で解を求める方法があります。

尚、ライツアウトは10x10のように全ての局面で解が存在する場合は解は常に1つです。
そのような大きさのものには以下のようなものがあります。

1x1,2x2,3x1,3x3,4x1,4x2,4x3,5x4,6x1,6x2,6x3,6x4,6x5,6x6,7x1,7x3,7x4,7x6,7x7,8x2,
8x4,8x8,9x1,9x3,9x6,9x7,10x1,10x2,10x3,10x4,10x5,10x6,10x7,10x8,10x9,10x10,11x4,
11x6,11x10,12x1,12x2,12x3,12x4,12x5,12x6,12x7,12x8,12x9,12x10,12x11,12x12,13x1,
13x3,13x4,13x6,13x7,13x9,13x10,13x12,13x13,14x2,14x6,14x8,14x10,14x12,15x1,15x3,
15x4,15x6,15x7,15x9,15x10,15x12,15x13,15x15,16x1,16x2,16x3,16x4,16x5,16x6,16x7,
16x8,16x9,16x10,16x11,16x12,16x13,16x15,17x4,17x10,17x12,17x16,.........

../../index.htmlnt/light/light2.html


10x10のライツアウト 投稿者:ミレイ 投稿日:01月28日(月)16時18分13秒


初めまして。ミレイと申します。10x10のライツアウトの解を調べて、最近結果が出たので書き込ませていただきます。

解:44手(唯一解)
*-*----*-*
-*--**--*-
*-*-**-*-*
---*--*---
-**-**-**-
-**-**-**-
---*--*---
*-*-**-*-*
-*--**--*-
*-*----*-*

全ての局面でクリア可能です。
1列目の点灯している場所の下を反転させて1列目を全て消灯させます。
2列目以降も同様に行い、光を下へ下へと追いやっていき、最終的には10列目のみが点灯している状態にします。
10列目の消し方は以下に書いておきます。90が左端で99が右端です。

90 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- *--------- 90 --*------- -***------ *---*----- *-*-**---- --*-*-*--- **---***-- --------*- **---**-** --*-*---*- *-*-*-**--
91 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- -*-------- 91 -*-*------ **-**----- -*-*-*---- ----***--- -*-----*-- ***-**-**- -------*-* ***-***-** -*---*-*-* ------***-
92 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --*------- 92 *-*-*----- *-*-**---- ----*-*--- *-**-***-- *---*---*- -**-*-*-** ------*-*- -**-**---- *-------*- *-*-**-***
93 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---*------ 93 -*-*-*---- **-*-**--- -*---*-*-- --***-***- ---*-*---* ----**-*-* -----*-*-- --------** -----*---- ----***-**
94 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ----*----- 94 --*-*-*--- -**-*-**-- *-*---*-*- **-***-*** *-*-*-*--- -***-**-** ----*-*--- -**-**-*** *---*-*-*- *-**-***--
95 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- -----*---- 95 ---*-*-*-- --**-*-**- -*-*---*-* ***-***-** ---*-*-*-* **-**-***- ---*-*---- ***-**-**- -*-*-*---* --***-**-*
96 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ------*--- 96 ----*-*-*- ---**-*-** --*-*---*- -***-***-- *---*-*--- *-*-**---- --*-*----- **-------- ----*----- **-***----
97 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- -------*-- 97 -----*-*-* ----**-*-* ---*-*---- --***-**-* -*---*---* **-*-*-**- -*-*------ ----**-**- -*-------* ***-**-*-*
98 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- --------*- 98 ------*-*- -----**-** ----*-*-*- ---***---- --*-----*- -**-**-*** *-*------- **-***-*** *-*-*---*- -***------
99 ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------- ---------* 99 -------*-- ------***- -----*---* ----**-*-* ---*-*-*-- --***---** -*-------- **-**---** -*---*-*-- --**-*-*-*


re:バックトラック法で迷路 投稿者:かっぱ 投稿日:10月22日(月)11時24分38秒

void backtracking(int i, int j) {
  searchMaze(i+1, j);
  searchMaze(i-1, j);
  searchMaze(i, j+1);
  searchMaze(i, j-1);
}

void searchMaze(int i, int j) {
  if(myMaze[i][j] == '.') {
    myMaze[i][j] = '@';
    backtracking(i, j);
    myMaze[i][j] = '.';
  } else if(myMaze[i][j] == 'g') {
    showMaze();
  }
}

お騒がせしました。
xに変更したのは一度訪れた場所を
今後サーチして欲しくない気持ちが込められていました。。。
バックトラック法を理解してなかったですね^^;
でもいまはよくわかりました、ありがとうございます!


re:バックトラック法で迷路 投稿者:高橋謙一郎 投稿日:10月19日(金)21時31分45秒


かっぱさん、こんばんは。

バックトラックは、関数からぬける時に、グローバルな局面を
必ず元の状態に戻さないといけません。かっぱさんの場合には、
「.」をいったん「@」に変えて再帰呼出しを実行したのだから、
呼出しから戻ってきた後は、元の「.」に戻す必要があります。
「x」にしてはいけません。単なるイージーミスかな?


バックトラック法で迷路 投稿者:かっぱ 投稿日:10月19日(金)10時25分19秒

バックトラック法を使って迷路を解くプログラムを試しに書いてみたのですが...

ゴールにたどり着く全ての道順を表示したいのですが、
なかなかうまくいきませんでした。
何か方法があれば教えてください。
#include <stdio.h>

char maze[6][9]={
  "s#......",
  ".###...#",
  ".......#",
  ".#.##..#",
  ".#..##.#",
  ".#..g#.#"
};

char myMaze[8][10];
/*
  ##########
  #s#......#
  #.###...##
  #.......##
  #.#.##..##
  #.#..##.##
  #.#..g#.##
  ##########
*/

void showMaze() {
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 10; j++) {
      printf("%c", myMaze[i][j]);
    }
    printf("\n");
  }
}

void initMaze() {
  for(int i = 0; i < 8; i++) {
    for(int j = 0; j < 10; j++) {
      myMaze[i][j] = '#';
    }
  }
  for(int i = 1; i <= 6; i++) {
    for(int j = 1; j <= 8; j++) {
      myMaze[i][j] = maze[i-1][j-1];
    }
  }
}


void backtracking(int i, int j) {

  if(myMaze[i+1][j] == '.') {
    myMaze[i+1][j] = '@';
    backtracking(i+1, j);
    myMaze[i+1][j] = 'x';
  } else if(myMaze[i+1][j] == 'g') {
    printf("%d %d\n",i, j);
    showMaze();
  }

  if(myMaze[i][j+1] == '.') {
    myMaze[i][j+1] = '@';
    backtracking(i, j+1);
    myMaze[i][j+1] = 'x';
  } else if(myMaze[i][j+1] == 'g') {
    printf("%d %d\n",i, j);
    showMaze();
  }
 
  if(myMaze[i][j-1] == '.') {
    myMaze[i][j-1] = '@';
    backtracking(i, j-1);
    myMaze[i][j-1] = 'x';
  } else if(myMaze[i][j-1] == 'g') {
    printf("%d %d\n",i, j);
    showMaze();
  }

  if(myMaze[i-1][j] == '.') {
    myMaze[i-1][j] = '@';
    backtracking(i-1, j);
    myMaze[i-1][j] = 'x';
  } else if(myMaze[i-1][j] == 'g') {
    printf("%d %d\n",i, j);
    showMaze();
  }
}

int main() {
  initMaze();

  backtracking(1, 1);


  return 0;
}


re:数独解法プログラミング 投稿者:高橋謙一郎 投稿日:08月17日(金)22時25分22秒


みずきさん、こんにちは。

5年前にエクセル版の数独ソルバーを見たことがあります。
自分が作ったものではなく、ある人がメールに添付してアドバイスを求めてきたものです。
先ほど調べたら、そのメールも添付ファイルもありました。しかし、他へのコピー流布は
しないで下さいという本人の希望があったので、お見せすることが出来ません。

構造的には、制約伝播(演繹法)をエクセル上でシミュレートしたとのことで、マクロ
(VBマクロ)は使われていませんでした。自動計算がオフになっていて、問題面を入力後に
[f9/計算]を押下すると計算が始まってゴールシークのように解が収束していくものでした。

ちなみに、背理法的な手法が必要になる問題は解けませんでしたが、マクロ(VBマクロ)で
再帰呼出しが可能かどうか知りませんが、可能ならどんな問題でも解けるエクセル版の数独
ソルバーは確実に作ることが出来ると思います。


数独解法プログラミング 投稿者:みずき 投稿日:08月15日(水)21時40分22秒


9×9の基本的な数独のプログラミングをやりたいと思っています!!
なんといってもパソコン初心者なので・・・・
できれば、エクセルのマクロでやりたいのですが。できますか??
よいホームページがあれば教えてください!!お願いします☆


倉庫番ソルバーVer7.1 投稿者:高橋謙一郎 投稿日:05月06日(日)14時53分17秒


久しぶりに倉庫番ソルバーを更新しました。(Ver7.1 英語版のみ)

というのも、Ver7.0 は Perfect や Revenge をベースにして作ったもの
なので、海外で独自に作られた面に対しては、どうも成績が良くなかった
のです。なので、今回の最新ソルバー Ver7.1 は、Ver7.0 を多少改良し、
さらに大量のメモリを使用する別種類の最良優先探索を追加しました。

本質的な性能は変わってないのですが、荷物密度の高い面での成績は格段
に良くなったと思います。尚、今回の日本語版は予定していません。

../../index.htmle/soko/index.html


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