一筆書きゲームのゴール可能なパターンをチェックするプログラム

SnakeTest.cs

using System.Collections;
using System.Collections.Generic;
using UnityEngine;
using NUnit.Framework;
using UnityEngine;
using UnityEngine.TestTools;


public class SnakeTest 
{
    struct Step
    {
        public Vector2Int Prev;
        public Vector2Int Dst;
        public byte OrigData;

        public Vector2Int Dir => Dst - Prev;

        public Step(Vector2Int prev, Vector2Int dst,byte dstData)
        {
            Prev = prev;
            Dst = dst;
            OrigData = dstData;
        }
    }

    class Map
    {
        int _width;
        int _height;
        byte[] _map;
        Vector2Int _current;

        public Vector2Int Current => _current;

        static Vector2Int[] _directions = new Vector2Int[]
        {
        new Vector2Int(1,0),
        new Vector2Int(-1,0),
        new Vector2Int(0,1),
        new Vector2Int(0,-1),
        };

        public char GetDirectionChar(Vector2Int dir)
        {
            if (dir == _directions[0]) return '右';
            if (dir == _directions[1]) return '左';
            if (dir == _directions[2]) return '下';
            if (dir == _directions[3]) return '上';
            return 'E';
        }

        public Map(int width,int height,byte[] map,Vector2Int cur)
        {
            _width = width;
            _height = height;
            _map = map;
            _current = cur;
        }

        public byte Get(Vector2Int p)
        {
            return _map[p.x + p.y * _width];
        }
        public void Set(Vector2Int p,byte value)
        {
            _map[p.x + p.y * _width] = value;
        }
        bool checkAllFill()
        {
    		for(int i=0;i<_map.Length;++i)
            {
                if (_map[i] == 0) return false;
            }
            return true;
        }

        bool IsInside(Vector2Int p)
        {
            if (p.x < 0) return false;
            if (p.x >= _width) return false;
            if (p.y < 0) return false;
            if (p.y >= _height) return false;
            return true;
        }

        public bool Do(Step step)
        {
            var isGoal = (Get(step.Dst) == 3);
            Set(step.Dst, 1);
            _current = step.Dst;
            return isGoal;
        }
        public void Undo(Step step)
        {
            Set(step.Dst, step.OrigData);
            _current = step.Prev;
        }

        public List<Step> MovableSteps()
        {
            var steps = new List<Step>();
            for (int i=0;i< _directions.Length; ++i)
            {
                var p = _current + _directions[i];
                if (IsInside(p))
                {
                    var d = Get(p);
                    if (d == 0)
                    {
                        steps.Add(new Step(_current,p,d));
                    }else if (d == 3)
                    {
                        // goal
                        if (checkAllFill())
                        {
                            steps.Add(new Step(_current, p,d));
                        }
                    }
                }
            }
            return steps;
        }
    }

    void checkNextLevel(Map map,Stack<Step> steps,ref int goalCount)
    {
        var list = map.MovableSteps();
        foreach(var s in list)
        {
            steps.Push(s);
            if (map.Do(s))
            {
                // ゴールまでの道筋
                string result = "";
                foreach(var r in steps)
                {
                    result = map.GetDirectionChar(r.Dir) + result;  // 逆順に足す
                }
                Debug.Log(result);

                ++goalCount;
            }
            checkNextLevel(map, steps, ref goalCount);
            map.Undo(s);
            steps.Pop();
        }
    }

    Map[] _mapArray = new Map[]
    {
        // 0
        new Map(6, 6, new byte[]
        {
            0,0,2,0,0,0,
            0,0,2,0,2,0,
            0,2,0,0,2,0,
            0,0,0,2,2,0,
            2,2,0,0,0,0,
            2,2,0,0,0,3,
        }, Vector2Int.zero),
        // 1
        new Map(6, 6, new byte[]
        {
            0,0,0,2,0,0,
            0,0,0,2,0,0,
            0,2,0,0,0,0,
            0,2,0,0,2,0,
            0,2,0,0,2,0,
            0,0,0,2,2,3,
        }, Vector2Int.zero),
        // 2
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,0,
            2,2,0,0,2,0,
            0,0,2,2,2,0,
            0,0,0,0,0,0,
            0,2,2,2,2,2,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 3
        new Map(6, 6, new byte[]
        {
            0,0,2,0,0,0,
            0,0,0,0,0,0,
            0,2,0,0,0,2,
            0,0,2,0,0,0,
            0,0,0,0,0,0,
            0,0,0,2,0,3,
        }, Vector2Int.zero),
        // 4
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,0,
            0,0,0,0,2,0,
            0,0,2,0,0,0,
            2,0,0,2,2,2,
            0,0,0,2,0,0,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 5
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,2,
            0,0,2,0,0,2,
            0,0,2,0,0,0,
            0,0,0,2,2,0,
            0,2,0,0,2,0,
            0,0,0,0,2,3,
        }, Vector2Int.zero),
        // 6
        new Map(6, 6, new byte[]
        {
            0,0,0,0,2,2,
            0,0,2,0,0,2,
            0,0,0,0,0,0,
            2,0,0,0,0,0,
            0,0,0,0,0,2,
            0,0,0,2,0,3,
        }, Vector2Int.zero),
        // 7
        new Map(6, 6, new byte[]
        {
            0,2,0,0,0,0,
            0,0,0,2,2,0,
            2,2,0,0,2,0,
            0,0,0,0,0,0,
            0,2,0,0,0,0,
            0,0,0,2,2,3,
        }, Vector2Int.zero),
        // 8
        new Map(6, 6, new byte[]
        {
            0,0,2,0,0,0,
            0,0,0,0,2,0,
            0,2,0,0,0,0,
            0,2,2,0,0,2,
            0,0,0,0,0,2,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 9
        new Map(6, 6, new byte[]
        {
            0,0,2,0,0,0,
            0,0,0,0,2,0,
            0,2,0,0,0,0,
            0,2,2,0,0,2,
            0,0,0,0,0,2,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 10
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,2,
            0,0,0,2,0,2,
            0,2,0,0,0,0,
            0,2,2,0,0,0,
            0,2,0,0,2,2,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 11
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,2,
            0,0,0,0,0,0,
            0,0,0,2,2,0,
            0,2,0,0,2,0,
            0,0,0,0,0,0,
            2,0,0,2,0,3,
        }, Vector2Int.zero),
        // 12
        new Map(6, 6, new byte[]
        {
            0,0,0,0,0,0,
            0,0,0,2,0,0,
            0,2,0,0,0,2,
            0,2,2,2,0,0,
            0,0,0,0,0,0,
            0,0,2,0,0,3,
        }, Vector2Int.zero),
        // 13
        new Map(6, 6, new byte[]
        {
            0,2,0,0,0,0,
            0,0,0,0,0,0,
            2,0,0,2,2,0,
            0,0,2,0,0,0,
            0,0,0,0,2,2,
            0,0,0,0,0,3,
        }, Vector2Int.zero),
        // 14
        new Map(6, 6, new byte[]
        {
            0,0,2,0,0,0,
            0,0,2,0,2,0,
            0,2,0,0,0,0,
            0,0,0,2,0,0,
            0,0,2,0,0,0,
            0,0,2,0,0,3,
        }, Vector2Int.zero),
    };

    [Test]
    public void SnakeCheck()
    {
        for(int idMap=0;idMap<_mapArray.Length;++idMap)
        {
            var map = _mapArray[idMap];
            Debug.Log("==================" + idMap);
            map.Set(map.Current, 1);    // 最初の位置を埋めておく
            int goalCount = 0;
            var steps = new Stack<Step>();
            checkNextLevel(map, steps, ref goalCount);
            Debug.Log(goalCount);
        }
    }
}