Алгоритм рішення судоку

Алгоритм рішення судоку.

Ігрове поле - квадрат розміром 9x9, розділений на менші квадрати зі стороною в 3 клітини. Все ігрове поле складається з 81 клітини. У них вже на початку гри стоять деякі числа (від 1 до 9), звані підказками. Потрібно заповнити вільні клітини цифрами від 1 до 9 так, щоб в кожному рядку, в кожному стовпці і в кожному малому квадраті 3x3 кожна цифра зустрічалася б тільки один раз.

Глобальні змінні

Ці глобальні змінні доступні всім процедурам і функціям програми.

нумерація полів

Нумерація полів відбувається при запуску програми, тобто при створенні форми. Поля нумеруються в наступному порядку.

Заповнення масиву x [i, j]. де i - номер стовпця, а j - номер рядка. 0? i? 8- 0? j? 8;

Заповнення двовимірного масиву m [k, mc [k]]

Для кожного поля, що має номер k = x [i, j]. 1? K? 81. що знаходиться в столбцe i і рядку j. знаходяться 20 полів m [k, mc [k]]. де 1? mc [k]? 20. кожне з яких знаходиться в столбцe i0 і рядку j0. Кожне з цих 20 полів знаходиться або в тій же самій рядку, або в тому ж самому стовпці, або в тому ж самому блоці розміру 3x3, що і поле k.

Для цього в циклі, де i змінюється від 1 до 8, j змінюється від 0 до 8, i0 змінюється від 0 до 8, j0 змінюється від 0 до 8, для двох номерів полів x [i, j] і x [i0, j0 ]. якщо їх номери стовпців збігаються, і при цьому їх номери рядків не совпадают- або їх номери рядків совадают, і при цьому їх номери стовпців совпадают- або їх номери стобцов не збігаються, і їх номери рядків не збігаються, і при цьому вони належать одній і тієї ж осередку розміру 3x3, що означає равноство целочисленного діяння на 3 номера рядка і номера стовпчика, то mc [x [i, j]] збільшується на одиницю, а x [i0, j0] записується в масив m [x [i, j], mc [x [i, j]]. соостветствующее номеру k = x [i, j]. В кінці цієї процедури для будь-якого k. 1? K? 81. все значення mc [k] = 20. і для кожного поля k, 1? k? 81. буде знайдено 20 полів m [k, L], 1? L? 20. для яких або номер стовпця m [k, L] збігається з номером стовпця поля k. а номер рядка m [k, L] не збігається з номером рядка поля k - або номер рядка m [k, L] збігається з номером рядка поля k. а номер стовпчика m [k, L] не збігається з номером стовпця поля k - або номер стовпця m [k, L] не збігається з номером стовпця поля k. номер рядка m [k, L] не збігається з номером рядка поля k. а частка від целосчіленного ділення на 3 номера стовпчика m [k, L] збігається з часткою від цілочисельного ділення на 3 номери стоблца k. і частка від целосчіленного ділення на 3 номера рядка m [k, L] збігається з часткою від цілочисельного ділення на 3 номера рядка k.

Введення вихідних даних. Заповнення глобальних масивів z [k, 0], s [k], p [k], 1? K? 81

В осередку z [k, 0] буде зберігатися вихідна задача. Якщо поле c номером k пусте, то в z [k, 0] записується нуль, а якщо в цьому полі є цифра, то в z [k, 0] записується ця цифра. Потім елементів масиву s [k] присвоюється значення z [k, 0].

Логічний масив p [k] заповнюється наступним чином: якщо поле c номером k пусте, то p [k] присвоюється значення false. а якщо воно не порожнє, то p [k] присвоюється значення true. У наступних рекурсивних функціях значення s [k] не змінюватиметься для тих полів, для яких p [k] = true.

Якщо Ви вибрали «Перебір всіх цифр», то значення змінної frugal присвоюється значення 0. Якщо обрана опція «Пошук одинаків», то змінної frugal присвоюється значення 1. Якщо вибрана опція «Пошук прихованих одинаків», то змінної frugal присвоюється значення 2.

Перевірка судоку на наявність помилок

Функція control перевіряє, чи немає двох однакових цифр, відмінних від нуля, в рядку, стовпці або блоці 3x3. Якщо таких цифр немає, то значення функції true. а якщо в якій-небудь рядку, стовпці або блоці 3x3 найдeтся дві однакові цифри, то значення функції дорівнює false.

Присвоюється значення локальної змінної q: = true - для всіх полів k з номерами від 1 до 81, і для всіх mc [k] = 20 полів, які перебувають з полем k в тому ж стовпці або в тій же рядку або в тому ж блоці 3x3 , якщо цифри збігаються і відмінні від нуля, то q: = false. Функції control присвоюється значення локальної змінної q.

Рекурсивна процедура неекономного рішення судоку

Процедура rec (k, g) викликається тоді, коли прапорець «Економно» на формі знятий. Рекурсивна процедура rec (k, g) ставить в поле з номером k цифру t. якої немає ні в в одному з 20 полів, що мають з полем k або той же самий номер стовпчика, або той же самий номер рядка, або той же самий блок розміром 3x3. Процедура має два параметри. Параметр k - це номер поля, в який ставиться цифра. Параметр g - це кількість рішень, які треба знайти.

Якщо на початку поле з номером k було непустою, то цифра, що стоїть в ньому, не може бути змінена, p [k] = true. В цьому випадку відбувається перехід до наступного поля з номером k + 1. тобто відбувається виклик рекурсивної процедури з параметраміrec (k + 1, g).

Якщо на початку поле з номером k було порожнім, тобто p [k] = false. то для поля з номером k шукається яка-небудь цифра від 1 до 9, якої немає в 20 полях, що мають з полем k або той же самий номер стовпчика, або той же самий номер рядка, або той же самий блок розміром 3x3. Якщо знайдеться така цифра t. то вона ставиться в поле з номером k. тобто s [k] присвоюється значення t - число ходів c збільшується на едініцу- після цього відбувається перехід до наступного поля з номером k + 1. тобто відбувається виклик рекурсивної процедури rec (k + 1, g). Якщо все 9 цифр перебрані, і жодну цифру не можна поставити в поле k. так як кожна цифра стоїть хоча б в одному з 20 полів, що мають з полем k або той же самий номер стовпчика, або той же самий номер рядка, або той же самий блок розміром 3x3, то в поле з номером k ставиться 0. тобто s [k] присвоюється нульове значення. Цей процес триває до тих пір, поки номер поля НЕ провосходіт кількості полів тобто k? 81. поки кількість знайдених рішень u менше заданого в качетсве другого параметра процедури значення g. і поки польозватель не натиснете кнопку «Стоп».

Відео: Рішення сложниx судоку. трійки

Як тільки буде викликана процедура rec (k, g) з номером k = 82. перевищує кількість полів, кількість рішень u збільшується на одиницю, в масив z [k, u] записується рішення s [k]. тобто для всіх полів з номером k від 1 до 81 елементу масиву z [k, u] присвоюється значення s [k].

Відео: Як вирішувати судоку

На рішення судоку йде іноді до 5 секунд. Але якщо судоку рішень не має, і при цьому знятий прапорець «Економно», то пошук рішення неекономним методом перебору може тривати дуже багато годин, і тому активована кнопка «Стоп» Процедура Application.ProcessMessages- в Лазарус запобігає зависання програми.

Підготовка до економного вирішення судоку

Процедура possible для кожного поля з номером k визначає, яке число w [k] можливих цифр може бути поставлено в кожне таке поле з номером k. і записує всі ці цифри в масив b [k, j]. де другий індекс j пробігає значення від 1 до w [k].

Якщо для якогось поля з номером k значення w [k] = 0. то ця судоку не має рішень, локальної змінної det присвоюється значення false. Якщо для якогось поля з номером k значення w [k] = 1. то в це поле з номером k ставиться дана єдино можлива цифра, тобто значенням s [k] присвоюється значення b [k, 1]. після чого функція ingress повторно перевіряє всі поля з номерами k від 1 до 81 (змінної rep присвоюється значення true). Цикл звершается тоді, коли або для якогось поля k кількість можливих цифр виявилося нульовим, тобто w [k] = 0. і судоку рішень не імеет- або коли для всіх полів з номерами k від 1 до 81 значення w [k] gt; 1 (при цьому значення змінної rep одно false).

Процедура possible. таким чином, знаходить всіх кандидатів для кожної порожньої комірки c номером k. записує їх в масив b [k, j]. а кількість цих кандидатів записує в масив w [k]. Після цього в таблиці відшукуються всен одинаки, тобто осередки, в яких можлива тільки одна цифра і ніяка інша, тобто находятсмя все такі осередки, для яких w [k] = 1. У ці осередки записується даний єдиний кандидат b [k, 1].

Пошук прихованих одинаків

Якщо в осередку варто кілька кандидатів, але один з них не зустрічається більше ні в жодній іншій клітинці даного блоку або стовпця або рядка, то такий кандидат має назву «прихованої одинаком». Функція ingress виявляє послідовно всіх «прихованих одинаків», записує їх у відповідні поля і після цього знову викликає процедуру possible. яка знову створює масив кандидатів для решти порожніх клітинок.

Кількість заповнених осередків буде зберігатися у змінній cp. значення якої буде збільшуватися на одиницю при кожному заповненні порожнього вічка або «одинаком», або «прихованої одинаком»

На початку шукаються «приховані одинаки», рівні цифрі t в кожному блоці з номером від 0 до 8, де номер блоку дорівнює li + 3 * lj. а li - частка від цілочисельного ділення на 3 номера стовпця i. а lj - частка від цілочисельного ділення на 3 номера рядка j.

Масив onel [li + 3 * lj, t] буде містити кількість кандидатів, рівних цифрі t і містяться в блоці з номером li + 3 * lj.

Якщо для якогось блоку onel [li + 3 * lj, t] = 1. то знаходиться осередок, що стоїть в стовпці з номером i і в рядку з номерм j. в якій є цифра t. і якщо ця комірка порожня, то в неї записується цифра t. а лічильник cp записаних попередньо цифр збільшується на 1.

Після цього перевіряється, чи немає серед дев`яти блоків з номероамі від 0 до 8 такого блоку з номером onel [li + 3 * lj, t]. для якого для якоїсь цифри t значення onel [li + 3 * lj, t] = 0. Якщо такий блок знайдеться, то судоку рішень не має, змінної det присвоюється значення false. управління передається на мітку ending. і функція завершує роботу з результатом false

Після цього шукаються «приховані одинаки», рівні цифрі t в кожному стовпці i з номером від 0 до 8. Масив onei [i, t] буде містити кількість кандидатів, рівних цифрі t і містяться в стовпці з номером i.

Якщо для якогось стовпця з номером i значення onei [i, t] = 1. то знаходиться осередок, що знаходиться в рядку з номером j. в якій є цифра t. і якщо ця комірка порожня, то в неї записується цифра t. а лічильник cp записаних попередньо цифр збільшується на 1.

Після цього перевіряється, чи немає серед дев`яти стовпців з номероамі від 0 до 8 такого стовпця з номером i. для якого для якоїсь цифри t значення onei [i, t] = 0. Якщо такий стовпець знайдеться, то судоку рішень не має, змінної det присвоюється значення false. управління передається на мітку ending. і функція завершує роботу з результатом false

Після цього шукаються «приховані одинаки», рівні цифрі t в кожному рядку j з номером від 0 до 8. Масив onej [j, t] буде містити кількість кандидатів, рівних цифрі t і містяться в рядку з номером j.

Якщо для якоїсь рядки з номером j значення onej [j, t] = 1. то знаходиться осередок, що знаходиться в стовпці з номером ш. в якій є цифра t. і якщо ця комірка порожня, то в неї записується цифра t. а лічильник cp записаних попередньо цифр збільшується на 1.

Після цього перевіряється, чи немає серед дев`яти рядків з номероамі від 0 до 8 такого рядка з номером j. для якої для якоїсь цифри t значення onej [j, t] = 0. Якщо такий рядок знайдеться, то судоку рішень не має, змінної det присвоюється значення false. управління передається на мітку ending. і функція завершує роботу з результатом false

після будь-якої записи в порожню осередок цифри змінної rep присвоюється значення true. що означає те, що цикл буде повторений, буде неайдени спочатку всі кандидати для кожного осередку за допомогою процедури possible, за допомогою тієї ж процедури possible шукаються і записуються в порожні клітинки «одинаки», а потім шукаються «приховані одинаки» функцією ingress. Цикл завершиться або тоді, коли не залишиться «прихованих одинаків», або тоді, коли знайдеться блок або рядок або стовпець, в які не можна поставити якусь із дев`яти цифр.

Рекурсивна процедура економного вирішення судоку

Рекурсивна процедура економного вирішення судоку recfrugal (k, g) працює точно так само, як процедура неекономного рішення судоку rec (k, g). але тільки для кожного поля перебираються не всі цифри від 1 до 9, а тільки можливі для кожного поля цифри з масиву b [k, j]. де j = w [k] більше 1.

Висновок рішення з номером d на екран

Знаходження всіх рішень судоку

Може бути утсновлена одна з трьох опцій «Пошук прихованих одинаків» (frugal = 2), або «Пошук одинаків» (frugal = 1), або «Перебір всіх цифр» (frugal = 0).

Якщо frugal = 0. то рекурсивної функцією rec (k, g) перебираються всі цифри для кожної вільної комірки, для якої p [k] = true.

Якщо frugal = 1. то спочатку обчислюються і записуються в масив b [k, t] всі можливі кандидати для кожної вільної комірки c номером k. а кількість можливих кандидатів записується в масив w [k]. Після цього в ті осередки, для яких існує єдиний кандидат, тобто в такі осередки, для яких w [k] = 1. записується цей кандидат. Описані дії здійснює функція possible (). Після того, що не отсанется жодної «одинаки», для кожної вільної комірки рекурсивної функцією recfrugal (k, g) перебираються залишилися кандидати.

Якщо frugal = 2. то після пошуку «одинаків» функцією possible () здійснюється пошук «приховані одинаки» функцією ingress (). тобто шукаються осередки, в яких варто кілька кандидатів, але один з кандидатів не зустрічається більше ні в жодній іншій клітинці даного блоку або стовпця або рядка. Цей кандідідат записується в відповідну клітинку. Після того, що не отсанется жодної «прихованої одинаки», для кожної вільної комірки рекурсивної функцією recfrugal (k, g) перебираються залишилися кандидати.

0), то - gt; Якщо (control () = false), то вивести повідомлення `Судоку неверная`- gt; - "height = тисячу п`ятьдесят-одна width = 809gt;

Запис рішення в файл

Пошук прихованих одинаків

задана Судоку

телефони +79203451544, +79106942514

Висновок на екран наступного рішення судоку

Якщо судоку має більше одного рішення, тобто u gt; 1. то активізується кнопка «gt; gt;», з якою пов`язана процедура ButtonNextSolutionclick (). яка збільшує значення disp на одиницю, якщо disp lt; u, і привласнює disp значення 1, якщо disp = u. Після цього рішення з номером disp виводиться на екран.

Висновок на екран попереднього рішення судоку

Якщо судоку має більше одного рішення, тобто u gt; 1. то активізується кнопка «lt; lt;», з якою пов`язана процедура ButtonBeforeSolutionclick (). яка зменшує значення disp на одиницю, якщо disp gt; 1, і привласнює disp значення u. якщо disp = 1. Після цього рішення з номером disp виводиться на екран.

Два алгоритму генерації судоку з заданим числом рішень.

Випадкова перестановка з 9 цифр

Дана процедура randomingnumber () переставляє 9 цифр у випадковому порядку і записує їх в глобальний масив y [t].

Випадкова перестановка з 81 поля

Дана процедура randomfield () переставляє 81 цифр у випадковому порядку і записує їх в глобальний масив r [k]. В алгоритмі №1 пошуку розв`язуваної судоку масив r [k] буде служити для випадкової вибірки h полів з 81 поля, а в алгоритмі №2 пошуку судоку перші h полів будуть заповнюватися в порядку, який записаний в масиві r [k]

Кількість рішень судоку

Ця функція rank (g) має параметр g. рівний заданому кількості рішень. Вона бере дані з глобального масиву gen [k]. намагається знайти кількість рішень на одиницю більше заданого g Відповідає судоку з цифрами в полях s [k] = gen [k] і записує в глобальну змінну u кількість рішень цієї судоку.