При подготовката ми за изпит номер 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 София, България.