A quick 'n' dirty solver for Eliza's Kabufuda Solitaire

KabufudaSolver.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KabufudaSolver {
    class Program {
        static void Main(string[] args) {
            Board board = new Board(Console.ReadLine(), int.Parse(Console.ReadLine()));
            Console.WriteLine(string.Join("\n", board.GetAllChildren()));
            Console.WriteLine();
            Dictionary<string, string> parents = new Dictionary<string, string>();
            // DFS finds an ugly solution fast. You can use a Queue on the expert difficulty, since it has lower branching factor.
            Stack<Board> queue = new Stack<Board>();
            queue.Push(board);
            String win = null;
            while (queue.Count > 0) {
                Board current = queue.Pop();
                foreach (Board child in current.GetAllChildren()) {
                    if (parents.ContainsKey(child.ToString())) {
                        continue;
                    }
                    parents.Add(child.ToString(), current.ToString());
                    if (child.IsWon()) {
                        win = child.ToString();
                        break;
                    }
                    queue.Push(child);
                }
                if (win != null) {
                    break;
                }
            }
            if (win == null) {
                Console.WriteLine("Game is unwinnable.");
                Console.ReadLine();
                return;
            }
            Stack<string> moves = new Stack<string>();
            while (parents.ContainsKey(win)) {
                moves.Push(win);
                win = parents[win];
            }
            while (moves.Count > 0) {
                Console.WriteLine(moves.Pop());
            }
            Console.ReadLine();
        }
    }

    class Board {
        List<char>[] stacks;
        List<char> freecells;

        public Board(string board, int numFree) {
            stacks = new List<char>[8];
            for (int i = 0; i < 8; i++) {
                stacks[i] = new List<char>();
                for (int j = 0; j < 5; j++) {
                    int stringIndex = i * 5 + j;
                    stacks[i].Add(board[stringIndex]);
                }
            }
            freecells = new List<char>();
            for (int i = 0; i < 4; i++) {
                if (i < numFree) {
                    freecells.Add(' ');
                } else {
                    freecells.Add('X');
                }
            }
        }
        public Board(Board other) {
            stacks = new List<char>[8];
            for (int i = 0; i < 8; i++) {
                stacks[i] = new List<char>(other.stacks[i]);
            }
            freecells = new List<char>(other.freecells);
        }

        public List<Board> GetAllChildren() {
            List<Board> output = new List<Board>();
            // Move from stacks.
            for (int i = 0; i < 8; i++) {
                bool putOntoEmpty = false;
                if (stacks[i].Count == 0) {
                    continue;
                }
                if (StackIsDone(i)) {
                    continue;
                }
                int index = stacks[i].Count - 1;
                int num = 1;
                while (index > 0 && stacks[i][index] == stacks[i][index - 1]) {
                    index--;
                    num++;
                }
                // On to another stack.
                for (int j = 0; j < 8; j++) {
                    if (j == i) {
                        continue;
                    }
                    if (StackIsDone(j)) {
                        continue;
                    }
                    if (stacks[j].Count == 0 && putOntoEmpty) {
                        continue;
                    }
                    int otherCount = stacks[j].Count;
                    if (otherCount > 0 && stacks[j][otherCount - 1] != stacks[i][index]) {
                        continue;
                    }
                    Board copy = new Board(this);
                    copy.stacks[j].AddRange(stacks[i].GetRange(index, stacks[i].Count - index));
                    copy.stacks[i].RemoveRange(index, stacks[i].Count - index);
                    if (copy.stacks[j].Count == 4 && copy.stacks[j][0] == copy.stacks[j][1]
                                                  && copy.stacks[j][0] == copy.stacks[j][2]
                                                  && copy.stacks[j][0] == copy.stacks[j][3]) {
                        copy.stacks[j].Clear();
                        copy.stacks[j].Add('!');
                        if (freecells.Count > 0 && freecells[freecells.Count - 1] == 'X') {
                            copy.freecells.RemoveAt(freecells.Count - 1);
                            copy.freecells.Insert(0, ' ');
                        }
                    }
                    output.Add(copy);
                    if (stacks[j].Count == 0) {
                        putOntoEmpty = true;
                    }
                    // Note that this does not allow moving fewer than the max.
                }
                // On to a freecell.
                for (int j = 0; j < freecells.Count; j++) {
                    if (num == 3 && stacks[i][index] == freecells[j]) {
                        Board copy = new Board(this);
                        copy.stacks[i].RemoveRange(index, stacks[i].Count - index);
                        copy.freecells.RemoveAt(j);
                        output.Add(copy);
                    } else if (freecells[j] == ' ' && !putOntoEmpty) {
                        Board copy = new Board(this);
                        copy.freecells[j] = stacks[i][index];
                        copy.stacks[i].RemoveAt(stacks[i].Count - 1);
                        output.Add(copy);
                        putOntoEmpty = true;
                    }
                }
            }
            // Move from a freecell.
            for (int i = 0; i < freecells.Count; i++) {
                if (freecells[i] == ' ') {
                    continue;
                } else if (freecells[i] == 'X') {
                    continue;
                }
                // On to a stack.
                for (int j = 0; j < 8; j++) {
                    if (stacks[j].Count == 0) {
                        continue;
                    }
                    if (StackIsDone(j)) {
                        continue;
                    }
                    int otherCount = stacks[j].Count;
                    if (otherCount > 0 && stacks[j][otherCount - 1] != freecells[i]) {
                        continue;
                    }
                    Board copy = new Board(this);
                    copy.stacks[j].Add(freecells[i]);
                    copy.freecells[i] = ' ';
                    if (copy.stacks[j].Count == 4 && copy.stacks[j][0] == copy.stacks[j][1]
                                                  && copy.stacks[j][0] == copy.stacks[j][2]
                                                  && copy.stacks[j][0] == copy.stacks[j][3]) {
                        copy.stacks[j].Clear();
                        copy.stacks[j].Add('!');
                        if (freecells.Count > 0 && freecells[freecells.Count - 1] == 'X') {
                            copy.freecells.RemoveAt(freecells.Count - 1);
                            copy.freecells.Insert(0, ' ');
                        }
                    }
                    output.Add(copy);
                }
            }
            return output;
        }
        bool StackIsDone(int index) {
            return stacks[index].Count == 1 && stacks[index][0] == '!';
        }

        public bool IsWon() {
            foreach (var stack in stacks) {
                if (stack.Count > 1) {
                    return false;
                }
            }
            return true;
        }

        static StringBuilder sb = new StringBuilder();
        public override string ToString() {
            sb.Clear();
            for (int i = 0; i < 8; i++) {
                if (stacks[i].Count == 0 || StackIsDone(i)) {
                    continue;
                }
                if (sb.Length != 0) {
                    sb.Append('|');
                }
                foreach (char c in stacks[i]) {
                    sb.Append(c);
                }
            }
            sb.Append('|');
            foreach (char c in freecells) {
                if (c != ' ' && c != 'X') {
                    sb.Append(c);
                }
            }
            return sb.ToString();
        }
        public override int GetHashCode() {
            return ToString().GetHashCode();
        }
    }
}