数独の正解図をランダムに作る

1つの数字に着目して、3×3のブロックごとに配置できる可能性を考えていくと
9*6*3*6*4*2*3*2*1 = 46656通りある。
まずは事前にそれをすべて書き出すことにする。
(過去にやったのでそのまま流用)
touch-sp.hatenablog.com

036147258
036147285
036147528
036147582
・
・
・

46656個の文字列(9文字)から1文字目、2文字目、3文字目・・・とすべて重複しないようにランダムに9個抽出することが今回のストラテジーである。

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> mylist = new List<string>();

            using (System.IO.StreamReader file = new System.IO.StreamReader("resource.txt"))
            {
                string line = "";
                // test.txtを1行ずつ読み込んでいき、末端(何もない行)までwhile文で繰り返す
                while ((line = file.ReadLine()) != null)
                {
                    mylist.Add(line);
                }
            }

            string[] b = new string[9];
            int[] kazu = new int[81];

            int[] start_position = { 0, 3, 6, 27, 30, 33, 54, 57, 60 };
            int[] next_position = { 0, 1, 2, 9, 10, 11, 18, 19, 20 };

            List<string> result = new List<string>();

            Stopwatch sw = new Stopwatch();
            sw.Start();

            for (int mycount = 0; mycount < 40000; mycount++)
            {
                string[] a = new string[9];
                System.Random r = new System.Random();
                int rnd = r.Next(46656);
                a[0] = mylist[rnd];

                List<string> mylist2 = mylist.Where(c => hantei(a[0],c)).ToList();

                System.Random r2 = new System.Random();
                rnd = r2.Next(mylist2.Count());
                a[1] = mylist2[rnd];

                List<string> mylist3 = mylist2.Where(c => hantei(a[1], c)).ToList();

                System.Random r3 = new System.Random();
                rnd = r3.Next(mylist3.Count());
                a[2] = mylist3[rnd];

                List<string> mylist4 = mylist3.Where(c => hantei(a[2], c)).ToList();

                b = Try(a, mylist4);
                
                for (int i = 0; i < 9; i++)
                {
                    for (int ii = 0; ii < 9; ii++)
                    {
                        int position = start_position[ii] + next_position[(int)char.GetNumericValue(b[i][ii])];
                        kazu[position] = i + 1;
                    }
                }
                string sdData = string.Join("", kazu);
                result.Add(sdData);
            }
            
            System.IO.File.WriteAllLines(@"sudoku_answer.txt", result);

            sw.Stop();
            Console.WriteLine(sw.Elapsed.ToString());
            Console.WriteLine("finish...");
            Console.ReadLine();
        }
        static bool hantei(string x, string y)
        {
            for(int i = 0; i < 9; i++)
            {
                if (x[i] == y[i])
                {
                    return false;
                }
            }
            return true;
        }
        static string[] Try(string[] a, List<string> mylist)
        {
            //0(空欄)を探す→存在しない場合には-1を返す
            int blank = Array.IndexOf(a, null);
            if (blank != -1)
            {
                var ary = Enumerable.Range(0, mylist.Count()).ToArray();
                int[] ary2 = ary.OrderBy(t => Guid.NewGuid()).ToArray();

                for (int i = 0; i < mylist.Count(); i++)
                {   
                    if (isOK(blank, mylist[ary2[i]], a))
                    {
                        a[blank] = mylist[ary2[i]];
                        Try(a, mylist);
                        int blank2 = Array.IndexOf(a, null);
                        if (blank2 == -1)
                        {
                            break;
                        }
                        a[blank] = null;
                    }
                }
            }
            return a;
        }
        static bool isOK(int x, string L, string[] a)
        {
            for(int i = 0; i < x; i++)
            {
                for (int indx = 0; indx < 9; indx++)
                {
                    if (L[indx] == a[i][indx])
                    {
                        return false;
                    }
                }
            }
            return true;
        }
    }
}
  1. まず一つ目をランダムに選択
  2. その後選択できるリストを絞り込む
  3. 二つ目をランダムに選択
  4. 再度選択できるリストを絞り込む
  5. 3つ目をランダムに選択
  6. 再再度選択できるリストを絞り込む
  7. 残りの6つはバックトラック法で選択
  8. 最初に戻り同様のことを繰り返す

ただし、通常のバックトラック法ではすべての解を見つけてしまうため、ここでは1つの解が見つかった時点で多重ループを抜けるように工夫してある。
以下の環境で40000個作るのに14分かかった。速いのか遅いのか?

Windows 10 Pro
Visual Studio 2017
Intel(R) Core(TM) i7-4600U CPU @2.10GHz 2.69GHz
RAM:8.0GB

MXNet 備忘録(2)

学習の基本的書き方

最近この本を愛読している

MXNetで作る データ分析AIプログラミング入門

MXNetで作る データ分析AIプログラミング入門

この本では機械学習には以下のような書き方がなされている

trainer = gluon.Trainer(model.collect_params(), 'adam')
loss_func = gluon.loss.SoftmaxCrossEntropyLoss()

print('start training...')
batch_size = 100
epochs = 8
loss_n = [] #ログ表示用

for epoch in range(1, epochs + 1):
    #ランダムに並べ替えたインデックスを作成
    indexs = np.random.permutation(X.shape[0])
    cur_start = 0
    while cur_start < X.shape[0]:
        cur_end = (cur_start + batch_size) if (cur_start + batch_size) < X.shape[0] else X.shape[0]
        data = X[indexs[cur_start:cur_end]]
        label = Y[indexs[cur_start:cur_end]]
        #ニューラルネットワークの順伝播
        with autograd.record():
            output = model(data)
            #損失を求める
            loss = loss_func(output, label)
            #ログ表示用に損失の値を保存
            loss_n.append(np.mean(loss.asnumpy()))
        #損失の値から逆伝播する
        loss.backward()
        #学習ステータスをデータサイズ分進める
        trainer.step(data.shape[0], ignore_stale_grad = True)
        cur_start = cur_end
    #ログを表示
    ll = np.mean(loss_n)
    print('%d epoch loss = %f' %(epoch, ll))
    loss_n = []

「MXNet Gluon」での基本的な書き方であるが、おそらく「loss.backward()」で勾配を求め、「trainer.step(データサイズ、ignore_stale_grad = True/False)」で実際にパラメータを更新していると思われる。
(間違っていたらごめんなさい)
最初「ignore_stale_grad = True」の意味がわからなかったが上記の本を読みすすめるうちになんとなくわかったような気がする。
「loss.backward()」の際に勾配が更新されなかったlayer(順伝播の際に使用しなかったlayer)があれば、そのlayerのパラメータを更新しないようにしているようである。
「Stacked Autoencoders」の事前学習のような時には必ず「ignore_stale_grad = True」を指定する必要があるのではないか。
(なんども書きます、間違っていたらごめんなさい)

Anacondaやめました

Anacondaのメリット

  • Jupyter Notebookがついてくる
  • 仮想環境を作る時に多くのモジュールをインストールしてくれる

「conda install」はもともと全く使っていない(「pip install」で不自由ない)

conda install <モジュール名>

Anacondaやめてどうしたか?

  • VS Codeに乗り換えた
  • 仮想環境は「venv」

VS Codeの設定

以下を参考にさせて頂いた
www.atmarkit.co.jp
qiita.com

MXNet 備忘録

ネットワークの定義

「HybridSequential」「HybridBlock」を使わない一般的な方法

  • 単純な順伝播型ネットワーク(分岐などがない)
from mxnet.gluon import nn

def Model():
    model = nn.Sequential()
    with model.name_scope():
        model.add(....) 
        model.add(....) 
        ....
        ....
    return model
  • 複雑なネットワーク(分岐などがある)
from mxnet.gluon import Block, nn

class Model(Block):
    def __init__(self, **kwargs):
        super(Model, self).__init__(**kwargs)
        with self.name_scope():
            self.embed = nn.Embedding(3,3) #例
            ....
            ....

	def forward(self, x):
            out = self.embed(x) #例
            ....
            ....		
            return out

モデルの初期化

#2つの書き方が存在する
model.initialize()
model.collect_params().initialize()

Gluon Package — mxnet documentationにはこのように書かれている

'initialize' initializes Parameters of this Block and its children. 
Equivalent to block.collect_params().initialize(...)

どちらでもいいらしい

「hybrid_forward」に出てくる「F」とは?

class Model(gluon.HybridBlock):
    def __init__(self, **kwargs):
        super(Model, self).__init__(**kwargs)
        
    def hybrid_forward(self, F, x):
        # F is a function space that depends on the type of x
        # If x's type is NDArray, then F will be mxnet.nd
        # If x's type is Symbol, then F will be mxnet.sym

mxnet-cu**について

Install a different MXNet package — Gluon Crash Course 0.2 documentation
ここにはこのように記載されている

All cu packages ship cudnn in default, there is no need to install it separately.

cuDNNをインストールしなくて良いってこと?
これ本当?

MXNetで作る データ分析AIプログラミング入門

MXNetで作る データ分析AIプログラミング入門

最近この本を読んでいるけど、GPUを使う場合にはcuDNNをインストールするようにと書かれている。