<file_sep>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KenkenSolve
{

    abstract class Span//Collection of cells, may be a row, column or a group
    {
        public List<Cell> Cells = new List<Cell>();

        public int Goal;
        public char Character;
        public abstract bool isValid();
        public abstract void GenerateValids(Puzzle p);

        public HashSet<int> Valids;
        public bool ChangedSinceGeneration = true;

        public abstract char CharCode { get; }
    }

    class ConstantSpan : Span
    {
        public override bool isValid()
        {
            return true;//Constants are always valid
        }

        public override void GenerateValids(Puzzle p)//Not necessary for constants
        { }

        public override char CharCode { get { return 'c'; } }
    }

    class AddSpan : Span
    {
        public override bool isValid()
        {
            return Cells.Sum(c => c.Value) == Goal;
        }

        public override void GenerateValids(Puzzle p)
        {
            Valids = new HashSet<int>();
            var sequence = Enumerable.Range(1, p.Size);//Generate a sequence 1, 2, ... n

            //Find any integers that add from our current sum to some integer less than our goal
            int currentSum = Cells.Sum(c => c.Value);

            foreach (var i in sequence)
            {
                if (currentSum + i <= Goal)
                {
                    Valids.Add(i);
                }
            }
        }
        public override char CharCode { get { return '+'; } }
    }
    class SubtractSpan : Span
    {
        public override bool isValid()
        {
            return Cells[0].Value - Cells[1].Value == Goal || Cells[1].Value - Cells[0].Value == Goal;
        }

        public override void GenerateValids(Puzzle p)
        {
            Valids = new HashSet<int>();
            var sequence = Enumerable.Range(1, p.Size);//Generate a sequence 1, 2, ... n

            foreach (var i in sequence)
            {
                foreach (var j in sequence)
                {
                    if (i - j == Goal || j - i == Goal)
                    {
                        Valids.Add(i);
                    }
                }
            }
        }
        public override char CharCode { get { return '-'; } }
    }
    class MultiplySpan : Span
    {
        public override bool isValid()
        {
            int product = 1;
            Cells.ForEach(c => product *= c.Value);

            return product == Goal;
        }

        public override void GenerateValids(Puzzle p)
        {
            Valids = new HashSet<int>();
            var sequence = Enumerable.Range(1, p.Size);//Generate a sequence 1, 2, ... n

            if (Cells.Count == 1)
            {
                Valids.Add(Goal / Cells[0].Value);
            }
            else
            {
                //Find any integers that will multiply to some integer less than our equal to our goal
                int currentProduct = 1;
                Cells.ForEach(c => currentProduct *= c.Value != 0 ? c.Value : 1);
                foreach (var i in sequence)
                {
                    if (currentProduct * i <= Goal)
                        Valids.Add(i);
                }
            }
        }
        public override char CharCode { get { return 'x'; } }
    }
    class DivideSpan : Span
    {
        public override bool isValid()
        {
            if (Cells[0].Value == 0 || Cells[1].Value == 0)
                return false;

            return Cells[0].Value / Cells[1].Value == Goal || Cells[1].Value / Cells[0].Value == Goal;
        }

        public override void GenerateValids(Puzzle p)
        {
            Valids = new HashSet<int>();
            var sequence = Enumerable.Range(1, p.Size);//Generate a sequence 1, 2, ... n


            foreach (var i in sequence)
            {
                foreach (var j in sequence)
                {
                    if (i / j == Goal || j / i == Goal)
                    {
                        Valids.Add(i);
                    }
                }
            }
        }
        public override char CharCode { get { return '/'; } }
    }

    class UniqueSpan : Span
    {
        public override bool isValid()
        {
            //Find the set difference between the sequence 1, 2 ... n and the row/column we have
            var difference = Cells.Select(c => c.Value).Except(Enumerable.Range(1, Goal));

            //If this has any values in it, it's not a valid row/column
            return !difference.Any();
        }

        public override void GenerateValids(Puzzle p)
        { }

        public override char CharCode { get { return ' '; } }
    }
}
<file_sep>﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KenkenSolve
{
    class Program
    {
        static void Main(string[] args)
        {
            Puzzle p = new Puzzle("game5.txt");


            p.Print(c => c.Group.Goal.ToString() + c.Group.CharCode);

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

            PuzzleSolve.Solve(p);

            s.Stop();
            Console.WriteLine(s.ElapsedMilliseconds);
            
            p.Print(c => c.Value.ToString());


            Console.WriteLine();

            Console.ReadKey();
        }
    }

}
<file_sep>﻿using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KenkenSolve
{
    class Puzzle
    {
        public Puzzle(string file)
        {
            string[] lines = File.ReadAllLines(file);

            Size = int.Parse(lines[0]);
            char[,] grid = new char[Size, Size];

            for (int y = 0; y < Size; y++)
            {
                string row = lines[1 + y];//Take a row from the game file
                for (int x = 0; x < Size; x++)
                    grid[x, y] = row[x];
            }

            for (int i = Size + 1; i < lines.Length; i++)
            {
                Span span;
                var pieces = lines[i].Split(';');

                switch (pieces[2][0])
                {
                    case '+':
                        span = new AddSpan();
                        break;
                    case '-':
                        span = new SubtractSpan();
                        break;
                    case 'x':
                        span = new MultiplySpan();
                        break;
                    case '/':
                        span = new DivideSpan();
                        break;
                    case 'c':
                        span = new ConstantSpan();
                        break;
                    default:
                        span = new AddSpan();
                        break;
                }

                span.Character = pieces[0][0];
                span.Goal = int.Parse(pieces[1]);

                Groups.Add(span);
            }

            for (int y = 0; y < Size; y++)
            {
                for (int x = 0; x < Size; x++)
                {
                    char c = grid[x, y];
                    Cell cell = new Cell();

                    cell.X = x;
                    cell.Y = y;

                    //build a bidirectional relationship between groups and cells
                    cell.Group = Groups.FirstOrDefault(g => g.Character == c);
                    cell.Group.Cells.Add(cell);

                    All.Add(cell);
                }
            }

            for (int i = 0; i < Size; i++)
            {
                Span column = new UniqueSpan { Cells = All.Where(c => c.X == i).ToList(), Goal = Size };
                Span row = new UniqueSpan { Cells = All.Where(c => c.Y == i).ToList(), Goal = Size };

                Columns.Add(column);
                Rows.Add(row);

                //build a bidirectional relationship between cells and columns/rows
                column.Cells.ForEach(c => c.Column = column);
                row.Cells.ForEach(c => c.Row = row);
            }

            All.ForEach(c=>c.Neighbours = getCellNeighbours(c));
        }

        static List<Cell> getCellNeighbours(Cell cell)
        {
            var neighbours = cell.Group.Cells.ToList();
            neighbours.AddRange(cell.Column.Cells);
            neighbours.AddRange(cell.Row.Cells);

            return neighbours.Where(c => !(c.Group is ConstantSpan) && c != cell).Distinct().ToList();
        }

        public List<Cell> All = new List<Cell>();

        public List<Span> Groups = new List<Span>();

        public List<Span> Columns = new List<Span>();
        public List<Span> Rows = new List<Span>();

        public int Size;

        //Tries to print the puzzle in a way that the original grid is visible, not perfect but works
        public void Print(Func<Cell, string> value)
        {
            foreach (var puzzleRow in Rows)
            {
                foreach (var cell in puzzleRow.Cells)
                {
                    Console.Write(value(cell).PadLeft(4, ' '));

                    int colI = puzzleRow.Cells.IndexOf(cell);
                    if (colI + 1 < puzzleRow.Cells.Count)//Check if we're at the end of the row
                    {
                        //If we're next to a neighbour of the same group, connect them on the same row
                        if (cell.Group == puzzleRow.Cells[colI + 1].Group)
                            Console.Write(" ");
                        else
                            Console.Write("|");
                    }

                }
                Console.WriteLine();

                int rowI = Rows.IndexOf(puzzleRow);
                if (rowI + 1 < Rows.Count)
                {
                    foreach (var cell in puzzleRow.Cells)
                    {
                        int colI = puzzleRow.Cells.IndexOf(cell);

                        //If we're next to a neighbour of the same group, connect them on the same column
                        if (cell.Group == Rows[rowI + 1].Cells[colI].Group)
                            Console.Write("     ");
                        else
                            Console.Write("-----");
                    }
                }
                Console.WriteLine();

            }
        }

    }

    class Cell
    {
        public Span Column;
        public Span Row;
        public Span Group;

        public int X;
        public int Y;

        public bool Busy = false;

        public int Value;

        public HashSet<int> PossibleValues = new HashSet<int>();

        public int PossibleValueCount = 0;

        public List<Cell> Neighbours = new List<Cell>();
    }


}
<file_sep>﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using MoreLinq;

namespace KenkenSolve
{
    class PuzzleSolve
    {
        public static void Solve(Puzzle puzzle)
        {
            initPuzzle(puzzle);

            puzzle.All.ForEach(c => updateCellPossibles(puzzle, c));

            solveCell(puzzle, puzzle.All.Where(p => p.PossibleValues.Any()).MinBy(p => p.PossibleValueCount));
        }


        private static int i = 0;
        static bool solveCell(Puzzle puzzle, Cell cell)
        {
            cell.Busy = true;//Set ourselves to 'busy' so we don't loop around in our search tree

            int initialValue = cell.Value;//Store our initial state so we can revert to it later if we need to
            HashSet<int> initialPossibleValues = cell.PossibleValues;

            foreach (var possibleValue in cell.PossibleValues)
            {
                cell.Value = possibleValue;
                i++;

                //Don't bother continuing if we just filled in a final cell of a group and it resulted in an invalid configuration
                if (cell.Group.Cells.All(c => c.Value != 0) && !cell.Group.isValid())
                    continue;

                if (isPuzzleValid(puzzle))
                    return true;//Did we just solve the puzzle? If so, return

                //Whenever we change our own value, we limit the possible values of all neighbours
                //Update these so we know where to go next
                foreach (var neighbour in cell.Neighbours)
                    updateCellPossibles(puzzle, neighbour);
                
                if (i % 50000 == 0)
                    showProgress(puzzle);

                Cell minNeighbour = null;
                int minNeighbourCount = int.MaxValue;

                foreach (var n in cell.Neighbours)
                {
                    if (!n.Busy && n.PossibleValueCount > 0)
                    {
                        if (n.PossibleValueCount < minNeighbourCount)
                        {
                            minNeighbourCount = n.PossibleValueCount;
                            minNeighbour = n;
                        }
                    }
                }
                //No valid neighbours? We've made a wrong choice earlier
                if (minNeighbour == null)
                    continue;


                //Continue expanding the recursive tree down into the valid neighbour with the least possible choices
                if (solveCell(puzzle, minNeighbour))
                    return true;//If a solution is found down the recursive tree, we can finish
            }

            //No solution found: time to clean up
            cell.Value = initialValue;
            cell.PossibleValues = initialPossibleValues;
            cell.Busy = false;
            return false;
        }

        static void showProgress(Puzzle puzzle)
        {
            int col = puzzle.Columns.Sum(c => c.isValid() ? 1 : 0);
            int row = puzzle.Rows.Sum(r => r.isValid() ? 1 : 0);
            int group = puzzle.Groups.Sum(g => g.isValid() ? 1 : 0);

            int correct = col + row + group;


            int num = puzzle.Columns.Count + puzzle.Groups.Count + puzzle.Rows.Count;

            Console.ForegroundColor = ConsoleColor.Cyan;
            Console.Write(new string('G', group));
            Console.ForegroundColor = ConsoleColor.Red;
            Console.Write(new string('C', col));
            Console.ForegroundColor = ConsoleColor.Green;
            Console.Write(new string('R', row));
            Console.ForegroundColor = ConsoleColor.Gray;
            Console.Write(new string('_', num - correct));
            Console.WriteLine(" ({0}/{1})", correct, num);
        }

        static void initPuzzle(Puzzle puzzle)
        {
            foreach (var cell in puzzle.All)
            {
                //Fill in constant value cells with their constant value
                if (cell.Group is ConstantSpan)
                {
                    cell.Value = cell.Group.Goal;
                }
            }
        }

        public static void updateCellPossibles(Puzzle puzzle, Cell cell)
        {
            if (cell.Group is ConstantSpan)
                return;

            var invalids = new List<int>();

            foreach (var c in cell.Row.Cells)
                if (c.Value > 0)
                    invalids.Add(c.Value);

            foreach (var c in cell.Column.Cells)
                if (c.Value > 0)
                    invalids.Add(c.Value);

            if (cell.Group.ChangedSinceGeneration)
                cell.Group.GenerateValids(puzzle);

            //find the set of valids not including any invalids
            cell.PossibleValues = cell.Group.Valids;
            cell.PossibleValues.ExceptWith(invalids);
            
            cell.PossibleValueCount = cell.PossibleValues.Count();
        }

        public static bool isPuzzleValid(Puzzle p)
        {
            bool valid = p.Columns.All(c => c.isValid());
            valid = valid && p.Rows.All(r => r.isValid());
            valid = valid && p.Groups.All(g => g.isValid());
            return valid;
        }
    }
}
