Прежде всего, я скажу, что это университетское задание, поэтому я не прошу, чтобы кто-то написал код для меня, мне просто нужно указать правильное направление. :)

Итак, мне нужно написать алгоритм для решения любой (решаемой) доски судоку произвольного размера. Я написал рекурсивную функцию, которая может быстро решить любую доску 9x9 (~ 1 мс), но когда я делаю большие доски (16x16), которые трудно решить, она испытывает трудности ... У меня был один тест, идущий в течение 20 минут, и он может ' Кажется, это решить. Он может решать простые 16x16 головоломки или даже пустую доску 16x16, так что я не думаю, что проблема заключается в размерах ... я думаю, это скорее алгоритм.

Во всяком случае, это основная логика моей программы ..

У меня есть 3D-вектор, который хранит возможные значения каждого моего квадратаКогда значение помещается в квадрат, оно удаляется из возможных значений окружающего квадрата, строки и столбца, в котором оно находится

Тогда моя функция решения в основном:

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there ar,e empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

Есть ли что-то неэффективное в этом? Могу ли я заставить его работать лучше? Я предполагаю, что доска 16x16 занимает так много времени, потому что дерево решений для нее настолько велико для доски, которая заполнена не очень сильно. Это странно, потому что доска 9x9 решит очень быстро.

Любые идеи или предложения были бы абсолютно потрясающими. Если есть какая-то информация, которую я пропустил, дайте мне знать тоже!