ホームページへ戻る  書き込みリストへ戻る
「コンピュータ&パズル」訪問者の自由メッセージコーナー

お気づきの点や感想要望などなんでもOK!


re:高橋の数タイプ1  投稿者:deepgreen  投稿日: 8月25日(金)00時23分47秒

「高橋の数」の0の扱いがようやくわかりました。
 高橋正視さんのHPで「高橋の数」が再定義されています。

 いままで、我々が考えていたのは、タイプ2に分類されるもので、もともとは、
 タイプ1が原点で、
   7308の 最小数を 0378 とするのがタイプ2
   これを   3078(桁落ちしない範囲の最小数)とするのがタイプ1
 だそうです。
 タイプ1は、以前、高橋謙一郎さんが、問題にしていたものですね。
 ということで、タイプ1もやってみようと思っています。


re:「高橋の数」 投稿者:deepgreen  投稿日: 8月21日(月)01時05分57秒

「高橋の数」の結論をやっとHPに載せることができました。
 暇な人は見にきてください。

 ハイライトは、「高橋の数」の一般式を求めるアルゴリズムです。

http://www2.tokai.or.jp/deepgreen/


カラーお絵かきロジック 投稿者:ゆたか  投稿日: 8月12日(土)04時55分58秒

下の話題とは全然関係ないですが、ここ最近、お絵かきロジック(ののぐらむ、ピクロス)の
ソルバーを作ってました。とりあえず、動くだけのものはできたんですが、パズル系雑誌に
掲載されているような上級レベルの問題になると、解くのに数分かかってしまい、まだまだ
出来が悪いです。
高橋さんのJavaソルバーで試すと、10秒もかからずに解けてしまうので、おどろきです。

せっかくなので、カラーお絵かきロジックにも対応してみました。
基本的に同じアルゴリズムで解ける様子。

以上、雑談でしたσ(^_^)

↓8/11付けの日記に実行結果を載せてます。

http://cgi3.tky.3web.ne.jp/~yutakakn/diary/index.html


N色ライツアウト 投稿者:高橋謙一郎  投稿日: 8月10日(木)21時49分08秒

さっそく私も試してみました。おやおや、ちゃんと解けますね。
驚きました。deepgreenさんに見事に解決されてしまいました。

deepgreenさんて、いったいどういう人なの? 凄いですね!

宿題をお盆休みに残さないようにHPを更新しました。(下のURL)
読んでもらえれば判りますが後半は説明する気力を無くしてし
まいました。

ひとつだけ補足すると「最初に立てる連立式」は2色のものとは
異なります。最初に2色と同じと言ってしまったのは私ですが
間違いでした。でないとせっかく方程式を解いても実際にN色
ライツアウトを得られた結果の式を使って計算させてもライツ
がアウトになってくれません。

../../index.htmlnt/light/light3.html


re:思考錯誤してみました。(4色ライツアウト) その3   投稿者:deepgreen  投稿日: 8月10日(木)02時24分35秒

続き
*** final *** Color=6,Raw=5,Col=5
  1 - - - - - - - - - - - - - - - - - - - - - 2 2 3  4 3 3 1 2 - 2 5 - 3 - 2 2 3 1 4 - - - 5 2 - 4 4 -
  - 1 - - - - - - - - - - - - - - - - - - - - 2 3 2  1 1 2 3 5 4 3 - 2 4 4 4 5 3 1 - 2 - 1 4 - - 4 4 -
  - - 1 - - - - - - - - - - - - - - - - - - - 4 3 3  5 3 2 4 1 4 2 4 5 1 1 5 5 4 5 2 5 - 5 2 4 - 3 1 -
  - - - 1 - - - - - - - - - - - - - - - - - - 1 - 1  3 5 3 3 4 4 1 1 3 5 4 1 4 - - 3 2 - 5 1 3 - 1 - -
  - - - - 1 - - - - - - - - - - - - - - - - - 2 4 3  4 - 4 5 1 2 4 3 2 1 2 3 5 1 2 5 4 - 2 2 1 - 1 1 -
  - - - - - 1 - - - - - - - - - - - - - - - - 2 1 1  2 2 1 2 5 2 1 1 4 5 2 - 5 - 4 2 4 - 5 3 4 - 4 4 -
  - - - - - - 1 - - - - - - - - - - - - - - - 4 4 4  2 - 5 4 4 4 5 3 5 4 1 1 - 2 5 - 5 - - 1 - - 1 3 -
  - - - - - - - 1 - - - - - - - - - - - - - - 5 - -  3 3 - 2 2 - - 1 2 2 3 2 4 5 - 1 3 - 1 5 5 - 4 1 -
  - - - - - - - - 1 - - - - - - - - - - - - - 5 5 5  - 4 3 1 - 2 5 4 2 5 5 3 4 1 5 2 1 - - 1 4 - 1 4 -
  - - - - - - - - - 1 - - - - - - - - - - - - 3 2 2  5 1 5 4 2 - 1 2 1 - - 2 3 5 4 4 - - 5 3 2 - 4 5 -
  - - - - - - - - - - 1 - - - - - - - - - - - 4 5 4  4 1 3 5 1 1 4 3 3 - 3 3 5 1 2 - 3 - 1 3 - - 3 1 -
  - - - - - - - - - - - 1 - - - - - - - - - - 5 4 5  4 - 4 1 2 2 4 1 5 3 2 5 4 2 2 3 4 - 5 5 3 - 5 - -
  - - - - - - - - - - - - 1 - - - - - - - - - - - -  2 2 2 1 5 2 - 1 4 - 2 1 5 - 3 1 4 - - 3 5 - 3 3 -
  - - - - - - - - - - - - - 1 - - - - - - - - 4 5 4  1 5 1 2 4 - 5 4 5 - - 4 3 1 3 2 - - 1 2 4 - 2 2 -
  - - - - - - - - - - - - - - 1 - - - - - - - 2 1 2  3 1 - 2 3 2 2 3 1 1 5 4 - 5 1 1 1 - 5 - 5 - - 2 -
  - - - - - - - - - - - - - - - 1 - - - - - - 1 2 2  2 3 4 4 4 1 3 1 - 4 - 4 4 3 4 1 1 - 1 1 5 - - 1 -
  - - - - - - - - - - - - - - - - 1 - - - - - 5 5 5  - 3 4 1 - 3 5 4 1 5 4 3 4 1 - 2 2 - - - 4 - - 5 -
  - - - - - - - - - - - - - - - - - 1 - - - - 4 3 3  2 2 5 - 5 2 3 5 2 1 5 - 3 4 4 5 1 - 5 3 1 - 4 - -
  - - - - - - - - - - - - - - - - - - 1 - - - 1 1 1  - - - - - - - - - - - - - - - - - - - - - - - 1 -
  - - - - - - - - - - - - - - - - - - - 1 - - 3 4 4  3 5 - 4 3 4 4 3 5 5 1 2 - 1 5 5 5 - 1 1 1 - - 3 -
  - - - - - - - - - - - - - - - - - - - - 1 - 2 - 1  - 5 1 2 1 1 - 4 2 3 5 2 5 1 - 4 - - 4 2 3 - 3 5 -
  - - - - - - - - - - - - - - - - - - - - - 1 3 4 3  4 4 1 - 1 4 3 1 4 5 1 - 3 2 2 1 5 - 1 3 5 - 3 - -
  - - - - - - - - - - - - - - - - - - - - - - 3 3 3  2 5 1 4 2 5 4 2 5 - 1 2 - 1 5 4 5 1 1 - 2 - 5 3 -
  - - - - - - - - - - - - - - - - - - - - - - 3 3 3  2 - - 3 4 4 4 3 5 5 2 1 - 2 4 5 5 - 1 1 - 1 - 2 -
  - - - - - - - - - - - - - - - - - - - - - - 3 3 3  3 1 - 2 3 2 2 3 1 1 5 4 - 5 1 1 1 - 5 5 5 - - 3 1

*** end


re:思考錯誤してみました。(4色ライツアウト) その2  投稿者:deepgreen  投稿日: 8月10日(木)02時22分57秒

以下にColor=4、6の解を添付
−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−−

*** final *** Color=3,Raw=5,Col=5
省略
*** final *** Color=4,Raw=5,Col=5
  1 - - - - - - - - - - - - - - - - - - - - - - - 1  - 3 3 1 - 2 2 1 - 3 - - 2 3 1 2 - 2 2 1 2 - 2 - -
  - 1 - - - - - - - - - - - - - - - - - - - - - 1 -  3 1 2 1 1 - 3 - - 2 2 - 3 1 1 2 - - 3 - - 2 2 - -
  - - 1 - - - - - - - - - - - - - - - - - - - - 3 3  3 2 3 3 3 3 - 1 3 2 2 2 1 3 - 1 3 1 1 3 2 1 2 - -
  - - - 1 - - - - - - - - - - - - - - - - - - - 3 -  1 1 3 - - 2 3 - 2 - 2 2 - 2 2 2 1 - 2 - 3 3 1 - -
  - - - - 1 - - - - - - - - - - - - - - - - - - 2 1  - 1 3 - 1 3 - - - - 1 - 1 - 3 - 2 3 - 1 1 3 2 - -
  - - - - - 1 - - - - - - - - - - - - - - - - - 3 3  2 - 3 2 3 2 3 3 - 3 2 - 3 - 2 - - 2 3 3 2 2 - - -
  - - - - - - 1 - - - - - - - - - - - - - - - - - -  2 3 - 3 - 3 3 2 1 1 - 2 2 1 2 3 1 1 2 - - 1 2 - -
  - - - - - - - 1 - - - - - - - - - - - - - - - 1 1  1 - 1 - - 3 2 3 3 - 2 - - 2 1 3 - 3 2 1 3 2 3 - -
  - - - - - - - - 1 - - - - - - - - - - - - - - - -  - - 3 2 - - 1 3 3 2 3 - 2 3 3 1 2 - 1 - 2 1 3 - -
  - - - - - - - - - 1 - - - - - - - - - - - - - 3 3  3 2 2 - - 3 1 - 2 - 1 2 3 2 3 2 1 1 2 3 - 2 1 - -
  - - - - - - - - - - 1 - - - - - - - - - - - - 1 -  - 2 2 2 1 2 - 2 3 1 2 2 1 - 3 3 3 3 1 - - 1 - - -
  - - - - - - - - - - - 1 - - - - - - - - - - - 3 -  - - 2 2 - - 2 - - 2 2 2 - - 2 - 3 2 2 - 3 1 1 - -
  - - - - - - - - - - - - 1 - - - - - - - - - - - -  2 3 1 - 1 3 2 - 2 3 1 - 3 3 2 - 2 3 2 - 1 3 2 - -
  - - - - - - - - - - - - - 1 - - - - - - - - - 1 -  3 1 3 2 - - 1 2 3 2 - - 3 3 3 - - - 1 - - - - - -
  - - - - - - - - - - - - - - 1 - - - - - - - - 3 -  1 1 - 2 3 2 2 1 3 3 3 2 2 3 3 1 3 - 1 - 1 2 2 - -
  - - - - - - - - - - - - - - - 1 - - - - - - - 1 1  2 2 1 2 - - 3 3 1 2 3 - - - 1 1 2 1 2 1 3 - 3 - -
  - - - - - - - - - - - - - - - - 1 - - - - - - - -  - - 3 1 2 - 1 - 2 1 3 3 2 - 3 2 3 3 1 - - 2 3 - -
  - - - - - - - - - - - - - - - - - 1 - - - - - 3 3  2 - 1 - 3 2 1 3 - 1 3 2 3 - - 1 3 - 1 3 1 2 2 - -
  - - - - - - - - - - - - - - - - - - 1 - - - - - -  2 3 1 2 - 3 2 2 1 2 1 2 2 1 1 2 1 1 3 - - 2 1 - -
  - - - - - - - - - - - - - - - - - - - 1 - - - 1 1  1 - 3 - 1 3 - 1 - 3 - - - - - 1 - 3 - 1 3 - 1 - -
  - - - - - - - - - - - - - - - - - - - - 1 - - 2 3  2 - 2 3 1 2 - 3 2 - - 3 1 - 1 3 - 1 - 3 1 1 2 - -
  - - - - - - - - - - - - - - - - - - - - - 1 - 1 -  - 2 1 3 3 2 1 2 1 2 1 1 3 - 2 - 2 2 2 - 1 3 3 - -
  - - - - - - - - - - - - - - - - - - - - - - 1 1 1  2 2 2 1 2 - 2 3 3 1 - 1 2 - 2 3 3 2 1 1 2 3 - - -
  - - - - - - - - - - - - - - - - - - - - - - - - -  - 3 1 1 2 1 - 3 - 1 3 1 - 3 1 3 - 1 - 3 2 3 3 1 -
  - - - - - - - - - - - - - - - - - - - - - - - - -  3 - 1 - 3 1 - 3 - 1 - - - - - 3 - 1 - 3 1 - 3 - 1
続く


re:思考錯誤してみました。(4色ライツアウト) その1 投稿者:deepgreen  投稿日: 8月10日(木)02時19分03秒

5x5のColor=2〜9までは、連立方程式がとけました。(あってるかな?)

ポイントは、掃出しの基点となる係数には、A*R=1 mod p となる
Rが存在する(逆数が存在する)Aの範囲にとどめることです。
例えば、2*R=1mod4となるRは存在しませんので、掃出しの基点と
なる係数には2を使用できません。

6色の場合、新しい条件式のパターンがあらわれました。

3*(X+Y+Z)=Aという形をしています。
(23) - - - - - - - - - - - - - - - - - - - - - - 3 3 3  2 5 1 4 2 5 4 2 5 - 1 2 - 1 5 4 5 1 1 - 2 - 5 3 -
(24) - - - - - - - - - - - - - - - - - - - - - - 3 3 3  2 - - 3 4 4 4 3 5 5 2 1 - 2 4 5 5 - 1 1 - 1 - 2 -
(25) - - - - - - - - - - - - - - - - - - - - - - 3 3 3  3 1 - 2 3 2 2 3 1 1 5 4 - 5 1 1 1 - 5 5 5 - - 3 1

mod 6の世界では、3*1=3;3*2=0;3*3=3;3*4=0;3*5=3;
となるので、

  (23)〜(25)の右辺に0,3以外の数字があらわれたら解は存在しないことになります
  (23)〜(25)の右辺は0,3のいずれか一方でなければならない(左辺は同じだから)
  よって、右辺が0の場合、X+Y+Z=0、2、4という制約になる。
      右辺が3の場合、X+Y+Z=1、3、5という制約になる。

従来の解の存在条件式は、存在条件のみを要請するものであったが、今回の新しい
パターンでは、解の存在条件だけでなく、変数の制約をも要請するものである。


(おまけ)
pが素数の場合、フェルマの定理「A^(p-1)=1 mod p (ただしA≠0)」
により、どのようなA(≠0)でもRが存在するので必ずとけます。

続く


re:思考錯誤してみました。(4色ライツアウト) 投稿者:高橋謙一郎  投稿日: 8月 8日(火)23時12分27秒

eXorさん、考察ありがとうございます。私が考察しているもと漠然と近いものがあります。

> だから両辺共に単純に半分に割ることはできないのでは。

そうなんですね。そして係数を1にする方法が無いのなら方程式は解けなかったと言わざるを得ません。
一般にN色ライツアウトを連立方程式で解く場合その方程式が解けるのはNが素数の場合に限られます。
では、色数が素数で無い場合は連立方程式を使った解き方が出来ないのかと言うとそうではありません。

> 左辺を110001にするなら、右辺の0を0と2、右辺の2を1と3のどちらにするか、正しく
> 選べばいいのではないでしょうか。

これは2段階の演算を行うことで可能です。色数(N)が素数でないライツアウトを解く為には、先ず
Nを素因数分解し、分解されたそれぞれの素数での計算式を適用することで解くことが出来ます。
例えばN=4の場合なら素因数分解すると2×2となるので「2色ライツアウト」の計算式を2段階で
使用します。例えば、答えが見え見えの簡単な例で示すと、

   問題面   押下法1   結果面1   押下法2   結果面2    押下法(1,2を合成)
  11022 10000 22022 20002 00000   30002
  10002 00000 20002 00000 00000   00000
  00000 00000 00000 00000 00000 → 00000
  30000 00000 00000 00000 00000   00000
  33000 10000 00000 00000 00000   10000

最初の2色ライツアウト計算式適用では、問題面の数字が2で割り切れるものは0と見なされます。
従って、結果面1は[0,2]だけの集合になります。何故ならmod2の世界では解けたと見なされ
ている状態だからです。2回目の計算式の適用は結果面1で 0→0,2→1 と見なして式を適用し、
得られた結果を今度は2倍します(2回押す)。そして、押下法1と押下法2を合成すると最終的な押下
法が得られることになります。これが現時点での私の結論ですが、課題が3つあります。

課題1
 何故、連立方程式が解けるのは色数が素数の場合に限られるのかは実験結果によるもので、まだ証明
 が出来ていません。(1000色までプログラムでテストした結果によります)

課題2
 4色ライツアウトは一発で解を得るのではなく2発で解を得ることになります。12色(2*2*3)なら
 3発で解を得ることになります。計算式レベルの段階で合成して一発で解を得る計算式を作れない
 ものだろうか。

課題3
 解が存在するとき、何通りの解があると言えるのか?(4色なら2色×2色(16通り)なのか?)

#もう少し詳しい説明をその内HPにアップしようと考えています。


思考錯誤してみました。 投稿者:eXor  投稿日: 8月 8日(火)21時38分50秒

 まず、『係数2』の意味ですが。
 右辺の全ての項の係数が2でないなら、解が2通りある事を意味するでしょう。
 例えば、

> X=3, Y=2, C=4
> 1: 2----2 113-3-
> 2: -2---- 11321-
> 3: --2--2 33323-
> 4: ---1-1 -311--
> 5: ----2- 313-1-
> 6: ------ 1-33-1

 上の1235式を2倍すると全て

2倍: ------ 222-2-

 このような、同じ式になります。これは、
   222
   020
 という押下パターンが『0解』である事を示しています。


 さて、次に両辺が2で割れない問題ですが。

 これはmodの影響で、2倍して0になる数が0と2、2になる数が1と3と、各2つあるからと思います。
( 0*2 mod 4 = 2*2 mod 4 , 1*2 mod 4 = 3*2 mod 4 )
 だから両辺共に単純に半分に割ることはできないのでは。

 例えば上の1,2式を足しあわせたものを考えると、
1+2式: 220002 222200
 左辺を110001にするなら、右辺の0を0と2、右辺の2を1と3のどちらにするか、正しく
選べばいいのではないでしょうか。

 もっともこれは仮説です。本当に110001となるパターンがあるかどうかは不明です。


 もし上の仮説が成立するならば。
 4式、6式と、1,2,3,5のうちいずれかを2倍した式、さらには1+2,1+3,1+5式の左辺をどう
にか2で割って右辺を調節したもの…以上の6式で、マトリックスが作れるのでは?
(※1,2,3,5式は2倍すると全て等しくなる、いわば同じグループの式なので、どの2式を足し
あわせても右辺が全て0か2になります。)

 ちょうど書いてみるなればこんな感じですね。

   4: ---1-1 -311--
(1+2)/2: 11---1 ??????
(1+3)/2: 1-1--- ??????
(1+5)/2: 1---11 ??????
式の2倍: ------ 222-2-
   6: ------ 1-33-1


re:素朴な疑問(4色ライツアウトの場合) 投稿者:高橋謙一郎  投稿日: 8月 8日(火)00時42分43秒

3色ライツアウトのゴマカシが解決しました。近い内に全面改定します。
しかし4色の場合は今だ未解決です。両辺を2で割るのは間違いでした。

 (2)mod4=(2+2+2)mod4...これは正しい式
 (1)mod4=(1+1+1)mod4...これは正しくない

ところで4色ライツアウトの一発計算式は作ることが出来ました。
あれこれやって偶然見付けたのですが何故そうなるのか説明が付い
ていません。mod演算の定理を全く知らないので...


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