你学到什么程度了,八皇后问题的回溯算法,看的懂吗。这跟那个是一个道理 。
最直接的方法,先把1-9填进去,不满足再回溯。
还有一个直接的方法,只对奇数平方宫有效,
按顺序位次写1~9
先是第一行中间, 然后是左上角,如果左上角出格,则把列再构一次,如果左上角有数的,则把数字写在对自己的下面。
像1~9的,
就是
x 1 x
x x x
x x x
然后1的左上角,出格,则把第三列,拉到最上面,
x 1 x
x x x
x x 2
然后2的左上角,出格,把第一列,拉到最右边
x 1 x
3 x x
x x 2
然后3的左上角有数,则把数字写在3的下面.
x 1 x
3 x x
4 x 2
其余的按上面规律写,结果是
8 1 6
3 5 7
4 9 2
写了一个回溯的,把所有情况都列出来了,没有剪枝。
#include <iostream>
using namespace std;
const int nrow = 3;
const int nlin = 3;
int a[nrow][nlin];
int visit[nrow * nlin + 1] = {0};
void solve(int i, int j, int visit[]) //表示第i行第j列填k, visit标志是否被选中
{
//结束,判断是否符合
if( i == nrow)
{
// 列,行
int nSumLine = 0;
for(int k = 0; k < nrow; k ++)
{
//列
int nTmpLin = a[0][k] + a[1][k] + a[2][k];
//行
int nTmpRow = a[k][0] + a[k][1] + a[k][2];
// 列 != 行
if(nTmpRow != nTmpLin)
return;
if(nSumLine == 0)
nSumLine = nTmpLin;
else
{
// 行不等或者列不等
if(nTmpLin != nSumLine || nTmpRow != nSumLine)
return;
}
}
//对角线
int nSumDia1 = a[0][0] + a[1][1] + a[2][2];
int nSumDia2 = a[0][2] + a[1][1] + a[2][0];
if(nSumDia2 != nSumDia1 || nSumDia1 != nSumLine)
return;
//符合情况
for(int i = 0; i < nrow; i ++)
{
for(int j = 0; j < nlin; j++)
{
cout << a[i][j] << " ";
}
cout << endl;
}
cout << endl;
return;
}
if(j == nlin)
return solve(i + 1, 0, visit);
for(int k= 1; k < 10; k ++)
{
if(visit[k] == 0)
{
visit[k] = 1;
a[i][j] = k;
solve(i, j + 1, visit);
visit[k] = 0;
}
}
}
int main()
{
solve(0, 0, visit);
return 0;
}
追问你的代码看不懂。
能不能只用if else 语句写出来。今天老师做出来大概都是if else 语句,没有return这些。
追答#include <iostream>
using namespace std;
int main()
{
int a[3][3] = {0};
int i, j, k;
for(i = 0, j = 1 ,k = 1; k < 10; k ++)
{
if(a[i][j] == 0)
a[i][j] = k;
int ansi = i;
int ansj = j;
i = i - 1;
j = j + 1;
if( i < 0 )
i = 2;
if( j > 2)
j = 0;
if(a[i][j] != 0)
{
i = ansi + 1;
j = ansj;
}
}
for(int i = 0; i < 3; i ++)
{
for(int j = 0; j < 3;j ++)
cout << a[i][j] << " ";
cout << endl;
}
return 0;
}