Тема: Алгоритми розвязання sudoku з прикладами мовою C#
Як ви розвязуєте sudoku ?
Мене цікавлять саме алгоритми, які інтелект застосовує до початкової задачі для того, щоб отримати рішення | розвязок.
Для простоти поки обмежимося найбільш поширеними типами:
▼Типи судоку
не звертайте уваги на те що всі вони квадрати 9x9, ми будемо абстрагуватися від розмірів і форм sudoku. Навіть форма клітин і топологія простору може сильно відрізнятися від класичних версій.
▼Інші типи судоку
Але поки триває розробка, я буду наводити деякі кількістні характеристики на основі класичного судоку.
Для чого це: Я пишу програму, яка буде розвязувати 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();
}
}
}Розвязувати будемо тільки вілідні задачі. Валідний судоку - той що має єдиний розвязок.
Я доклав купу зусиль, щоб зробити все красиво, і тепер мені не вистачає тільки алгоритму для розвязання.
Як тільки появляться ідеї, буду постити їх сюди. І ви приєднуйтесь.
Подякували: P.Y., 0xDADA11C7, mamkin haker, ch0r_t, fed_lviv, dot, koala, Betterthanyou, Chemist-i, /KIT\10
