<<4>> VERY TINY FORTRAN programming language

    <<4.1>> VTF: Very Tiny FORTRAN document & etc.(1977-)

    <<4.2>> 10-Puzzle Solution； VTF application(1979)

 EASY-4のVTFによる,10-Puzzleの解決について

                                                 190928～190928j Netobi.Nao

1979年にEASY-4のVeryTinyFortran言語を使って,いわゆる10パズル問題を調べる

プログラムを作って問題を解決した件について,ざっと説明します．

私(達)にとって未知の,この数学的課題を解いた事がEASY-4の最大の成果だと思って

います． 10パズル問題については,下記cf0,cf1等を参照して下さい．

文体不統一や記述の重複など,読みにくいかもしれませんが,ご勘弁願います．

1979年6月に10パズル問題の解をEASY-4を使って全て調べてみようとしました．

当時,このパズルの解答は私や周囲の人には知られていない未知の問題でした． 

極めて大袈裟に例えると,４色問題(４色定理,cf2)の証明を1976年に汎用コンピュー

ター(IBM/System370?)を使って解決したのと同様の事を自作CPU上の自作言語(VTF)

で解法プログラムを作り,解決しようとしました．

EASY-4の環境では,たいしたプログラムは作れませんが,なんとか多数の組み合わせ

計算をさせて膨大な可能解を求め,それを元に手作業で不可能解を書き出しました．

EASY-4のVTF環境では,入力可能なプログラムは３画面分程しか有りません． 

１画面が15行ほどなので,数十行程のプログラムしか組めません．その限定で解を求

めるAMI_10という名前のプログラムを作りました(写真参照)．

概要は,0000～9999の整数値の各桁の値A,B,C,Dに対し,計算順序つまり括弧の付け方

の全ての組合せと加減乗除の全ての演算の組合せのどれかで10になった場合は,その

最初の例を表示して次の数に進みます．A,B,C,Dの並びの組合せ順序は24通りありま

すが,順序は無変更です．理由はプログラムが大きくなり過ぎる事です. 代わりに,

0000～9999までの全数で計算します． 従って,例えば,1,1,5,8の解を求めると,1158

では不可能,1185でも,1518,1581,5118,5181,5811でも不可能で,8115になって可能と

なり,表示されます(PAGE=105(他)の写真参照)．

EASY-4にはプリンターが無いので,AMI_10では可能解を画面に表示して,１画面分溜

まると,キーボード入力待ちになります． そして,その画面を撮影した後,キー入力

して処理を進めます． この処理を10日間続けていたら,画面数131で無事に最後まで

求められました.  従ってCPU-timeは約240時間となりますが,実際には,私が不在や

就寝中で即応できずに単なる入力待ちの時間も少なくないと思います．

こうして得られた131枚の可能解の写真から,逆に不可能なケースを手作業で抜き出

し,結果を手書きして名刺サイズにプリントしました(写真参照)． 

知人にもコピーを渡したりして検証段階に入りました． 反例は見付からず,結果は

正しいと思われました． 

2014年になって(つまり35年後!),Wikiにも掲載されている事を知り(cf0),その解を

調べましたが,EASY-4の解と同一でしたので,検証されたと思います．

従って,EASY-4のCPU動作,VeryTinyFortranの動作,解析プログラムAMI_10の全てが

240時間に渡って基本的には正常動作したものと推認しました．

SOLUTION  of 10-PUZZLE  by  EASY-4  VTF

======================================= 

                                                190928～190928j Netobi.Nao

===========================================================================

In 1979, using EASY-4 VeryTinyFortran language, I developed so-called  

10-Puzzle problem. I will briefly explain problem that problem was solved 

by making VTF program.

MOST Great achievement of EASY-4 is to solve this mathematical problem,

which was unknown to us, I am thinking.

Please refer to following cf1, etc. for 10-Puzzle problem.

Duplication of description and inconsistancy and strange description may be

 difficult to read, please pardon!

In 1979/06, I tried to investigate all possible/impossible number of 

10-Puzzle problem using EASY-4 computer. 

At that time, answer of this puzzle was unknown to me and people around me.

Four-color mathematical problem(4-color theorem,cf3) was proved using 

general computer(IBM/System370?) in 1976. To extremely exaggerate, almost 

same thing that I solved with my own CPU and own language. 

I made solution program(AMI_10) and tried to solve it.

In environment of EASY-4, it can not make lot of program step, instead,  

calculate many combination.  Many combination calculation were performed 

to obtain large number of possible solution, and based on that, impossible 

solution was obtained manually!

In EASY-4 VTF environment, source program is within about 3 screen line.

In that limitation, I made VTF program to find solution(AMI_10;see photo).

Outline is calculation order for each value A,B,C,D of integer value from 

0000 to 9999, calculate all combination of parentheses and operator(add/sub

/mul/div). When result is just 10 case, display it, and continue next.

24 combination of A,B,C,D order is unchanged. Reason is that program need 

more line.  Instead, calculate between 0000 to 9999 all.  

So, for example, if you find solution of 1,1,5,8 case, AMI_10 proceed from 

1158(=not possible), 1185(=not),1518,1581,5118,5181,5811(=not), and then 

8115 is possible, and display this case(see photo PAGE = 105(,other)).

Since EASY-4 do not have printer, AMI_10 display possible solution.  When  

full, it wait for keyboard input. After shooting screen, key in to proceed. 

I continued this procedure for 10 day and at last, finished 131-page.

Therefore, CPU-time is about 240 hour. But I think it include waiting time

for key-input, because of my absence or sleeping, etc.

From 131-page possible solution photo print, impossible case was manually 

extracted and handwritten and printed on business card size (see photo).

I gave copy to acquaintance and entered to verification stage. 

No counterexample was found, result seemed correct.

In 2014 (=35 year later!), I knew that it was posted on Wikipedia(cf1), I 

checked Wiki solution. It was same as EASY-4's, so I think it was verified.

Therefore, it was assumed that EASY-4_CPU and VeryTinyFortran and AMI_10 

operate all basically normally for 240 hour.

Reference Web-site：

cf0(10-パズル): https://ja.wikipedia.org/wiki/%E3%83%86%E3%83%B3%E3%83%91%E3%82%BA%E3%83%AB

cf1(10-Puzzle): https://curiosity.com/topics/can-you-solve-the-10-puzzle-curiosity/

cf2(4色問題): https://ja.wikipedia.org/wiki/%E5%9B%9B%E8%89%B2%E5%AE%9A%E7%90%86

cf3(4ColorTheorem): https://en.wikipedia.org/wiki/Four_color_theorem

---  F i n  ---