我是 C++ 新手,必须做一个家庭作业(数独)。我被困在一个问题上。
问题是要实现解决数独的搜索功能。
说明:为了找到解决方案,递归搜索使用如下。假设有一个尚未分配的带有数字的字段 (d1....dn) (n > 1)。然后我们首先尝试将字段分配给 d1,执行传播,然后继续递归搜索。可能发生的是传播导致失败(字段变为空)。在这种情况下,搜索失败,需要为其中一个字段尝试不同的数字。由于搜索是递归的,因此会尝试最后考虑的字段的下一个数字。如果没有一个数字导致解决方案,则搜索再次失败。这反过来又会导致尝试与前一个字段不同的数字,依此类推。
在通过为其分配字段来尝试数字 d 之前,您必须创建一个新板作为当前板的副本(使用复制构造函数并使用 new 从堆中分配板)。然后才对副本执行分配。如果对搜索的递归调用返回失败,则可以为下一个要尝试的数字创建一个新板。
我试过了:
// 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