数独を全探索で解く（C#版）

はじめに

先人に触発されて、C#で数独を解いてみた。

変更点

• C#で書く
• 盤面を文字列でなくbyte配列で保持する
• 行・列・ブロックの取り得る状態をbit列で保持する
• イテレータを使用して、取り得る解を全て返す

実装

※簡潔に表すために、エラー処理等は省いています

環境.

Windows 11
Visual Studio 2022
.NET 8.0

使い方

main.cs

var q = "800000000003600000070090200050007000000045700000100030001000068008500010090000400";
var a = NumPle.Solve(q).Take(2).ToArray();

Console.WriteLine(a.Length switch {
    1 => a,
    0 => "Error:解がありません",
    _ => "Error:解が複数あります"
});

解法クラス

問題を読み込み、取り得る解を全て返す
問題及び解は先人に倣い、文字列（81文字）としている
クラスを直接参照せず、静的関数（Solve）のみ外部からアクセス可能とした

NumPle.cs

public class NumPle
{
    public static IEnumerable<byte> Parse(string s) => s.Select(c => (byte)(c - '0'));

    public static IEnumerable<string> Solve(string question)
    {
        var max = (int)Math.Sqrt(question.Length);
        return new NumPle([.. Parse(question)], max).Solve();
    }

    readonly byte[] cells;
    readonly int max;

    NumPle(byte[] cells, int max)
    {
        this.cells = cells;
        this.max = max;
    }

    IEnumerable<string> Solve()
    {
        var (i, possibles) = new Possible(max, cells).GetMinimum();
        if (i < 0)
        {
            if (IsComplete)
                yield return Answer;
            yield break;
        }

        foreach (var n in possibles)
        {
            cells[i] = n;
            foreach (var answer in Solve())
                yield return answer;
        }

        cells[i] = 0;
    }

    bool IsComplete => cells.All(v => v != 0);

    string Answer => string.Join("", cells.Select(v => $"{v}"));
}

探索クラス

盤面の状態から、次に変更すべきセルの位置と取り得る解を返す
次に変更すべきセルは、一番取り得る解が少ないセルとした
また、取り得る解が無いセルが見つかった場合は、解無しとなるためエラー（セル位置=-1）を返す

Possible.cs

internal class Possible(int max)
{
    readonly byte[] indexes = [.. Enumerable.Range(1, max).Select(i => (byte)i)];

    readonly Rows rows = new(max);
    readonly Columns columns = new(max);
    readonly Blocks blocks = new(max);
    readonly List<int> sets = [];
    readonly int length = max * max;

    public Possible(int max, byte[] cells) : this(max)
    {
        for (var i = 0; i < cells.Length; i++)
        {
            var n = cells[i] - 1;
            if (n < 0) continue;
            sets.Add(i);
            this[i, n] = true;
        }
    }

    public (int Cell, byte[] Possibles) GetMinimum()
    {
        if (IsError) return (-1, []);

        var (m, p) = (-1, new byte[max]);

        for (var i = 0; i < length; i++)
        {
            if (sets.Contains(i)) continue;
            var numbers = indexes.Where(n => !this[i, n - 1]).ToArray();
            // 取り得る解が無い場合は、この盤面はエラー
            if (numbers.Length <= 0) return (-1, []);
            if (p.Length <= numbers.Length) continue;
            (m, p) = (i, numbers);
        }

        return (m, p);
    }

    bool this[int cell, int bit]
    {
        get => rows[cell, bit] | columns[cell, bit] | blocks[cell, bit];
        set
        {
            rows[cell, bit] = value;
            columns[cell, bit] = value;
            blocks[cell, bit] = value;
        }
    }

    bool IsError => rows.IsError || columns.IsError || blocks.IsError;
}

行・列・ブロックの状態クラス

行・列・ブロックの状態を保持する
セル位置から各行・列・ブロックの位置を計算して、入力された数値を保持する
同じ数値が2回以上入力された場合は、エラー（IsError = true）とする
位置計算以外は、共通化（Countsクラス）した

Counts.cs

internal abstract class Counts(int count)
{
    static bool GetBit(int bits, int i) => (bits & 1 << i) != 0;
    static void SetBit(ref int bits, int i, bool value) => bits = value ? bits | 1 << i : bits & ~(1 << i);

    readonly int[] val = new int[count];
    protected readonly int length = count;

    protected abstract int GetIndex(int index);

    public bool this[int cell, int bit]
    {
        get => GetBit(val[GetIndex(cell)], bit);
        set
        {
            if (this[cell, bit] == value) IsError = true;
            SetBit(ref val[GetIndex(cell)], bit, value);
        }
    }

    public bool IsError { get; private set; }
}

internal class Rows(int count) : Counts(count)
{
    protected override int GetIndex(int index) => index / length;
}

internal class Columns(int count) : Counts(count)
{
    protected override int GetIndex(int index) => index % length;
}

internal class Blocks(int count) : Counts(count)
{
    readonly int SPLIT = count / 3;

    protected override int GetIndex(int index) =>
        (index % length) / SPLIT + (index / length / SPLIT) * SPLIT;
}

まとめ

先人（Python）に比べて行数が爆発した