【C#】ルービックキューブの最短解を求めたい PythonからC#へ

はじめに

ルービックキューブを解くプログラムを書いてみよう(前編:キューブを操る実装) - Qiita
ルービックキューブを解くプログラムを書いてみよう(中編:IDA*探索) - Qiita
ルービックキューブを解くプログラムを書いてみよう(後編:状態のindex化, Two-Phase-Algorithm) - Qiita
こちらの記事を参考にしてルービックキューブの「最短解」を求める試みをやってきました。結果的には無理だったんですが。
touch-sp.hatenablog.com
touch-sp.hatenablog.com
PythonをC#に変えたら少しは速くなるのか？興味があったので試してみることにしました。C#はすらすらコードが書けないのでゆっくり進めていく予定です。どこかで行き詰るかもしれません。

コード

cpをインデックス化して遷移表を作り保存する

using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;

namespace make_cp_move_table
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] move_names = { "U", "U2", "U'", "D", "D2", "D'", "L", "L2", "L'", "R", "R2", "R'", "F", "F2", "F'", "B", "B2", "B'" };

            var move_dict = new Dictionary<int, int[]>()
            {
                {0,  new int[]{ 3, 0, 1, 2, 4, 5, 6, 7} },
                {1,  new int[]{ 2, 3, 0, 1, 4, 5, 6, 7} },
                {2,  new int[]{ 1, 2, 3, 0, 4, 5, 6, 7} },
                {3,  new int[]{ 0, 1, 2, 3, 5, 6, 7, 4} },
                {4,  new int[]{ 0, 1, 2, 3, 6, 7, 4, 5} },
                {5,  new int[]{ 0, 1, 2, 3, 7, 4, 5, 6} },
                {6,  new int[]{ 4, 1, 2, 0, 7, 5, 6, 3} },
                {7,  new int[]{ 7, 1, 2, 4, 3, 5, 6, 0} },
                {8,  new int[]{ 3, 1, 2, 7, 0, 5, 6, 4} },
                {9,  new int[]{ 0, 2, 6, 3, 4, 1, 5, 7} },
                {10, new int[]{ 0, 6, 5, 3, 4, 2, 1, 7} },
                {11, new int[]{ 0, 5, 1, 3, 4, 6, 2, 7} },
                {12, new int[]{ 0, 1, 3, 7, 4, 5, 2, 6} },
                {13, new int[]{ 0, 1, 7, 6, 4, 5, 3, 2} },
                {14, new int[]{ 0, 1, 6, 2, 4, 5, 7, 3} },
                {15, new int[]{ 1, 5, 2, 3, 0, 4, 6, 7} },
                {16, new int[]{ 5, 4, 2, 3, 1, 0, 6, 7} },
                {17, new int[]{ 4, 0, 2, 3, 5, 1, 6, 7} }
            };

            int cp_to_index(int[] cp)
            {
                int index = 0;
                for (int i = 0; i < 8; i++)
                {
                    index *= 8 - i;
                    for (int j = i + 1; j < 8; j++)
                    {
                        if (cp[i] > cp[j]) index += 1;
                    }
                }
                return index;
            }

            int[] index_to_cp(int x)
            {
                int[] cp = new int[8];
                for (int i = 6; i > -1; i -= 1)
                {
                    cp[i] = x % (8 - i);
                    x /= (8 - i);
                    for (int j = i + 1; j < 8; j++)
                    {
                        if (cp[j] >= cp[i]) cp[j] += 1;
                    }
                }
                return cp;
            }

            int[,] cp_move_table = new int[40320, 18];

            for (int i = 0; i < 40320; i++)
            {
                int[] cp_before_move = index_to_cp(i);
                for (int move_num = 0; move_num < 18; move_num++)
                {
                    int[] cp_after_move = move_dict[move_num].Select(x => cp_before_move[x]).ToArray();
                    cp_move_table[i, move_num] = cp_to_index(cp_after_move);
                }
            }

            using (FileStream fs = new FileStream("cp_move_table.data", FileMode.Create))
            {
                BinaryFormatter bf = new BinaryFormatter();
                bf.Serialize(fs, cp_move_table);
            }
        }
    }
}

保存したデータは下記で読み込めます。PythonでいうPickleのような使い方です。

string path = "cp_move_table.data";

int[,] cp_move_table;

using (FileStream fs = new FileStream(path, FileMode.Open))
{
    BinaryFormatter bf = new BinaryFormatter();
    cp_move_table = (int[,])bf.Deserialize(fs);
}

coをインデックス化して遷移表を作り保存する

using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;

namespace make_co_move_table
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] move_names = { "U", "U2", "U'", "D", "D2", "D'", "L", "L2", "L'", "R", "R2", "R'", "F", "F2", "F'", "B", "B2", "B'" };

            var cp_move_dict = new Dictionary<int, int[]>()
            {
                {0,  new int[]{ 3, 0, 1, 2, 4, 5, 6, 7} },
                {1,  new int[]{ 2, 3, 0, 1, 4, 5, 6, 7} },
                {2,  new int[]{ 1, 2, 3, 0, 4, 5, 6, 7} },
                {3,  new int[]{ 0, 1, 2, 3, 5, 6, 7, 4} },
                {4,  new int[]{ 0, 1, 2, 3, 6, 7, 4, 5} },
                {5,  new int[]{ 0, 1, 2, 3, 7, 4, 5, 6} },
                {6,  new int[]{ 4, 1, 2, 0, 7, 5, 6, 3} },
                {7,  new int[]{ 7, 1, 2, 4, 3, 5, 6, 0} },
                {8,  new int[]{ 3, 1, 2, 7, 0, 5, 6, 4} },
                {9,  new int[]{ 0, 2, 6, 3, 4, 1, 5, 7} },
                {10, new int[]{ 0, 6, 5, 3, 4, 2, 1, 7} },
                {11, new int[]{ 0, 5, 1, 3, 4, 6, 2, 7} },
                {12, new int[]{ 0, 1, 3, 7, 4, 5, 2, 6} },
                {13, new int[]{ 0, 1, 7, 6, 4, 5, 3, 2} },
                {14, new int[]{ 0, 1, 6, 2, 4, 5, 7, 3} },
                {15, new int[]{ 1, 5, 2, 3, 0, 4, 6, 7} },
                {16, new int[]{ 5, 4, 2, 3, 1, 0, 6, 7} },
                {17, new int[]{ 4, 0, 2, 3, 5, 1, 6, 7} }
            };

            var co_move_dict = new Dictionary<int, int[]>()
            {
                {0,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {1,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {2,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {3,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {4,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {5,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {6,  new int[]{ 2, 0, 0, 1, 1, 0, 0, 2} },
                {7,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {8,  new int[]{ 2, 0, 0, 1, 1, 0, 0, 2} },
                {9,  new int[]{ 0, 1, 2, 0, 0, 2, 1, 0} },
                {10, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {11, new int[]{ 0, 1, 2, 0, 0, 2, 1, 0} },
                {12, new int[]{ 0, 0, 1, 2, 0, 0, 2, 1} },
                {13, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {14, new int[]{ 0, 0, 1, 2, 0, 0, 2, 1} },
                {15, new int[]{ 1, 2, 0, 0, 2, 1, 0, 0} },
                {16, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0} },
                {17, new int[]{ 1, 2, 0, 0, 2, 1, 0, 0} }
            };

            int co_to_index(int[] x)
            {
                int index = 0;
                foreach(int co_i in x.Take(x.Length - 1))
                {
                    index *= 3;
                    index += co_i;
                }
                return index;
            }

            int[] index_to_co(int x)
            {
                int[] co = new int[8];
                int sum_co = 0;
                for (int i = 6; i > -1; i -= 1)
                {
                    co[i] = x % 3;
                    x /= 3;
                    sum_co += co[i];
                }
                co[7] = (3 - sum_co % 3) % 3;
                return co;
            }

            int[,] co_move_table = new int[2187, 18];

            for (int i = 0; i < 2187; i++)
            {
                int[] co_before_move = index_to_co(i);
                for (int move_num = 0; move_num < 18; move_num++)
                {
                    int[] co_after_move = cp_move_dict[move_num].Select((value, index) => (co_before_move[value] + co_move_dict[move_num][index]) % 3).ToArray();
                    co_move_table[i, move_num] = co_to_index(co_after_move);
                }
            }
            using (FileStream fs = new FileStream("co_move_table.data", FileMode.Create))
            {
                BinaryFormatter bf = new BinaryFormatter();
                bf.Serialize(fs, co_move_table);
            }
        }
    }
}

eoをインデックス化して遷移表を作り保存する

using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Runtime.Serialization.Formatters.Binary;

namespace make_eo_move_table
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] move_names = { "U", "U2", "U'", "D", "D2", "D'", "L", "L2", "L'", "R", "R2", "R'", "F", "F2", "F'", "B", "B2", "B'" };

            var ep_move_dict = new Dictionary<int, int[]>()
            {
                {0,  new int[]{ 0, 1, 2, 3, 7, 4, 5, 6, 8, 9, 10, 11 } },
                {1,  new int[]{ 0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 11 } },
                {2,  new int[]{ 0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10, 11 } },
                {3,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8 } },
                {4,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9 } },
                {5,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 11, 8, 9, 10 } },
                {6,  new int[]{ 11, 1, 2, 7, 4, 5, 6, 0, 8, 9, 10, 3 } },
                {7,  new int[]{ 3, 1, 2, 0, 4, 5, 6, 11, 8, 9, 10, 7 } },
                {8,  new int[]{ 7, 1, 2, 11, 4, 5, 6, 3, 8, 9, 10, 0 } },
                {9,  new int[]{ 0, 5, 9, 3, 4, 2, 6, 7, 8, 1, 10, 11 } },
                {10, new int[]{ 0, 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 11 } },
                {11, new int[]{ 0, 9, 5, 3, 4, 1, 6, 7, 8, 2, 10, 11 } },
                {12, new int[]{ 0, 1, 6, 10, 4, 5, 3, 7, 8, 9, 2, 11 } },
                {13, new int[]{ 0, 1, 3, 2, 4, 5, 10, 7, 8, 9, 6, 11 } },
                {14, new int[]{ 0, 1, 10, 6, 4, 5, 2, 7, 8, 9, 3, 11 } },
                {15, new int[]{ 4, 8, 2, 3, 1, 5, 6, 7, 0, 9, 10, 11 } },
                {16, new int[]{ 1, 0, 2, 3, 8, 5, 6, 7, 4, 9, 10, 11 } },
                {17, new int[]{ 8, 4, 2, 3, 0, 5, 6, 7, 1, 9, 10, 11 } }
            };

            var eo_move_dict = new Dictionary<int, int[]>()
            {
                {0,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {1,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {2,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {3,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {4,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {5,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {6,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {7,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {8,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {9,  new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {10, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {11, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {12, new int[]{ 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0 } },
                {13, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {14, new int[]{ 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0 } },
                {15, new int[]{ 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 } },
                {16, new int[]{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } },
                {17, new int[]{ 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0 } }
            };

            int eo_to_index(int[] x)
            {
                int index = 0;
                foreach (int eo_i in x.Take(x.Length - 1))
                {
                    index *= 2;
                    index += eo_i;
                }
                return index;
            }

            int[] index_to_eo(int x)
            {
                int[] eo = new int[12];
                int sum_eo = 0;
                for(int i = 10; i > -1; i -= 1)
                {
                    eo[i] = x % 2;
                    x /= 2;
                    sum_eo += eo[i];
                }
                eo[11] = (2 - sum_eo % 2) % 2;
                return eo;
            }

            int[,] eo_move_table = new int[2048, 18];

            for(int i = 0; i < 2048; i++)
            {
                int[] eo_before_move = index_to_eo(i);
                for(int move_num = 0; move_num < 18; move_num++)
                {
                    //new_eo = [(self.eo[p] + move.eo[i]) % 2 for i, p in enumerate(move.ep)]
                    int[] eo_after_move = ep_move_dict[move_num].Select((value, index) => (eo_before_move[value] + eo_move_dict[move_num][index]) % 2).ToArray();
                    eo_move_table[i, move_num] = eo_to_index(eo_after_move);
                }
            }

            using (FileStream fs = new FileStream("eo_move_table.data", FileMode.Create))
            {
                BinaryFormatter bf = new BinaryFormatter();
                bf.Serialize(fs, eo_move_table);
            }
        }
    }
}

状態を表すクラスを作る

まずは先に保存した遷移表などがグローバル変数風に使えるようにGlobalクラスを作りました。

Globalクラス

using System.Collections.Generic;

public static class Global
{
    public static int[,] cp_move_table;
    public static int[,] co_move_table;
    public static int[,] eo_move_table;
    public static Dictionary<int, int[]> ep_move_dict = new Dictionary<int, int[]>()
        {
            {0,  new int[]{ 0, 1, 2, 3, 7, 4, 5, 6, 8, 9, 10, 11 } },
            {1,  new int[]{ 0, 1, 2, 3, 6, 7, 4, 5, 8, 9, 10, 11 } },
            {2,  new int[]{ 0, 1, 2, 3, 5, 6, 7, 4, 8, 9, 10, 11 } },
            {3,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 8 } },
            {4,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 10, 11, 8, 9 } },
            {5,  new int[]{ 0, 1, 2, 3, 4, 5, 6, 7, 11, 8, 9, 10 } },
            {6,  new int[]{ 11, 1, 2, 7, 4, 5, 6, 0, 8, 9, 10, 3 } },
            {7,  new int[]{ 3, 1, 2, 0, 4, 5, 6, 11, 8, 9, 10, 7 } },
            {8,  new int[]{ 7, 1, 2, 11, 4, 5, 6, 3, 8, 9, 10, 0 } },
            {9,  new int[]{ 0, 5, 9, 3, 4, 2, 6, 7, 8, 1, 10, 11 } },
            {10, new int[]{ 0, 2, 1, 3, 4, 9, 6, 7, 8, 5, 10, 11 } },
            {11, new int[]{ 0, 9, 5, 3, 4, 1, 6, 7, 8, 2, 10, 11 } },
            {12, new int[]{ 0, 1, 6, 10, 4, 5, 3, 7, 8, 9, 2, 11 } },
            {13, new int[]{ 0, 1, 3, 2, 4, 5, 10, 7, 8, 9, 6, 11 } },
            {14, new int[]{ 0, 1, 10, 6, 4, 5, 2, 7, 8, 9, 3, 11 } },
            {15, new int[]{ 4, 8, 2, 3, 1, 5, 6, 7, 0, 9, 10, 11 } },
            {16, new int[]{ 1, 0, 2, 3, 8, 5, 6, 7, 4, 9, 10, 11 } },
            {17, new int[]{ 8, 4, 2, 3, 0, 5, 6, 7, 1, 9, 10, 11 } }
        };
}

コードの最初で保存したデータを読み込めばそれ以降はグローバル変数風に使用可能になります。

int[,] read_move_table(string path)
{
    using (FileStream fs = new FileStream(path, FileMode.Open))
    {
        BinaryFormatter bf = new BinaryFormatter();
        return (int[,])bf.Deserialize(fs);
    }
}

Global.cp_move_table = read_move_table("cp_move_table.data");
Global.co_move_table = read_move_table("co_move_table.data");
Global.eo_move_table = read_move_table("eo_move_table.data");

これで次に作成するStateクラス内でも使用可能です。

Stateクラス

using System.Linq;

class State
{
    public int cp;
    public int co;
    public int[] ep;
    public int eo;

    public State(int cp, int co, int[] ep, int eo)
    {
        this.cp = cp;
        this.co = co;
        this.ep = ep;
        this.eo = eo;
    }
    public State apply_move(int move_num)
    {
        int new_cp = Global.cp_move_table[this.cp, move_num];
        int new_co = Global.co_move_table[this.co, move_num];
        int new_eo = Global.eo_move_table[this.eo, move_num];
        int[] new_ep = Global.ep_move_dict[move_num].Select(x => this.ep[x]).ToArray();
        return new State(new_cp, new_co, new_ep, new_eo);
    }
}

（注）epだけは組み合わせが多く遷移表を作成していません。

完成を判定する関数を作る

bool is_solved(State q_state)
{
    return (q_state.cp == 0 && q_state.co == 0 && q_state.ep.SequenceEqual(Enumerable.Range(0, 12).ToArray()) && q_state.eo == 0);
}

次の1手の可否を決定する関数を作る

bool is_move_available(int pre, int now)
{
    if (pre == -1) return true;
    if (pre / 3 == now / 3) return false;
    if (pre / 3 == 0 && now / 3 == 1) return false; //U→Dはダメ
    if (pre / 3 == 3 && now / 3 == 2) return false; //R→Lはダメ
    if (pre / 3 == 4 && now / 3 == 5) return false; //F→Bはダメ
    return true;
}

いよいよ実行

using System;
using System.Collections.Generic;
using System.IO;
using System.Runtime.Serialization.Formatters.Binary;
using System.Linq;
using System.Diagnostics;

namespace cube_solver
{
    class Program
    {
        static void Main(string[] args)
        {
            int[,] read_move_table(string path)
            {
                using (FileStream fs = new FileStream(path, FileMode.Open))
                {
                    BinaryFormatter bf = new BinaryFormatter();
                    return (int[,])bf.Deserialize(fs);
                }
            }

            Global.cp_move_table = read_move_table("cp_move_table.data");
            Global.co_move_table = read_move_table("co_move_table.data");
            Global.eo_move_table = read_move_table("eo_move_table.data");

            string[] move_names = { "U", "U2", "U'", "D", "D2", "D'", "L", "L2", "L'", "R", "R2", "R'", "F", "F2", "F'", "B", "B2", "B'" };

            bool is_move_available(int pre, int now)
            {
                if (pre == -1) return true;
                if (pre / 3 == now / 3) return false;
                if (pre / 3 == 0 && now / 3 == 1) return false; //U→Dはダメ
                if (pre / 3 == 3 && now / 3 == 2) return false; //R→Lはダメ
                if (pre / 3 == 4 && now / 3 == 5) return false; //F→Bはダメ
                return true;
            }

            bool is_solved(State q_state)
            {
                return (q_state.cp == 0 && q_state.co == 0 && q_state.ep.SequenceEqual(Enumerable.Range(0, 12).ToArray()) && q_state.eo == 0);
            }

            List<int> current_solution = new List<int> { -1 };


            bool depth_limited_search(State q_state, int depth)
            {
                if (depth == 0 && is_solved(q_state))
                {
                    return true;
                }
                if (depth == 0)
                {
                    return false;
                }

                int prev_move = current_solution.Last();
                for (int move_num = 0; move_num < 18; move_num++)
                {
                    if (!(is_move_available(prev_move, move_num))) continue;
                    current_solution.Add(move_num);
                    if (depth_limited_search(q_state.apply_move(move_num), depth - 1)) return true;
                    current_solution.RemoveAt(current_solution.Count - 1);
                }
                return false;
            }

            string scramble = "R' U' F R' B' F2 L2 D'";

            State scramble2state(string scramble)
            {
                State start_state = new State(0, 0, Enumerable.Range(0, 12).ToArray(), 0);
                int[] moves = scramble.Split(" ").Select(x => Array.IndexOf(move_names, x)).ToArray();
                foreach (int each_move in moves)
                {
                    start_state = start_state.apply_move(each_move);
                }
                return start_state;
            }

            State scrambled_state = scramble2state(scramble);

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

            for (int depth = 0; depth < 21; depth++)
            {
                Console.WriteLine("Start searching lenght {0}", depth);
                if (depth_limited_search(scrambled_state, depth)) break;
            }
            current_solution.RemoveAt(0);

            sw.Stop();
            TimeSpan ts = sw.Elapsed;

            Console.WriteLine("finished!({0})", ts);
            Console.WriteLine(string.Join(" ", current_solution.Select(x => move_names[x])));

            Console.ReadKey();
        }
    }
}

結果

Start searching lenght 0
Start searching lenght 1
Start searching lenght 2
Start searching lenght 3
Start searching lenght 4
Start searching lenght 5
Start searching lenght 6
Start searching lenght 7
Start searching lenght 8
finished!(00:00:50.1692662)
D L2 B F2 R F' U R

約1分で8手の問題が解けました。
枝刈りのコードは全く書いていないので総当たりの検索です。これから改良していきたいと考えています。

動作環境

ASRock DeskMini H470
CPU: Core i7 11700
メモリ：16G 2666MHz

最後に

続きを別記事に書きました。
touch-sp.hatenablog.com