C ++ - решить игру судоку

Question

Я новичок в C ++ и должен выполнить домашнее задание (судоку).Я застрял в проблеме.

Проблема в том, чтобы реализовать функцию поиска, которая решает судоку.

Инструкция: Для поиска решения используется рекурсивный поиск следующим образом.Предположим, что есть еще не назначенное поле с цифрами (d1 .... dn) (n> 1).Затем мы сначала пытаемся присвоить поле d1, выполнить распространение, а затем продолжить рекурсивный поиск.Может случиться так, что распространение приведет к сбою (поле станет пустым).В этом случае поиск завершается неудачно, и для одного из полей необходимо использовать разные цифры.Поскольку поиск является рекурсивным, пробуется следующая цифра для поля, которое считается последним.Если ни одна из цифр не приводит к решению, поиск снова заканчивается неудачей.Это, в свою очередь, приведет к попытке использовать цифру, отличную от предыдущего поля, и т. Д.

Прежде чем использовать цифру d, назначив ей поле, необходимо создать новую доску, являющуюся копиейтекущая доска (используйте конструктор копирования и выделите доску из кучи с новой).Только тогда выполните задание на копии.Если рекурсивный вызов для поиска завершается неудачно, можно создать новую доску для следующей цифры, которую нужно попробовать.

Я пробовал:

// Search for a solution, returns NULL if no solution found
Board* Board::search(void) {
    // create a copy of the cur. board
    Board *copyBoard = new Board(*this);
    Board b = *copyBoard;

    for(int i = 0; i < 9; i++){
        for(int j = 0; j < 9; j++){

              //  if the field has not been assigned, assign it with a digit 
            if(!b.fs[i][j].assigned()){
                digit d = 1;

                     // try another digit if failed to assign (1 to 9)
                while (d <=9 && b.assign(i, j, d) == false){
                        d++;


                      // if no digit matches, here is the problem, how to 
                      // get back to the previous field and try another digit?
                      // and return null if there's no pervious field 
                if(d == 10){
                      ...
                    return NULL;
                }
            }
        }
    }
    return copyBoard;
 }

Другая проблема заключается в том, где использоватьрекурсивный вызов?Какие-нибудь советы?спасибо!

Полная инструкция может быть найдена здесь: http://www.kth.se/polopoly_fs/1.136980!/Menu/general/column-content/attachment/2-2.pdf

Код: http://www.kth.se/polopoly_fs/1.136981!/Menu/general/column-content/attachment/2-2.zip

Answer 1

В вашем коде нет рекурсии. Вы не можете просто посетить каждое поле один раз и попытаться присвоить ему значение. Проблема в том, что вы можете назначить, скажем, 5 для поля (3,4), и только в том случае, если вы дойдете до поля (6,4), окажется, что не может быть 5 в (3 4). В конце концов вам нужно выйти из рекурсии, пока вы не вернетесь к (3,4) и не попробуете другое значение там.

С рекурсией вы можете не использовать вложенные циклы for для посещения полей, а посетить следующее поле с рекурсивным вызовом. Либо вам удастся добраться до последнего поля, либо вы попробуете все возможности и затем выйдите из функции, чтобы вернуться к предыдущему полю, которое вы посетили.

---

Sidenote: определенно не выделяйте динамическую память для этой задачи:

//Board *copyBoard = new Board(*this);
Board copyBoard(*this); //if you need a copy in the first place

Answer 2

В основном вы можете попробовать что-то вроде этого (pseudocode'ish)

bool searchSolution(Board board)
{
 Square sq = getEmptySquare(board)
 if(sq == null)
    return true; // no more empty squares means we solved the puzzle

 // otherwise brute force by trying all valid numbers
 foreach (valid nr for sq)
 {
    board.doMove(nr)

    // recurse
    if(searchSolution(board))
        return true

    board.undoMove(nr) // backtrack if no solution found
 }

 // if we reach this point, no valid solution was found and the puzzle is unsolvable
 return false;

}

Функция getEmptySquare (...) может возвращать случайный пустой квадрат или квадрат с наименьшим количеством оставшихся опций,Использование последнего сделает алгоритм сходящимся намного быстрее.