Научно-методически статии
КАК КОМПЮТЪРЪТ РЕШАВА СУДОКУ – МАТЕМАТИЧЕСКИ МОДЕЛ НА АЛГОРИТЪМА
Резюме. В работата се разглеждат някои аспекти на обучението по програмиране. Набляга се на занимателния момент при подбора на подходящи примери за демонстрация на отделните езикови конструкции и структури от данни. Такъв пример е разгледаният алгоритъм за решаване на широко разпространената в последно време главоблъсканица судоку. Това е направено във връзка с понятието множество и неговото приложение в програмирането.
Ключови думи: education in programming; data structures; set; Sudoku matrix; Sudoku puzzle; mathematical model of an algorithm
Настоящата работа е замислена да подпомогне преподавателя по програмиране в стремежа му да даде съдържателен, интересен и забавен пример за ползата на понятието множество в програмирането. За целта обучаемите трябва добре да познават основните дефиниции от теория на множествата и да владеят основните операции с множества. Оттук следва и добре известният факт, че за да си добър програмист, е необходимо (но не и достатъчно) да си добър математик.
Класически пример за използването на множества в програмирането е станала програмната реализация на задачата за намиране на прости числа по метода, наречен „Решето на Ератостен“ (Jensen & Wirth, 1985; Nakov & Dobrikov, 2005; Stoyanova & Gochev, 1994). Тук сме длъжни да отбележим, че в (Stoyanova & Gochev, 1994) при реализацията на този алгоритъм е допусната грешка, причислявайки числото 1 към множеството на простите числа. Подобна грешка е недопустима за едно учебно помагало, тъй като би довела до объркване от страна на ползващите го.
Тук ще се спрем на занимателна и актуална задача, която се приема с голям интерес от страна на учащите – алгоритми за решаване на судоку. Това е широко разпространена в днешно време главоблъсканица, неизменно присъстваща в развлекателните страници на повечето вестници и списания и в развлекателни интернет сайтове. Судоку е игра, която развива у човек най-вече математическите способности, логическото мислене, комбинативността, въображението, умението за прогнозиране и други качества.
Ние няма да се спираме на програмната реализация на разглежданата от нас задача. Това до голяма степен зависи от езика за програмиране, избран от учебното заведение. Удобен за програмната реализация на разглеждания от нас алгоритъм е езикът „Паскал“, тъй като в него има вградени средства за работа с множества (Jensen & Wirth, 1985; Stoyanova & Gochev, 1994). Същият все още се избира от някои учебни заведения в системата на средното образование в качеството му на първи език за програмиране. Изложените идеи могат да бъдат реализирани и на произволен друг език за програмиране, например C++. Но в този случай трябва да търсим допълнителни средства за работа с множества – например реализираните в Standard Template Library (STL) асоциативни контейнери set и multiset (Azalov, 2008). Също така може да се използва и шаблонният клас set от системата за компютърна алгебра “Symbolic C++”, чийто програмен код е даден в подробности в (Tan, Steeb & Hardy, 2000). Разбира се, с учебна цел би могло да се създаде и собствен клас множество, като се опишат функциите, реализиращи теоретико-множествените операции (Todorova, 2011-a), (Todorova, 2011-b). Това би било прекрасно упражнение, като се има предвид и фактът, че базовото („универсално“) множество е с относително малка мощност. Например стандартната главоблъсканица судоку е с базово множество целите числа от 1 до 9, плюс празното множество.
Тук ще разгледаме само математическия модел на алгоритъма. По този начин съставянето на компютърна програма, решаваща произволна главоблъсканица судоку, се превръща в една нелоша тема за разработка на курсов проект по програмиране за ученици и студенти. Много често, както и в случая, описанието на математическия модел е достатъчно за програмната реализация на съответния алгоритъм.
Математически модел на алгоритъма
\(S=\left(s_{i j}\right), 1 \leq i, j \leq m=n^{2}\) Нека \(n\) е произволное квадра цяло полотнажително \(m \times m\) ма числотрица и (квадра некатна таб \(m=n^{2}\). лица, Нека двумерен масив), всички елементи на който са цели числа, принадлежащи на затворения интервал \([1, m]\). С помощта на \(n-1\) хоризонтални и \(n-1\) вертикални линии, прекарани съответно между някои от редовете и някои от стълбовете, матрицата \(S\) е разделена на \(n^{2}\) непресичащи се \(n \times n\) квадратни подматрици, които ще наричаме блокове. На фиг. 1 е показана матрицата \(S\) при \(n=3\).
Нека да означим блоковете в дефинираната по-горе матрица \(S=\left(s_{i j}\right)\) с \(A_{k l}, 1 \leq k, l \leq n\). Тогава по дефиниция, ако \(s_{i j} \in A_{k l}\), то
\[ (k-1) n \lt i \leq k n \] и
\[ (l-1) n \lt j \leq l n . \]
Нека \(s_{i j}\) принадлежи на блока \(A_{k l}\) и нека да са известни \(i\) и \(j\). Тогава лесно можем да съобразим, че \(k\) и \(l\) могат да бъдат изчислени с помощта на
формулите \[ k=\left[\tfrac{i-1}{n}\right]+1 \] и
\[ l=\left[\tfrac{j-1}{n}\right]+1, \] където с \([x]\) сме означили както обикновено функцията цяла част на реалното число \(x\).
Ще казваме, че \(S=\left(s_{i j}\right), 1 \leq i, j \leq m=n^{2}\) е судоку-матрица, ако във всеки ред, всеки стълб и всеки блок съществува точно по едно число от множеството \(Z_{m}=\left\{1,2, \ldots, m=n^{2}\right\}\).
Широко разпространена е главоблъсканицата, наречена судоку. Дадена е судоку-матрица, на която са изтрити някои от елементите. Липсващите елементи на \(S\) ще отъждествяваме с 0. Задачата на главоблъсканицата се състои в това да се възстановят липсващите елементи на судоку-матрицата. Предполага се, че авторите на конкретната главоблъсканица така са подбрали липсващите елементи, че задачата да има единствено решение. Това условие ще пропуснем и няма да се съобразяваме с него. Нещо повече, препоръчваме в заданието към обучаемите да бъде поставено условието да бъде намерен и броят на възможните решения. Ако задачата няма решение, то този брой ще бъде нула.
Най-разпространените главоблъсканици судоку са при \(n=3\), т.е. при \(m=9\).
Тук ще направим математически модел, описващ алгоритъм за създаване на компютърна програма, намираща всички решения (ако съществуват) на произволна главоблъсканица судоку. За целта съществено ще използваме познанията от теория на множествата.
Разглеждаме множествата \(R_{i}, C_{j}\) и \(B_{k l}\), където \(1 \leq i, j \leq m=n^{2}\), \(1 \leq k, l \leq n\). За всяко \(i=1,2, \ldots, m\), 2, , m , множеството \(R_{i}\) се състои от всички липсващи числа в \(i\)-я ред на матрицата. Аналогично дефинираме и множествата \(C_{j}, j=1,2, \ldots, m\) съответно за липсващите числа в \(j\)-я стълб и \(B_{k l}, k, l=1,2, \ldots, n\) съответно за липсващите числа в блоковете \(A_{k l}\) на \(S\). По такъв начин, ако стартираме програмата и дадем нулеви стойности на всички елементи на матрицата \(S\), то с помощта на създадената програма ще получим всевъзможните \(m \times m\) судоку-матрици.
Началото на алгоритъма се състои в многократното обхождане на всички елементи \(s_{i j} \in S\), такива че \(s_{i j}=0\), т.е. това са елементите, чиито истински стойности трябва да открием.
Нека \(s_{i j}=0\) и нека \(s_{i j} \in A_{k l}\). Полагаме
\[ P=R_{i} \cap C_{j} \cap B_{k l} . \]
Тогава са възможни следните три случая:
і) \(P=\phi\) ii) \(P=\{d\}, d \in Z_{m}=\{1,2, \ldots, m\}\)(празнот, d ∈ Zо мно m = {1жество). В този случай зада, 2, , m}, т.е. броят \(|P|\) нача елементитета няма решение. на \(P\) е равен на 1 (\(P\) е едноелементно множество). Тогава единствената възможност за \(s_{i j}\) е \(s_{i j}=d\), т.е. в този случай сме открили неизвестната стойност на \(s_{i j}\). Премахваме общия елемент \(d\) от множествата \(R_{i}, C_{j}\) и \(B_{k l}\), C j и Bk l , след което преминаваме към следващия нулев елемент на матрицата \(S\) (ако съществува такъв). iii) \(|P| \geq 2\). Тогава нищо не можем да кажем за неизвестната стойност на
\(s_{i j}\) и преминаваме към следващия нулев елемент на матрицата \(S\). Обхождането на нулевите елементи на матрицата \(S\) продължава, докато не настъпи едно от следните събития:
е1) занякои \(i, j \in\{1,2, \ldots, m\}\) еизпълнено \(s_{i j}=0\), но \(P=R_{i} \cap C_{j} \cap B_{k l}=\phi\). В този случай задачата няма решение;
е2) всички елементи на \(S\) станат различни от нула (строго положителни). Намерили сме едно решение на главоблъсканицата;
е3) обходени са всички нулеви елементи на \(S\), но не е настъпило нито събитие е1, нито събитие е2. С други думи, при всички оставащи нулеви елементи на \(S\) винаги е в сила описаният по-горе случай iii.
В случай че настъпи едно от събитията е1 или е2, то процедурата спира своята работа и извежда получения резултат.
В случай че настъпи събитие e3, то алгоритъмът трябва да продължи, използвайки други способи, например да приложим метода на „пробите и грешките“. В конкретния случай този метод се състои в следното.
Избираме произволно \(s_{i j} \in S\), такова че \(s_{i j}=0\) и нека \(k=\left[\tfrac{i-1}{n}\right]+1\), \(l=\left[\tfrac{j-1}{n}\right]+1\). Нека \(P=R_{i} \cap C_{j} \cap B_{k l}=\left\{d_{1}, d_{2}, \ldots, d_{t}\right\}\). Тогава за всяко \(d_{r} \in P, r=1,2, \ldots, t\) полагаме \(s_{i j}=d_{r}\). Такова полагане ще наричаме случайна проба. (Добре би било в програмната реализация на алгоритъма да броим и всички случайни проби до достигане на дадено решение.) След това решаваме задачата за намиране на неизвестните елементи на судоку-матрицата с един неизвестен елемент по-малко. Тук е удобно използването на рекурсия. База на рекурсията, т.е. ще излезем от процедурата, ако настъпи събитие e1 или e2. Това неминуемо би трябвало да се получи (т.е. няма да попаднем във „вечен цикъл“), тъй като при случайните проби намаляваме броя на нулевите елементи с 1.
На базата на описания тук модел ние реализирахме компютърна програма, която намира решението на произволно судоку (Yordzhev, 2014).
Стартирахме създадената програма при нулеви стойности на всички клетки. При \(n=2\) получихме, че броят на всички 4 X 4 судоку-матрици е равен на 288. При това, за да се получи този резултат, компютърът е направил 568 случайни проби. При \(n=3\) получихме, че съществуват точно 96 670 903 752 021 072 936 960 на брой 9 X 9 судоку матрици. Този резултат е известен и напълно съвпада с резултата, получен от други учени, вероятно и с други методи. На нас не ни е известен броят на всички 16 X 16 судокуматрици и смятаме, че това е открит за науката проблем. Но за да бъде решен този проблем, за целта е необходимо да ползваме много мощни и много бързи компютри.
REFERENCES/ЛИТЕРАТУРА
Azalov, P. (2008). Obektno orientirano programirane – strukturi ot danni i STL. Sofia: Ciela (ISBN 978-954-28-0184-9). [Азълов, П. (2008). Обектно ориентирано програмиране – структури от данни и STL. София: Сиела (ISBN 978-954-28-0184-9).]
Jensen, K. & Wirth, N. (1985). Pascal User Manual and Report. \(3{ }^{\text {rd }}\) ed., Springer-Verlag, (ISBN 3-540-96048-1.)
Nakov, P. & Dobrikov, P. (2005). Programirane \(=++\) Algiritmi. 3-thEdition, Sofia (ISBN 954-8905-16-X).[Наков, П. & Добриков, П. (2005). Програмиране \(=++\) Алгоритми. Трето издание. София (ISBN 954-8905-16-X).]
Stoyanova, R. & Gochev,G. (1994). Programirane na Pascal s 99 primerni programi. Sofia: Paraflow (ISBN 954-564-012-Х). [Стоянова, Р. & Гочев, Г. (1994). Програмиране на Pascal с 99 примерни програми. София: Paraflo (ISBN 954-564-012-Х).]
Tan, K. S., Steeb, W. -H. & Hardy, Y. (2000). Symbolic C++: An Introduction to Computer Algebra using Object-Oriented Programming. Springer (ISBN 1-85233-260-3.)
Todorova, M. (2011-a). Obektno orientirano programirane na bazata na ezika \(C++\). Sofia: Ciela, ISBN 978-954-28-0909-8. [Тодорова, М. Обектно ориентирано програмиране на базата на езика \(C++\). София: Сиела, ISBN 978-954-28-0909-8.]
Todorova, M. (2011-b). Strukturi ot danni i programirane na ezika \(C++\). Sofia: Ciela (ISBN 978-954-28-0990-6). [Тодорова, M. (2011) Структури от данни и програмиране на езика \(C++\). София: Сиела (ISBN 978-954-28-0990-6).]
Yordzhev, K. (2014). Pobitovi operatcii, grafi i kombinatorni prilozheniya. Blagoevgrad: SWU “Neofit Rilski” (ISBN 978-954-680-961-2). [Йорджев, К. (2014). Побитови операции, графи и комбинаторни приложения. Благоевград: ЮЗУ „Н. Рилски“ (ISBN 978-954-680-961-2).]