1 Востаннє редагувалося leofun01 (31.10.2021 12:59:42)

Тема: Алгоритми розвязання sudoku з прикладами мовою C#

Як ви розвязуєте sudoku ?
Мене цікавлять саме алгоритми, які інтелект застосовує до початкової задачі для того, щоб отримати рішення | розвязок.

Для простоти поки обмежимося найбільш поширеними типами:

Типи судоку
  • Класичний sudoku 9x9

  • Класичний sudoku 9x9 + діагоналі

  • Hyper sudoku 9x9

  • Nonomino sudoku 9x9

не звертайте уваги на те що всі вони квадрати 9x9, ми будемо абстрагуватися від розмірів і форм sudoku. Навіть форма клітин і топологія простору може сильно відрізнятися від класичних версій.

Інші типи судоку
  • Трикутний sudoku

  • Super Sudoku 3D

Але поки триває розробка, я буду наводити деякі кількістні характеристики на основі класичного судоку.

Для чого це: Я пишу програму, яка буде розвязувати sudoku. Користую C#, але зараз це не важливо.

Ідея:
Маємо абстрактні об'єкти: дошка (1), регіони (27), клітини (81).

Клітина:
Містить інформацію про цифри, які в ній можна розмістити, і які не можна.
Завжди визначена - ми завжди можемо чітко зказати чи можна там розмістити якусь конкретну цифру.
Але не завжди можемо зказати яка із допустимих цифр буде в цій клітині в кінцевому розвязку sudoku.
Не містить інформацію про свою позицію на дошці або в регіоні.

Дошка:
Містить інформацію про всі клітини і всі регіони. Кожній клітині поставлено у відповідність унікальний індекс - ціле число [0 .. 80]. Контролює оновлення клітин в такий спосіб, що якщо в даному регіоні клітина має тільки одне допустиме значення, то у всіх інших клітинах цього регіону це значення позначається як не допустиме.

Регіон:
Множина індексів (клітин дошки), які визначають область, в межах якої кожна цифра буде зустрічатись не більше ніж 1 раз. Кожний { рядок | стовпець | квадрат 3x3 } є регіоном.
Може містити інформацію про свою позицію на дошці. Але не може містити інформацію про значення клітин.
Як будь-яка множина, може бути результатом { перетину | обєднання } інших множин.

Фрагмети програми, код

Абстрактна клітина:

using System;
using System.Collections.Generic;

namespace DotNetSudoku {
    public interface ICell<C> : IEquatable<C>, IEnumerable<int>
        where C : ICell<C>, new()
    {
        bool this[int i] { get; set; }
        bool HasValue { get; }
        int ToInt();
        new IEnumerator<C> GetEnumerator();

        C Not();
        C And(C c);
        C Xor(C c);
        C Or(C c);
    }
}

Конкретна клітина, може містити hex цифру:

using System;
using System.Collections;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;
using System.Text;

namespace DotNetSudoku {
    using C = CellInt16;
    using IC = ICell<CellInt16>;

    [DebuggerDisplay("{ToString(),nq}, Bits = {_bits,h}")]
    public struct CellInt16 : IC
    {
        private short _bits;
        private CellInt16(int bits) { _bits = (short)bits; }

        private const byte _s = 16;

        public bool this[int i] {
            get { return (1 << i & _bits) == 0; }
            set {
                if(value)
                    _bits &= (short)~(1 << i);
                else
                    _bits |= (short)(1 << i);
            }
        }
        public bool HasValue {
            get {
                int b = -1 << _s | _bits;
                return (b + 1 | b) == -1;
            }
        }
        public int ToInt() {
            if(_bits == -1) return -1;
            int b = ~(-1 << _s | _bits);
            if((b - 1 & b) != 0)
                throw new InvalidOperationException();
            int i = 0;
            int s = _s;
            while(b > 1) {
                s >>= 1;
                if((-1 << s & b) != 0) {
                    b >>= s;
                    i += s;
                }
            }
            return i;
        }
        public override string ToString() {
            StringBuilder sb = new StringBuilder("{");
            IEnumerator<int> e = GetEnumerator();
            if(e.MoveNext()) {
                sb.Append(" ");
                sb.Append(e.Current);
            }
            while(e.MoveNext()) {
                sb.Append(", ");
                sb.Append(e.Current);
            }
            return sb.Append(" }").ToString();
        }
        public override int GetHashCode() { return _bits; }
        public IEnumerator<int> GetEnumerator() {
            for(int i = 0; i < _s; ++i)
                if(this[i]) yield return i;
        }
        IEnumerator<C> ICell<C>.GetEnumerator() {
            for(int i = 0; i < _s; ++i)
                if(this[i]) yield return (C)i;
        }
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        public bool Equals(C c) { return _bits == c._bits; }
        public override bool Equals(object o) { return o is C && Equals((C)o); }

        C IC.Not() { return new C(~_bits); }
        C IC.And(C c) { return new C(_bits | c._bits); }
        C IC.Xor(C c) { return new C(~(_bits ^ c._bits)); }
        C IC.Or(C c) { return new C(_bits & c._bits); }

        public static bool operator ==(C l, C r) { return l.Equals(r); }
        public static bool operator !=(C l, C r) { return !l.Equals(r); }

        public static C operator ~(C c) { return ((IC)c).Not(); }
        public static C operator &(C l, C r) { return ((IC)l).And(r); }
        public static C operator ^(C l, C r) { return ((IC)l).Xor(r); }
        public static C operator |(C l, C r) { return ((IC)l).Or(r); }

        public static implicit operator C(int value) {
            if(value == -1) return new C(-1);
            if((value & -_s) != 0)
                throw new ArgumentOutOfRangeException();
            return new C(~(1 << value));
        }
    }
}

Абстрактна впорядкована множина:

using System;
using System.Collections.Generic;
using System.ComponentModel;

namespace DotNetSudoku {
    public interface IOrderedSet<T> : IEnumerable<T>
        where T : IEquatable<T>, IComparable<T>
    {
        int Count { get; }
        bool Contains(T i);
    }
}

Частково реалізована впорядкована множина:

using System;
using System.Collections;
using System.Collections.Generic;

namespace DotNetSudoku {
    public abstract class OrderedSet<T> : IOrderedSet<T>
        where T : IEquatable<T>, IComparable<T>
    {
        public abstract int Count { get; }
        public virtual bool Contains(T item) {
            foreach(T t in this)
                if(ReferenceEquals(t, item) ||
                    !ReferenceEquals(t, null) && t.Equals(item)
                ) return true;
            return false;
        }
        public abstract IEnumerator<T> GetEnumerator();
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

        public static readonly OrderedSet<T> Empty = new EmptySet();

        private sealed class EmptySet : OrderedSet<T> {
            internal EmptySet() { }
            public override int Count { get { return 0; } }
            public override bool Contains(T item) { return false; }
            public override IEnumerator<T> GetEnumerator() { yield break; }
        }
    }
}

Є ще статичний клас-розширення для множин

using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Diagnostics;

namespace DotNetSudoku {
    public static class OrderedSetExtension {
        private class InternalOrderedSet<T> : OrderedSet<T>
            where T : IEquatable<T>, IComparable<T>
        {
            private int? _count;
            private Func<int> _getCount;
            private Predicate<T> _contains;
            private readonly IEnumerable<T> _enumer;

            internal InternalOrderedSet(IEnumerable<T> enumer) {
                _validate(enumer);
                _enumer = enumer;
            }
            internal InternalOrderedSet(IEnumerable<T> enumer, Predicate<T> contains)
                : this(enumer) { _contains = contains; }
            internal InternalOrderedSet(IEnumerable<T> enumer, Predicate<T> contains, int count)
                : this(enumer, contains) { _count = count; }
            internal InternalOrderedSet(IEnumerable<T> enumer, Predicate<T> contains, Func<int> getCount)
                : this(enumer, contains) { _getCount = getCount; }

            public override int Count {
                get {
                    if(!_count.HasValue) {
                        int c = 0;
                        if(_getCount != null) c = _getCount();
                        else foreach(T _ in this) ++c;
                        _count = c;
                    }
                    return _count.Value;
                }
            }
            public override bool Contains(T item) {
                if(_contains == null) _contains = base.Contains;
                return _contains(item);
            }
            public override IEnumerator<T> GetEnumerator() {
                foreach(T t in _enumer)
                    if(_contains(t))
                        yield return t;
            }
        }

        private static IEnumerable<T> _unionEnumerable<T>(IOrderedSet<T> r0, IOrderedSet<T> r1)
            where T : IEquatable<T>, IComparable<T>
        {
            var e0 = r0.GetEnumerator();
            var e1 = r1.GetEnumerator();
            bool m0 = e0.MoveNext();
            bool m1 = e1.MoveNext();
            while(m0 && m1) {
                T i0 = e0.Current;
                T i1 = e1.Current;
                bool lt = true;
                bool gt = true;
                if(!ReferenceEquals(i0, i1)) {
                    bool nn = !ReferenceEquals(i0, null);
                    lt = nn ? i0.CompareTo(i1) <= 0 : i1.CompareTo(i0) >= 0;
                    gt = nn ? i0.CompareTo(i1) >= 0 : i1.CompareTo(i0) <= 0;
                }
                yield return lt ? i0 : i1;
                if(lt) m0 = e0.MoveNext();
                if(gt) m1 = e1.MoveNext();
            }
            if(m0) do yield return e0.Current; while(e0.MoveNext());
            if(m1) do yield return e1.Current; while(e1.MoveNext());
        }
        private static IOrderedSet<T> _intersect<T>(IOrderedSet<T> r0, IOrderedSet<T> r1)
            where T : IEquatable<T>, IComparable<T>
        {
            return new InternalOrderedSet<T>(
                _unionEnumerable(r0, r1),
                i => r0.Contains(i) && r1.Contains(i)
            );
        }
        public static IOrderedSet<T> Intersect<T>(this IOrderedSet<T> _this, IOrderedSet<T> other)
            where T : IEquatable<T>, IComparable<T>
        {
            if(ReferenceEquals(_this, other)) return _this;
            _validate(_this); _validate(other);
            return _intersect(_this, other);
        }
        public static IOrderedSet<T> Union<T>(this IOrderedSet<T> _this, IOrderedSet<T> other)
            where T : IEquatable<T>, IComparable<T>
        {
            if(ReferenceEquals(_this, other)) return _this;
            _validate(_this); _validate(other);
            return new InternalOrderedSet<T>(
                _unionEnumerable(_this, other),
                i => _this.Contains(i) || other.Contains(i),
                () => _this.Count + other.Count - _intersect(_this, other).Count
            );
        }
        public static IOrderedSet<T> SymmetricExcept<T>(this IOrderedSet<T> _this, IOrderedSet<T> other)
            where T : IEquatable<T>, IComparable<T>
        {
            if(ReferenceEquals(_this, other)) return OrderedSet<T>.Empty;
            _validate(_this); _validate(other);
            return new InternalOrderedSet<T>(
                _unionEnumerable(_this, other),
                i => _this.Contains(i) ^ other.Contains(i),
                () => _this.Count + other.Count - _intersect(_this, other).Count * 2
            );
        }
        public static IOrderedSet<T> Except<T>(this IOrderedSet<T> _this, IOrderedSet<T> other)
            where T : IEquatable<T>, IComparable<T>
        {
            if(ReferenceEquals(_this, other)) return OrderedSet<T>.Empty;
            _validate(_this); _validate(other);
            return new InternalOrderedSet<T>(
                _unionEnumerable(_this, other),
                i => _this.Contains(i) && !other.Contains(i),
                () => _this.Count - _intersect(_this, other).Count
            );
        }

        public static bool _exist<T>(IOrderedSet<T> _this, Predicate<T> match)
            where T : IEquatable<T>, IComparable<T>
        {
            foreach(T t in _this)
                if(match(t)) return true;
            return false;
        }
        public static bool Exist<T>(this IOrderedSet<T> _this, Predicate<T> match)
            where T : IEquatable<T>, IComparable<T>
        {
            _validate(_this); _validate(match);
            return _exist<T>(_this, match);
        }
        public static bool All<T>(this IOrderedSet<T> _this, Predicate<T> match)
            where T : IEquatable<T>, IComparable<T>
        {
            _validate(_this); _validate(match);
            return !_exist<T>(_this, t => !match(t));
        }

        [DebuggerStepThrough]
        private static void _validate(object o) {
            if(ReferenceEquals(o, null))
                throw new ArgumentNullException();
        }
    }
}

Абстрактна дошка (інтерфейс):

using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace DotNetSudoku {
    using R = IOrderedSet<int>;
    using RC = ReadOnlyCollection<IOrderedSet<int>>;

    public interface IBoard<C> : IEnumerable<C>
        where C : ICell<C>, new()
    {
        RC Regions { get; }
        C EmptyCell { get; }
        int CellsCount { get; }
        C this[int i] { get; set; }
        bool IsComplete();
        R GetAffected(int i);
        IBoard<C> GetClone();
    }
}

Абстрактна дошка (з алгоритмами):

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;

namespace DotNetSudoku {
    using R = IOrderedSet<int>;
    using RC = ReadOnlyCollection<IOrderedSet<int>>;

    public abstract class Board<C> : IBoard<C>
        where C : ICell<C>, new()
    {
        private C[] _cells;
        private R[] _affected;
        private bool? _valid;
        private readonly RC _regions;
        public RC Regions { get { return _regions; } }

        public abstract C EmptyCell { get; }
        protected abstract IList<R> InitRegions(int count);

        protected Board(int cellsCount, int regionsCount) : this(cellsCount, null) {
            _regions = new RC(InitRegions(regionsCount));
        }
        protected Board(int cellsCount, RC regions) {
            _cells = new C[cellsCount];
            _affected = new R[cellsCount];
            _valid = null;
            for(int i = 0; i < cellsCount; ++i)
                _cells[i] = EmptyCell;
            _regions = regions;
        }
        protected Board(Board<C> board) : this(board.CellsCount, board._regions) {
            _valid = board._valid;
        }

        public static readonly C InvalidCell = (new C()).Not();

        public int CellsCount { get { return _cells.GetLength(0); } }
        public bool? IsValid { get { return _valid; } }
        public virtual C this[int i] {
            get { return _cells[i]; }
            set {
                C ci = this[i];
                C ni = ci.And(value);
                if(ci.Equals(ni)) return;
                _cells[i] = ni;
                ni = this[i];
                if(ni.HasValue) {
                    if(ni.Equals(InvalidCell))
                        _valid = false;
                    else
                        foreach(int a in GetAffected(i))
                            if(i != a) this[a] = ni.Not();
                }
            }
        }

        private int _getUndefined() {
            int i = 0, count = CellsCount;
            for(; i < count && this[i].HasValue; ++i)
                if(this[i].Equals(InvalidCell)) _valid = false;
            if(i == count && !_valid.HasValue) _valid = true;
            return i;
        }
        public bool IsComplete() {
            return _getUndefined() >= CellsCount;
        }
        public R GetAffected(int i) {
            if(_affected[i] != null) return _affected[i];
            R a = OrderedSet<int>.Empty;
            foreach(R r in _regions)
                if(r.Contains(i))
                    a = a.Union<int>(r);
            _affected[i] = a;
            return a;
        }
        public Board<C> GetClone() {
            Board<C> clone = (Board<C>)MemberwiseClone();
            if(_cells != null) {
                clone._cells = new C[CellsCount];
                Array.Copy(_cells, clone._cells, CellsCount);
            }
            return clone;
        }
        IBoard<C> IBoard<C>.GetClone() { return GetClone(); }
        public IEnumerator<C> GetEnumerator() {
            return ((IEnumerable<C>)_cells).GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }

        public void TryToSolve() {
            // тут я хочу розмістити алгоритм, який мав би розвязати цей sudoku.
        }
    }
}

Дошка класичного судоку 9x9:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Collections.ObjectModel;
using System.ComponentModel;
using System.Diagnostics;
using System.Text;

namespace DotNetSudoku {
    using B = Board9x9;
    using C = CellInt16;
    using R = IOrderedSet<int>;
    using RC = ReadOnlyCollection<IOrderedSet<int>>;
    using RangeEx = ArgumentOutOfRangeException;

    public class Board9x9 : Board<C>
    {
        private byte _i;
        protected const byte w = 3, h = 3, l = w * h, cc = l * l;
        protected const byte rcount = l * 3;

        public override C EmptyCell { get { return any; } }
        protected override IList<R> InitRegions(int count) {
            IList<R> regions = new List<R>(count);
            for(byte y = 0; y < l; ++y)
                regions.Add(new Row(y));
            for(byte x = 0; x < l; ++x)
                regions.Add(new Column(x));
            for(byte x = 0; x < l; x += w)
                for(byte y = 0; y < l; y += h)
                    regions.Add(new Square(y * l + x));
            return regions;
        }

        public Board9x9() : base(cc, rcount) { }
        protected Board9x9(int cellsCount, int regionsCount) : base(cellsCount, regionsCount) { }
        protected Board9x9(int cellsCount, RC regions) : base(cellsCount, regions) { }
        protected Board9x9(B board) : base(board) { _i = board._i; }

        [Browsable(false)]
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        protected static readonly C any = (C)0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8;
        protected static readonly C none = ~(new C());

        public static char CellToChar(C c) {
            c &= any;
            if(!c.HasValue) return '_';
            int i = c.ToInt();
            return i < 0 ? 'x' : (char)('1' + i);
        }
        public static C? CharToCell(char ch) {
            if('_' == ch || ch == '0') return any;
            if('1' <= ch && ch <= '9') return ch - '1';
            if('x' == ch) return none;
            return null;
        }

        [DebuggerStepThrough]
        [EditorBrowsable(EditorBrowsableState.Never)]
        public void Add(C c) {
            if(_i >= cc) throw new InvalidOperationException();
            this[_i] = c;
            ++_i;
        }
        [DebuggerStepThrough]
        [EditorBrowsable(EditorBrowsableState.Never)]
        public void Add(char ch) {
            C? c = CharToCell(ch);
            if(c.HasValue) Add(c.Value);
        }
        [DebuggerStepThrough]
        [EditorBrowsable(EditorBrowsableState.Never)]
        public void Add(string s) {
            int len = s.Length;
            for(int i = 0; i < len; ++i)
                Add(s[i]);
        }

        public virtual C this[int x, int y] {
            get { _validate(x, y); return base[y * l + x]; }
            set { _validate(x, y); base[y * l + x] = value; }
        }
        [DebuggerStepThrough]
        private void _validate(int x, int y) {
            if(x < 0 || l <= x) throw new RangeEx("x");
            if(y < 0 || l <= y) throw new RangeEx("y");
        }

        public new B GetClone() { return (B)base.GetClone(); }
        public override string ToString() {
            string newLine = "\r\n";
            StringBuilder sb = new StringBuilder("{");
            for(int y = 0, i = 0; i < l; y = i += h) {
                for(; y < h + i; ++y) {
                    sb.Append(newLine);
                    sb.Append(" ");
                    for(int x = 0, j = 0; j < l; x = j += w) {
                        C c = this[y * l + x];
                        sb.Append("   ");
                        sb.Append(CellToChar(c));
                        for(++x; x < w + j; ++x) {
                            c = this[y * l + x];
                            sb.Append(", ");
                            sb.Append(CellToChar(c));
                        }
                        sb.Append(",");
                    }
                }
                sb.Append(newLine);
            }
            return sb.Append("}").ToString();
        }

        protected struct Row : R
        {
            public readonly byte Y;

            public Row(int y) {
                if(y < 0 || l <= y) throw new RangeEx();
                Y = (byte)y;
            }

            public int Count { get { return l; } }
            public bool Contains(int i) {
                return i >= 0 && i < cc && i / l == Y;
            }
            public IEnumerator<int> GetEnumerator() {
                for(int x = 0; x < l; ++x)
                    yield return Y * l + x;
            }
            IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        }
        protected struct Column : R
        {
            public readonly byte X;

            public Column(int x) {
                if(x < 0 || l <= x) throw new RangeEx();
                X = (byte)x;
            }

            public int Count { get { return l; } }
            public bool Contains(int i) {
                return i >= 0 && i < cc && i % l == X;
            }
            public IEnumerator<int> GetEnumerator() {
                for(int y = 0; y < l; ++y)
                    yield return y * l + X;
            }
            IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        }
        protected struct Square : R
        {
            public readonly byte Pos;

            public Square(int pos) {
                if(
                    pos < 0 || cc <= pos ||
                    pos / l > (w - 1) * h ||
                    pos % l > w * (h - 1)
                )
                    throw new RangeEx();
                Pos = (byte)pos;
            }

            public int X { get { return Pos % l; } }
            public int Y { get { return Pos / l; } }
            public int Count { get { return l; } }
            public bool Contains(int i) {
                int x = i % l, y = i / l;
                return i >= 0 && i < cc
                    && X <= x && x < X + w
                    && Y <= y && y < Y + h;
            }
            public IEnumerator<int> GetEnumerator() {
                for(int y = 0; y < h; ++y)
                    for(int x = 0; x < w; ++x)
                        yield return y * l + x + Pos;
            }
            IEnumerator IEnumerable.GetEnumerator() { return GetEnumerator(); }
        }
    }
}

Приклад користання:

using System;

namespace DotNetSudoku {
    public static class Program {
        public static void Main(string[] args) {
            Board9x9 b = new Board9x9() {
                "_ 2 _   6 _ _   _ 3 8",
                "_ _ _   _ _ 4   _ _ _",
                "_ _ _   _ 7 _   _ _ _",

                "7 _ _   _ _ 5   4 _ _",
                "_ 8 _   _ _ _   _ 2 _",
                "_ _ _   _ _ _   _ _ _",

                "4 _ _   _ _ _   1 _ _",
                "1 _ _   2 _ _   _ _ _",
                "_ _ _   3 8 _   _ _ _",
            };
            Console.WriteLine(b);
            b.TryToSolve();
            Console.WriteLine(b);
            if(b.IsValid.HasValue) {
                if(b.IsValid.Value) Console.WriteLine("Solved.");
                else Console.WriteLine("This sudoku is invalid.");
            }
            else Console.WriteLine("Cannot to solve this puzle.");
            Console.Write("Press enter to exit. ");
            Console.ReadLine();
        }
    }
}

Розвязувати будемо тільки вілідні задачі. Валідний судоку - той що має єдиний розвязок.

Я доклав купу зусиль, щоб зробити все красиво, і тепер мені не вистачає тільки алгоритму для розвязання.

Як тільки появляться ідеї, буду постити їх сюди. І ви приєднуйтесь.

2 Востаннє редагувалося koala (31.10.2021 16:18:17)

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Невалідні теж немає особливої проблеми розв'язувати: беремо першу-ліпшу клітину (можна з мінімальною кількістю допустимих варіантів) і намагаємося розв'язати судоку, де в цій клітині кожен із варіантів.
Стосовно алгоритму: перебираємо змінені регіони, якщо в якомусь з них утворилася однозначно відома клітина - вичищаємо це значення в усіх регіонах, куди ця клітина входить, і позначаємо змінені регіони. Перебраний регіон викидаємо зі змінених.
Можна навіть сильніше: представимо регіон як матрицю "клітина - значення" з 0, якщо комбінація неможлива, і 1, якщо можлива. Якщо в цій матриці можна довільною перестановкою утворити прямокутник з нулів з сумою розмірів, що дорівнює розмірності матриці (тобто для розмірності 9 - 1х8, 2х7, 3х6, 4х5), то можна також очистити симетричний відносно основної діагоналі прямокутник. Наприклад (для розмірності 4):

Значення        Поля
          1   2   3   4
1         1   1   0   0
2         1   1   0   0
3         1   0   1   1
4         1   1   1   1

У полі 1 може бути значення 1-4, у полі 2 - 1, 2 і 4, у полях 3 і 4 - значення 3 і 4. Є прямокутник з нулів у кутку -  значить, можна також очистити симетричний прямокутник, і матриця стає


Значення        Поля
          1   2   3   4
1         1   1   0   0
2         1   1   0   0
3         0   0   1   1
4         0   0   1   1

(в полях 1 і 2 неможливі значення 3 і 4).

Подякували: leofun011

3

Re: Алгоритми розвязання sudoku з прикладами мовою C#

koala написав:

Невалідні теж немає особливої проблеми розв'язувати: беремо першу-ліпшу клітину (можна з мінімальною кількістю допустимих варіантів) і намагаємося розв'язати судоку, де в цій клітині кожен із варіантів.

Так, я відклав цей етап на потім, хочу зпочатку отримати красивий алгоритм для валідних, а потім якось припасувати рішення для всіх решта. Відчуваю що можу наробити алгоритмічних помилок, і якщо намагатись порішати всі задачі зразу, то складніше буде шукати помилки.

koala написав:

Стосовно алгоритму: перебираємо змінені регіони, якщо в якомусь з них утворилася однозначно відома клітина - вичищаємо це значення в усіх регіонах, куди ця клітина входить, і позначаємо змінені регіони. Перебраний регіон викидаємо зі змінених.

Так, це вже зроблено на етапі заповнення клітин значеннями (в класі Board<C>). Ось тут:

public virtual C this[int i] {
    get { return _cells[i]; }
    set {
        C ci = this[i];
        C ni = ci.And(value);
        if(ci.Equals(ni)) return;
        _cells[i] = ni;
        ni = this[i];
        if(ni.HasValue) {
            if(ni.Equals(InvalidCell))
                _valid = false;
            else
                foreach(int a in GetAffected(i))
                    if(i != a) this[a] = ni.Not();
        }
    }
}

GetAffected(i) повертає множину індексів клітин, на які ця клітина (this[і]) має вплив, тобто обєднання всіх регіонів, в які входить ця клітина. Це було перше що прийшло в голову.

koala написав:

Можна навіть сильніше: представимо регіон як матрицю "клітина - значення" з 0, якщо комбінація неможлива, і 1, якщо можлива. Якщо в цій матриці можна довільною перестановкою утворити прямокутник з нулів з сумою розмірів, що дорівнює розмірності матриці (тобто для розмірності 9 - 1х8, 2х7, 3х6, 4х5), то можна також очистити симетричний відносно основної діагоналі прямокутник. Наприклад (для розмірності 4):

Значення        Поля
          1   2   3   4
1         1   1   0   0
2         1   1   0   0
3         1   0   1   1
4         1   1   1   1

У полі 1 може бути значення 1-4, у полі 2 - 1, 2 і 4, у полях 3 і 4 - значення 3 і 4. Є прямокутник з нулів у кутку -  значить, можна також очистити симетричний прямокутник, і матриця стає


Значення        Поля
          1   2   3   4
1         1   1   0   0
2         1   1   0   0
3         0   0   1   1
4         0   0   1   1

(в полях 1 і 2 неможливі значення 3 і 4).

Шикарно, цього в мене поки нема. Буду думати чи можна цей алгоритм записати без матриць. В будь-якому випадку його треба буде зробити.

Подякували: 0xDADA11C71

4

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Над тим, що запропонував koala, мені треба посидіти-подумати. Як людина я розумію чому це буде працювати, але як програміст - хз як його реалізувати.

Помітив, трапляються ситуації коли якась цифра не може бути розміщена у всіх клітинах крім одної і при цьому в неї статус залишається як "є кілька варіантів" (1, 2, 6), хоча має бути тільки один (1):

https://i.ibb.co/9HgwzTf/sudoku-1-alone.png

для таких випадків зробив цей фрагмент:

foreach(R r in _regions) {
    foreach(int i in r) {
        C a = EmptyCell;
        foreach(int j in r)
            if(i != j)
                a = a.And(this[j].Not());
        if(a.HasValue && !a.Equals(InvalidCell)) {
            C t = this[i];
            C ta = t.And(a);
            if(!t.Equals(ta))
                this[i] = ta;
        }
    }
}

5

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Для перетину регіонів:

https://i.ibb.co/ctXGJHc/sudoku-135-intersect.png

foreach(R ro in _regions) {
    foreach(R ri in _regions) {
        if(ReferenceEquals(ro, ri)) continue;
        R x = ro.Intersect<int>(ri);
        if(x.Count < 2) continue;
        C a = InvalidCell;
        foreach(int i in x)
            a = a.Or(this[i]);
        foreach(int i in ro.Except<int>(ri))
            a = a.And(this[i].Not());
        if(!a.Equals(InvalidCell))
            foreach(int i in ri.Except<int>(ro)) {
                C t = this[i];
                C ta = t.And(a.Not());
                if(!t.Equals(ta)) this[i] = ta;
            }
    }
}

6

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Вибір, проблемою є вибір.

Яким би продуманим не був алгоритм, завжди існуватимуть способи задати обмеження і початковий стан системи так, що на якомусь етапі доведеться робити припущення про значення в даній клітині. І знову вилазить рекурсія, якої я хотів уникнути.

7 Востаннє редагувалося leofun01 (20.01.2022 08:31:00)

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Знайшов сторінку, яка рішає Sudoku, там є script, в ньому функція SolvePos(). Пробую розібрати, паралельно читаючи стратегію.

Я помилився
Не валідні

* 1-constrained#3

"......6894..1..7...8...2...2..5..3...1...8.........251..1.9..36..4.1..72.32.76..."

не має розвязку.

перевірив і він валідний (має 1 розвязок).

"123457689496183725587962143279541368315628497648739251751294836864315972932876514"

8 Востаннє редагувалося comport (20.01.2022 18:48:13)

Re: Алгоритми розвязання sudoku з прикладами мовою C#

А яке застосування цього?

9

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Знайшов сторінку, яка краще рішає Sudoku (by Andrew Stuart). Там є алгоритми і покрокові підказки.

comport написав:

А яке застосування цього?

Для мене це розвага, спосіб відпочинку.

Подякували: ch0r_t1

10

Re: Алгоритми розвязання sudoku з прикладами мовою C#

11

Re: Алгоритми розвязання sudoku з прикладами мовою C#

Алгоритм формуваня рішеня виявився зовсім не простим, і я ще в процесі .. (хотів написати "в процесі його створеня", але ні, далі про це). Репозиторій тепер публічний.

Я прочитав про те, як люди (і деякі програми) розвязують Sudoku, і це дуже цікаво. Крім базових правил, треба користувати стратегії (1, 2). Їх багато, я бачив кілька десятків, більшість з них застосовні для 9x9 і не узагальнюються для більших розмірів. Особливо зподобались ті, що користують математичні теореми. Також знайшов сторінку (Rosetta Code (en)), де пропонують готові примітивні рішеня.

В якийсь момент мені стало цікаво скільки взагалі існує варіантів заповнити порожню дошку 9x9. OEIS показує 6.67e+21 (A107739: 6670903752021072936960). Я вже знайшов деякі дільники (9!, (2!*3!*3!)^2) і їх обгрунтуваня, але решта для мене залишається загадкою (на приклад: ¿ звідки взявся 2^7 ?). Читав статті, де мало бути поясненя як вийшло таке число, але .. чи то я надто тупий, чи там його не є. А в більшості випадків статті просто безтолкові (приклад), не містять корисної інфо.

І для Sudoku 16x16 точної кількості рішень досі не знайдено, було би добре її знайти.