При подготовката ми за изпит номер 2 по C# в Софтуерната академия попаднах на една, за мен, интересна задача: Решаване на Sudoku! Реших да споделя решението си с вас. Използвам Brute Force метода, тъй като изникна първи в съзнанието ми, пък и нали точно по този начин решаваме едно Sudoku – минаваме през всички възможни комбинации от цифри за да стигнем до единствения възможен отговор. Нека първо обясним какво е Sudoku и какво представлява Brute Force метода.
Sudoku – Това е игра която представлява матрица с размер 9 Х 9 на брой квадратчета, които от своя страна са групирани на под матрици с размер 3 Х 3, погледнете картинката за по добра представа. Целта на играта е при дадени ни попълнени определен брой квадратчета да запълним останалите квадратчета с цифрите от 1 до 9 като спазваме следните условия: цифрите не трябва да се повтарят във всяка под матрица (една под матрица трябва да се състои от всички цифри от 1 до 9), същото важи за хоризонталите и вертикалите на голямата матрица!
Brute Force – Отговаря напълно на името си – Груба сила. Това е метод при който се ползват всички възможни комбинации за да постигнем целта си (независимо дали става дума за пароли, комбинации, пътища и т.н.). Много бавен метод но пък за сметка на това трудно може нещо да го спре (да не кажем че е невъзможно).
Ето условието на задачата: Problem 2 Sudoku
За решението на задачата реших да използвам рекурсия тъй като е най-логичния и правилен избор при Brute Force метода, ето го и самото решение.
Създал съм 4 метода:
SolveSudoku:
private static void SolveSudoku(int y, int x) { if (y > 8 || solved) { solved = true; return; } else { while (sudoku[y, x] != 0) { if (++x > 8) { x = 0; y++; if (y > 8) { solved = true; return; } } } for (int number = 1; number < 10; number++) { if (CheckY(x, number) && CheckX(y, number) && CheckBox(y, x, number)) { sudoku[y, x] = number; if (x < 8) { SolveSudoku(y, x + 1); } else { SolveSudoku(y + 1, 0); } } } if (solved) { return; } sudoku[y, x] = 0; } }
Този метод се извиква рекурсивно, като всяко следващо извикване е за поредното празно поле (++х докато не попаднем на празно поле или не решим Sudoku-то), докато не запълни и последното поле – условието за това е (y > 8) тъй като увеличаваме „х“ до 8 след което увеличаваме „y“ с едно – следователно след последното поле (8, 8) „y“ ще стане 9 и Sudoku-то ще е решено. Преди да попълним всяко поле с числата от 1 до 9 проверяваме, чрез извикване на методите представени по надолу, дали числото не е в разрез на изискванията на играта. Ако е в разрез с правилата минаваме към следващото число. Ако стигнем до числото 9 и то също не изпълнява условията, зануляваме полето (записваме 0 – което означава че полето е празно) и чрез return се връщаме на предишното поле.
CheckX:
private static bool CheckX(int y, int number) { for (int x = 0; x < 9; x++) { if (sudoku[y, x] == number) { return false; } } return true; }
Чрез този метод проверяваме числото спрямо големия хоризонтал дали отговаря на правилата на играта.
CheckY:
private static bool CheckY(int x, int number) { for (int y = 0; y < 9; y++) { if (sudoku[y, x] == number) { return false; } } return true; }
Чрез този метод проверяваме числото спрямо големия вертикал дали отговаря на правилата на играта.
CheckBox:
private static bool CheckBox(int y, int x, int number) { x = (x / 3) * 3; y = (y / 3) * 3; for (int modY = 0; modY < 3; modY++) { for (int modX = 0; modX < 3; modX++) { if (sudoku[y + modY, x + modX] == number) { return false; } } } return true; }
Чрез този метод проверяваме числото спрямо под матрицата в която се намира дали отговаря на правилата на играта. Тук tricky момента е намирането на границите на под матрицата в която се намира числото, чрез тези две изчисления както сами може да проверите и разберете е много хитро да постигнем това:
x = (x / 3) * 3;
y = (y / 3) * 3;
Останалата част от решението е тривиална – приемане на входните данни и отпечатване на резултата, и не е цел на статията за това няма да я включа в съдържанието и. Ако има въпроси или препоръки, питайте или критикувайте градивно, смело и безотговорно.
Това е от мен за сега, благодаря за вниманието!
14.02.2013г. 22:22 София, България.