Problem B: 算法实验8-2 回溯算法-着色问题
Time Limit: 1 Sec Memory Limit: 128 MBSubmit: 1078 Solved: 651
[Submit] [Status] [Web Board] [Creator:]
Description
四色定理：任何一个平面地图可以用不超过四种颜色进行着色， 使得拥有同一边界线的国家着不同的颜色。
现要求用不超过 4 种颜色对七巧板着色，使得相邻板块颜色不同， 设计回溯算法打印输出不同的颜色方案。
tle="" align="" />
【算法设计】
七巧板转换为邻接矩阵，四种颜色用数字1、 2、 3、 4表示。
【参考程序】
现要求用不超过 4 种颜色对七巧板着色，使得相邻板块颜色不同， 设计回溯算法打印输出不同的颜色方案。
tle="" align="" />【算法设计】
七巧板转换为邻接矩阵，四种颜色用数字1、 2、 3、 4表示。
【参考程序】
#include <stdio.h>
int total=0;
int color[8];
int data[8][8]={{0,0,0,0,0,0,0,0},{0,0,1,0,0,1,0,1},{0,1,0,0,1,0,1,0},{0,0,0,0,0,0,1,1},{0,0,1,0,0,0,1,1},{0,1,0,0,0,0,0,1},{0,0,1,1,1,0,0,0},{0,1,0,1,1,1,0,0}};
int colorsame(int s)
{
int i,flag;
flag=0;
for(i=1;i<=s-1;i++)
if(data[i][s]==1 && color[i]==color[s])
flag=1;
return flag;
}
void output()
{
int i;
for(i=1;i<=7;i++)
printf("%d",color[i]);
printf("\n");
total++;
}
void trypaint(int s)
{
int i;
if(s>7)
{ 省略...... } //输出可行解
else
{
// 搜索尝试不同的着色
省略......
}
}
int main()
{
int i;
for(i=0;i<=7;i++)
color[i]=0;
total=0;
trypaint(1);
printf("Total=%d\n",total);
}
Input
无
Output
输出所有可行的着色方案和总方案数。
Sample Output Copy
1211233
1211234
1211243
1211244
1211332
1211334
1211342
1211344
1211432
1211433
1211442
1211443
1213244
1213342
1213344
1213442
1214233
1214332
1214432
1214433
1221233
1221234
1221243
1221244
1221334
1221344
1221433
1221443
1223214
1223244
1223314
1223344
1224213
1224233
1224413
1224433
1231244
1231342
1231344
1231442
1233214
1233244
1233312
1233314
1233342
1233344
1233412
1233442
1234312
1234412
1241233
1241332
1241432
1241433
1243312
1243412
1244213
1244233
1244312
1244332
1244412
1244413
1244432
1244433
1311223
1311224
1311243
1311244
1311322
1311324
1311342
1311344
1311422
1311423
1311442
1311443
1312243
1312244
1312344
1312443
1314223
1314322
1314422
1314423
1321243
1321244
1321344
1321443
1322213
1322214
1322243
1322244
1322314
1322344
1322413
1322443
1324213
1324413
1331224
1331244
1331322
1331324
1331342
1331344
1331422
1331442
1332214
1332244
1332314
1332344
1334312
1334322
1334412
1334422
1341223
1341322
1341422
1341423
1342213
1342413
1344213
1344223
1344312
1344322
1344412
1344413
1344422
1344423
1411223
1411224
1411233
1411234
1411322
1411324
1411332
1411334
1411422
1411423
1411432
1411433
1412233
1412234
1412334
1412433
1413224
1413322
1413324
1413422
1421233
1421234
1421334
1421433
1422213
1422214
1422233
1422234
1422314
1422334
1422413
1422433
1423214
1423314
1431224
1431322
1431324
1431422
1432214
1432314
1433214
1433224
1433312
1433314
1433322
1433324
1433412
1433422
1441223
1441233
1441322
1441332
1441422
1441423
1441432
1441433
1442213
1442233
1442413
1442433
1443312
1443322
1443412
1443422
2112133
2112134
2112143
2112144
2112334
2112344
2112433
2112443
2113124
2113144
2113324
2113344
2114123
2114133
2114423
2114433
2122133
2122134
2122143
2122144
2122331
2122334
2122341
2122344
2122431
2122433
2122441
2122443
2123144
2123341
2123344
2123441
2124133
2124331
2124431
2124433
2132144
2132341
2132344
2132441
2133124
2133144
2133321
2133324
2133341
2133344
2133421
2133441
2134321
2134421
2142133
2142331
2142431
2142433
2143321
2143421
2144123
2144133
2144321
2144331
2144421
2144423
2144431
2144433
2311123
2311124
2311143
2311144
2311324
2311344
2311423
2311443
2312143
2312144
2312344
2312443
2314123
2314423
2321143
2321144
2321344
2321443
2322113
2322114
2322143
2322144
2322311
2322314
2322341
2322344
2322411
2322413
2322441
2322443
2324113
2324311
2324411
2324413
2331124
2331144
2331324
2331344
2332114
2332144
2332311
2332314
2332341
2332344
2332411
2332441
2334311
2334321
2334411
2334421
2341123
2341423
2342113
2342311
2342411
2342413
2344113
2344123
2344311
2344321
2344411
2344413
2344421
2344423
2411123
2411124
2411133
2411134
2411324
2411334
2411423
2411433
2412133
2412134
2412334
2412433
2413124
2413324
2421133
2421134
2421334
2421433
2422113
2422114
2422133
2422134
2422311
2422314
2422331
2422334
2422411
2422413
2422431
2422433
2423114
2423311
2423314
2423411
2431124
2431324
2432114
2432311
2432314
2432411
2433114
2433124
2433311
2433314
2433321
2433324
2433411
2433421
2441123
2441133
2441423
2441433
2442113
2442133
2442311
2442331
2442411
2442413
2442431
2442433
2443311
2443321
2443411
2443421
3112134
3112144
3112234
3112244
3113122
3113124
3113142
3113144
3113224
3113244
3113422
3113442
3114122
3114132
3114422
3114432
3122134
3122144
3122231
3122234
3122241
3122244
3122431
3122441
3123144
3123241
3123244
3123441
3124231
3124431
3132144
3132241
3132244
3132441
3133122
3133124
3133142
3133144
3133221
3133224
3133241
3133244
3133421
3133422
3133441
3133442
3134122
3134221
3134421
3134422
3142231
3142431
3143122
3143221
3143421
3143422
3144122
3144132
3144221
3144231
3144421
3144422
3144431
3144432
3211132
3211134
3211142
3211144
3211234
3211244
3211432
3211442
3213142
3213144
3213244
3213442
3214132
3214432
3221134
3221144
3221234
3221244
3223114
3223144
3223211
3223214
3223241
3223244
3223411
3223441
3224211
3224231
3224411
3224431
3231142
3231144
3231244
3231442
3233112
3233114
3233142
3233144
3233211
3233214
3233241
3233244
3233411
3233412
3233441
3233442
3234112
3234211
3234411
3234412
3241132
3241432
3243112
3243211
3243411
3243412
3244112
3244132
3244211
3244231
3244411
3244412
3244431
3244432
3411122
3411124
3411132
3411134
3411224
3411234
3411422
3411432
3412134
3412234
3413122
3413124
3413224
3413422
3421134
3421234
3422114
3422134
3422211
3422214
3422231
3422234
3422411
3422431
3423114
3423211
3423214
3423411
3431122
3431124
3431224
3431422
3432114
3432211
3432214
3432411
3433112
3433114
3433122
3433124
3433211
3433214
3433221
3433224
3433411
3433412
3433421
3433422
3441122
3441132
3441422
3441432
3442211
3442231
3442411
3442431
3443112
3443122
3443211
3443221
3443411
3443412
3443421
3443422
4112133
4112143
4112233
4112243
4113122
4113142
4113322
4113342
4114122
4114123
4114132
4114133
4114223
4114233
4114322
4114332
4122133
4122143
4122231
4122233
4122241
4122243
4122331
4122341
4123241
4123341
4124133
4124231
4124233
4124331
4132241
4132341
4133122
4133142
4133221
4133241
4133321
4133322
4133341
4133342
4134122
4134221
4134321
4134322
4142133
4142231
4142233
4142331
4143122
4143221
4143321
4143322
4144122
4144123
4144132
4144133
4144221
4144223
4144231
4144233
4144321
4144322
4144331
4144332
4211132
4211133
4211142
4211143
4211233
4211243
4211332
4211342
4213142
4213342
4214132
4214133
4214233
4214332
4221133
4221143
4221233
4221243
4223211
4223241
4223311
4223341
4224113
4224133
4224211
4224213
4224231
4224233
4224311
4224331
4231142
4231342
4233112
4233142
4233211
4233241
4233311
4233312
4233341
4233342
4234112
4234211
4234311
4234312
4241132
4241133
4241233
4241332
4243112
4243211
4243311
4243312
4244112
4244113
4244132
4244133
4244211
4244213
4244231
4244233
4244311
4244312
4244331
4244332
4311122
4311123
4311142
4311143
4311223
4311243
4311322
4311342
4312143
4312243
4314122
4314123
4314223
4314322
4321143
4321243
4322113
4322143
4322211
4322213
4322241
4322243
4322311
4322341
4324113
4324211
4324213
4324311
4331122
4331142
4331322
4331342
4332211
4332241
4332311
4332341
4334112
4334122
4334211
4334221
4334311
4334312
4334321
4334322
4341122
4341123
4341223
4341322
4342113
4342211
4342213
4342311
4344112
4344113
4344122
4344123
4344211
4344213
4344221
4344223
4344311
4344312
4344321
4344322
Total=768