Kyouen Solver

using System;
using System.Collections;
using System.Collections.Generic;
using System.Threading.Tasks;
using System.Diagnostics;
class CustomData
{
    public int id;
    public List<int> p_list;
    public int[] counter;
    public int idx;
}
class Program
{
    static List<Tuple<int, int, List<int>>> points = new();
    static int N = 6;
    static List<List<int>> circles_l = new();
    static bool IsConcyclicInOrder(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
    {
        // AC * BD = AB * CD + BC * AD
        double AC = Math.Sqrt(Math.Pow(x3 - x1, 2) + Math.Pow(y3 - y1, 2));
        double BD = Math.Sqrt(Math.Pow(x4 - x2, 2) + Math.Pow(y4 - y2, 2));
        double AB = Math.Sqrt(Math.Pow(x2 - x1, 2) + Math.Pow(y2 - y1, 2));
        double CD = Math.Sqrt(Math.Pow(x4 - x3, 2) + Math.Pow(y4 - y3, 2));
        double BC = Math.Sqrt(Math.Pow(x3 - x2, 2) + Math.Pow(y3 - y2, 2));
        double AD = Math.Sqrt(Math.Pow(x4 - x1, 2) + Math.Pow(y4 - y1, 2));
        double delta = AC * BD - AB * CD - BC * AD;
        return delta >= -1e-10 && delta <= 1e-10;
    }

    static bool IsConcyclic(double x1, double y1, double x2, double y2, double x3, double y3, double x4, double y4)
    {
        return IsConcyclicInOrder(x1, y1, x2, y2, x3, y3, x4, y4) || IsConcyclicInOrder(x1, y1, x2, y2, x4, y4, x3, y3);
    }

    static void PreProcessCircles()
    {

        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                points.Add(new Tuple<int, int, List<int>>(j, i, new List<int>()));
            }
        }

        HashSet<BitArray> circles = new();
        for (int i = 0; i < points.Count; i++)
        {
            for (int j = i + 1; j < points.Count; j++)
            {
                for (int k = j + 1; k < points.Count; k++)
                {
                    List<int> circle = new List<int> { i, j, k };
                    for (int u = 0; u < points.Count; u++)
                    {
                        if (u == i || u == j || u == k)
                        {
                            continue;
                        }
                        int[] _tmp = { i, j, k, u };
                        Array.Sort(_tmp);
                        if (IsConcyclic(points[_tmp[0]].Item1, points[_tmp[0]].Item2, points[_tmp[1]].Item1, points[_tmp[1]].Item2, points[_tmp[2]].Item1, points[_tmp[2]].Item2, points[_tmp[3]].Item1, points[_tmp[3]].Item2))
                        {
                            circle.Add(u);
                        }
                    }
                    if (circle.Count >= 4)
                    {
                        BitArray _bits = new(N * N, false);
                        foreach (var p in circle)
                        {
                            _bits[p] = true;
                        }
                        if (!circles.Contains(_bits))
                        {
                            circles.Add(_bits);
                            circles_l.Add(circle);
                            foreach (var u in circle)
                            {
                                points[u].Item3.Add(circles_l.Count - 1);
                            }
                        }
                    }
                }
            }
        }
    }
    static List<int> Compute(int task_id, List<int> p_list, int[] counter, int idx)
    {
        int max_count = 0;
        List<int> max_p_list = new();
        int search_count = 0;

        void Dfs(int[] counter, int[] p_marked, int total_marked, int idx)
        {
            search_count++;
            if (search_count % 1000000 == 0)
            {
                Console.WriteLine($"[{task_id}][Step {search_count}]: [{string.Join(", ", p_list)}]");
            }
            int i_max = Math.Min(2 * N + idx, points.Count);
            for (int i = idx; i < i_max; i++)
            {
                if (p_marked[i] == 0)
                {
                    int new_total_marked = total_marked;
                    foreach (var j in points[i].Item3)
                    {
                        counter[j]++;
                        if (counter[j] == 3)
                        {
                            foreach (var p in circles_l[j])
                            {
                                if (p_marked[p] == 0)
                                {
                                    new_total_marked++;
                                }
                                p_marked[p]++;
                            }
                        }
                    }
                    if (N * N - new_total_marked + p_list.Count + 1 > max_count)
                    {
                        p_list.Add(i);
                        Dfs(counter, p_marked, new_total_marked, i + 1);
                        p_list.RemoveAt(p_list.Count - 1);
                    }

                    foreach (var j in points[i].Item3)
                    {
                        if (counter[j] == 3)
                        {
                            foreach (var p in circles_l[j])
                            {
                                p_marked[p]--;
                            }
                        }
                        counter[j]--;
                    }
                }
            }
            if (max_count < p_list.Count)
            {
                max_count = p_list.Count;
                max_p_list = new List<int>(p_list);
                Console.WriteLine($"[{task_id}]: {max_count} [{string.Join(", ", max_p_list)}]");
            }
        }

        Dfs(counter, new int[points.Count], 0, idx);
        return max_p_list;
    }

    static void AlgorithmStart()
    {
        List<Task<List<int>>> tasks = new();
        List<int> p_list = new List<int>();
        int max_count = 0;
        List<int> max_p_list = null;

        void Dfs_2step(int[] counter, int idx)
        {
            int i_max = Math.Min(2 * N + idx, points.Count);
            if (p_list.Count == 0)
            {
                i_max = (N - 1) / 2;
            }
            for (int i = idx; i <= i_max; i++)
            {
                foreach (var j in points[i].Item3)
                {
                    counter[j]++;
                }
                p_list.Add(i);
                if (p_list.Count >= 2)
                {
                    Console.WriteLine($"Starting task [{string.Join(",", p_list.ToArray())}]");
                    var task = Task<List<int>>.Factory.StartNew(
                        (Object obj) =>
                        {
                            CustomData data = obj as CustomData;
                            if (data == null) return null;
                            return Compute(data.id, data.p_list, data.counter, data.idx);
                        },
                        new CustomData()
                        {
                            id = tasks.Count,
                            p_list = new List<int>(p_list),
                            counter = (int[])counter.Clone(),
                            idx = i + 1
                        }
                    );
                    tasks.Add(task);
                }
                else
                {
                    Dfs_2step(counter, i + 1);
                }
                p_list.RemoveAt(p_list.Count - 1);
                foreach (var j in points[i].Item3)
                {
                    counter[j]--;
                }
            }
        }

        Dfs_2step(new int[circles_l.Count], 0);
        Task.WaitAll(tasks.ToArray());
        foreach (Task<List<int>> task in tasks)
        {
            if (max_count < task.Result.Count)
            {
                max_count = task.Result.Count;
                max_p_list = task.Result;
            }
        }
        Console.WriteLine("=========================");
        Console.WriteLine($"[{N}x{N}] Final Result: {max_count} [{string.Join(", ", max_p_list)}]");
    }

    static void Main()
    {
        PreProcessCircles();
        Stopwatch stopWatch = new Stopwatch();
        stopWatch.Start();
        AlgorithmStart();
        stopWatch.Stop();
        TimeSpan ts = stopWatch.Elapsed;
        string elapsedTime = string.Format("{0:00}:{1:00}:{2:00}.{3:00}",
            ts.Hours, ts.Minutes, ts.Seconds,
            ts.Milliseconds / 10);
        Console.WriteLine("RunTime " + elapsedTime);
    }
}