Судоку алгоритм отступания ⇐ C++

[Anonymous]

Во -первых, я утверждаю, что это университетское задание, поэтому я не прошу кого -то написать код для меня, мне просто нужно указать в правильном направлении. < /p>

ОК, поэтому мне нужно написать алгоритм для решения любого (решаемого) Совета произвольного размера Судоку. Я написал рекурсивную функцию, которая может быстро решить любую плату 9x9 (~ 1 мс), но когда я делаю большие платы (16x16), которые трудно решить ее. Кажется, решает это. Это может решить простые головоломки 16x16 или даже пустую доску 16x16, так что я не думаю, что это проблема. Br /> В любом случае, это основная логика моей программы. из мой каждый квадратный < /li>
Когда значение помещается в квадрат, оно удаляется из возможных значений окружающего квадрата, строки и столбца, которые он находится в < /li>
< /ul>

Тогда моя решающая функция в основном: < /p>

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 are 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
}
< /code>

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

Подробнее здесь: https://stackoverflow.com/questions/769 ... -algorithm