(Част 1) : Изграждане на решаващия инструмент и създаване на данни, които могат да се използват

въведение

Преди 15 или 20 години открих играта судоку, нямам ясен спомен как го направих, но си спомням, че наистина се заинтересувах от играта от пръв поглед.

Бързо намерих начин да решавам судоку, като написах възможните стойности на кутия вътре в нея и след това повторих цялото судоку, ред по редове, колона по колона и квадрат по квадрати и изтрих невъзможните стойности във всяка кутия, докато остане само една възможна стойност

Детето обича играта си не защото е лесна, а защото е трудна.

Бенджамин Спок

Когато можете да използвате прост метод за решаване на игра, тази игра моментално става скучна.

Поради тази причина всъщност никога не съм се наслаждавал да играя судоку толкова, колкото ми е било приятно да намеря метод за решаването му.

Ето визуализация на судоку с възможни числа в липсващите полета:

Нещо, което исках да направя, беше да направя решаващ проблем. По това време не знаех абсолютно нищо за програмирането, но знаех основите на Excel.

Затова реших да създам решаване на судоку с помощта на Excel, което за съжаление не можах да постигна, въпреки че алгоритъмът беше ясен в главата ми, не можах да го преведа, използвайки само функциите If/Else в Excel.

Така че продължих с живота си и 15 години по-късно започнах да уча програмиране.
Научих C в училище 42 в Париж и се опитах отново да създам решаване на судоку. Този път се почувствах много по-близо до постигането на моята програма, но познанията ми по програмиране все още бяха твърде малко по онова време и правенето на това на C не беше най-практичният начин, тъй като прави всичко по-сложно, отколкото трябва.

Продължете напред 2 години по-късно, започнах да уча Python онлайн, за да се подготвя за тренировъчния лагер на Flat Iron.

За да практикувам току-що придобитите си умения, решавам (отново) да опитам да направя решаване на судоку този път с Python. Имах много добра идея как да го направя. Но бях убеден, че ще попадна на грешки и че няма да е толкова ясен процес, колкото си мислех. Това е, което езикът C ви прави, предполагам.

Изграждане на решаващия инструмент

Така или иначе започнах да пиша своя софтуер за решаване на судоку.
Първо направих 3 различни функции, една за обработка на редове, една за обработка на колони, една за обработка на квадрати.

Създадох променлива, съдържаща судоку, за да реша, че е масив от масиви с размери 9 на 9, и въведох стойностите на мрежата на судоку, която намерих онлайн, заменяйки неизвестните числа с 0.

След това създадох функция за предварителна обработка, за да превърна нулите от моето судоку в списък с възможни стойности от 1 до 9.

Единственото нещо, което трябваше да направя след това, беше да повторя судоку с моите 3 функции, създадени преди това, докато моят списък с възможни стойности за всяка нула беше направен само до една възможна стойност. И тогава „Воаля!“.

Изграждането на решаващия процес беше изненадващо плавен процес. Това ме накара да обичам Python и езиците на високо ниво като цяло, тъй като ми отне много малко време да го направя в сравнение със C например.

Подобряване на решаващия инструмент с цел извеждане на полезни данни

Веднъж във Flat Iron ми хрумна идеята да анализирам изчислителното време на моя солвър. Изведнъж имах много въпроси, като:

  • Колко по-бърз или по-бавен ще бъде моята програма за решаване в зависимост от броя на неизвестните числа в судокуто за решаване?
  • Колко рунда са необходими за решаване на судоку?
  • Как се сравнява с хората?

Когато научихме за обектно-ориентираното програмиране в Python, реших да превърна моя решаващ инструмент в клас, за да го направя по-удобен за потребителя и лесен за използване.

Също така по този начин мога да създавам свойства вътре в Sudoku обекти като:

  • времето, необходимо за решаване
  • броя кръгове, необходими за решаване
  • броя на неизвестните променливи
  • първоначалното състояние на судокуто и състоянието на решеното судоку

И методи като:

  • solve() за решаване на судоку
  • print(), за да покаже судокуто по добре форматиран начин
  • get_solved_time(), който връща броя микросекунди, необходими за решаването
  • solve_like_humans() за решаване на судоку като човек (добавено време за обработка и т.н.)

Тъй като е трудно да се сдобиете с данни от хора, решаващи судоку, вместо това реших да създам метод за създаване на тези данни. Очевидно няма да е толкова добро, колкото да имате истински човешки набор от данни, но трябва да се доближи достатъчно.

След като всичко това е направено, имаме нужда от голям набор от судоку за решаване. За щастие намерих набор от 1 милион судоку за решаване на Kaggle!

Сега е време да създадете използваеми данни с помощта на решаващия инструмент.

За целта ще създам функция, която обхожда судокуто за решения, решава ги и експортира данните в csv файл.

Във втората част на този блог ще анализираме данните, произведени от решаващия инструмент, и ще начертаем визуализация на човешки данни спрямо моя решаващ инструмент.

Следва продължение…