研究研究算法--N皇后问题(hdoj2553,附JS和C代码)

零、前言

这道题目据说比较经典,原题是8*8的,我扩展为N*N的了,但是大于10,CPU耗时太大,有其他办法优化。

一、题目

在N*N的方格棋盘放置了N个皇后,使得它们不相互攻击
即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。
你的任务是,对于给定的N,求出有多少种合法的放置方法。

二、分析

由于是N*N的,所以只考虑一个方向就可以了。从第一行到最后一行递归遍历即可。

三、实现

C语言代码:

#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#include "time.h"

int col = 0;
int row = 0;
int printNums = 0;

void put(char ** chessboard_with_flag,char ** chessboard_no_flag,int curcol,int * putways_num);
void printChessboard(char ** chessboard);
char **  setHolder(char ** chessboard,int curcol,int currow);
char ** copyChessboard(char ** chessboard);

int main(int argc, char const *argv[]) {
  int n = 0;
  printf("%s\n", "请输入N值,为保证时间,建议大小1到13:");
  scanf("%d", &n);
  while (n>13 || n<=0) {
      printf("%s\n", "输入错误,请重输:");
      scanf("%d", &n);
  }
  col =n;
  row = n;
  clock_t startTime = clock();
  char ** chessboard_init;
  chessboard_init = malloc(sizeof(char *)*col);
  for(int i=0;i<col;i++){
    chessboard_init[i] = malloc(sizeof(char)*row);
    for(int j=0;j<row;j++){
      chessboard_init[i][j]='0';
    }
  }
  int putways_num = 0;
  put(chessboard_init,copyChessboard(chessboard_init),0,&putways_num);
  printf("共有%d种放置方法\n", putways_num);
  printf("%d*%d C语言计算所花费的时间为 %lu ms\n",col,row, clock()/1000 - startTime/1000);

  return 0;
}

// 在curcol行放置棋子
// chessboard : 当前棋盘状态,是否可放置,带标记
// chessboard_no_flag : 干净的棋盘
void put(char ** chessboard,char ** chessboard_no_flag,int curcol,int * putways_num){
  // 如果最后一行都已经被放置了,说明这是一种可行的放置方法,方法数目+1
  if(curcol==col){
    (*putways_num)++;
    printChessboard(chessboard_no_flag);
  }
  if(curcol<0 || curcol>=col){
    return;
  }

  char ** chessboard_temp = copyChessboard(chessboard);
  for(int i=0;i<row;i++){
    char curstatus = chessboard_temp[curcol][i];
    if(curstatus == '0'){
      // 可放置,则置为1,表示已放置
      char ** chessboard_no_flag_temp = copyChessboard(chessboard_no_flag);
      chessboard_no_flag_temp[curcol][i] = '1';
      char ** chessboard_after_put = setHolder(chessboard_temp,curcol,i);
      put(chessboard_after_put,chessboard_no_flag_temp,curcol+1,putways_num);
    }
  }
}
// 打印棋盘
void printChessboard(char ** chessboard){
  printf("第%d种:\n", ++printNums);
  for(int i=0;i<col;i++){
    for(int j=0;j<row;j++){
      printf("%c  ", chessboard[i][j]);
    }
    printf("\n");
  }
}
// 根据某个点设置每行每列每个对角线的占位
char ** setHolder(char ** chessboard,int curcol,int currow){
  char ** chessboard_temp = copyChessboard(chessboard);
  for(int i=0;i<col;i++){
    for(int j=0;j<row;j++){
      if(i==curcol || j==currow || (abs(i - curcol) == abs(j-currow)) ){
        chessboard_temp[i][j] = '1';
      }
    }
  }
  return chessboard_temp;
}
// 复制一个新的棋盘
char ** copyChessboard(char ** chessboard){
  char ** chessboard_temp = malloc(sizeof(char*)*col);
  for(int j=0;j<col;j++){
    chessboard_temp[j] = malloc(sizeof(char)*row);
    strcpy(chessboard_temp[j],chessboard[j]);
  }
  return chessboard_temp;
}

上面代码拆分得比较清楚了,比较好理解。不做过多解释。

为了满足JS开发者,依样画瓢,写了个JS版本的。

JS实现:

var col = 8;
var row = 8;
var printNums = 0;
var putways_num = 0;

main(8);

function main(n) {
  col = row = n;
  var startTime = Date.now();
  var chessboard_init = [];
  for(var i=0;i<col;i++){
    chessboard_init[i] = [];
    for(var j=0;j<row;j++){
      chessboard_init[i][j]='0';
    }
  }
  put(chessboard_init,copyChessboard(chessboard_init),0);
  console.log(`共有${putways_num}种放置方法\n`);
  console.log(`${col}*${row}`,`JS计算所花费的时间为 ${Date.now() - startTime} ms\n`);

  return 0;
}

// chessboard : 当前棋盘状态,是否可放置,带标记
// chessboard_no_flag : 干净的棋盘
function put(chessboard,chessboard_no_flag,curcol){

  if(curcol==col){
    (putways_num)++;
    printChessboard(chessboard_no_flag);
  }
  if(curcol<0 || curcol>=col){
    return;
  }
  var chessboard_temp = copyChessboard(chessboard);
  for(var i=0;i<row;i++){
    var curstatus = chessboard_temp[curcol][i];
    if(curstatus == '0'){
      // 可放置,则置为1,表示已放置
      var chessboard_no_flag_temp = copyChessboard(chessboard_no_flag);
      chessboard_no_flag_temp[curcol][i] = '1';
      var chessboard_after_put = setHolder(chessboard_temp,curcol,i);
      put(chessboard_after_put,chessboard_no_flag_temp,curcol+1,putways_num);
    }
  }
}

function printChessboard(chessboard){
  console.log(`第${++printNums}种:`);
  var res = "";
  for(var i=0;i<col;i++){
    for(var j=0;j<row;j++){
      res +=" "+ chessboard[i][j];
    }
    res += "\n";
  }
  console.log(res);
}

function setHolder(chessboard, curcol, currow){
  var chessboard_temp = copyChessboard(chessboard);
  for(var i=0;i<col;i++){
    for(var j=0;j<row;j++){
      if(i==curcol || j==currow || (Math.abs(i - curcol) == Math.abs(j-currow)) ){
        chessboard_temp[i][j] = '1';
      }
    }
  }
  return chessboard_temp;
}

function copyChessboard(chessboard){
  var chessboard_temp = [];
  for(var j=0;j<col;j++){
    chessboard_temp[j] = [];
    for(var i=0;i<row;i++){
      chessboard_temp[j][i] = chessboard[j][i];
    }
  }
  return chessboard_temp;
}

把上面JS代码,复制粘贴到浏览器调试窗就行了。注:最好是chrome。

四、测试

C代码测试:

gcc hdoj2553.c -o out
...
共有92种放置方法
8*8 C语言计算所花费的时间为 10 ms

JS代码测试:

...
共有92种放置方法
8*8 JS计算所花费的时间为 64 ms

为什么JS不适合用来计算,这里也可见一斑。

五、总结

C语言代码中,要注意的就是二重指针需要分别申请存储空间。JS就无所谓了。

这道题,网上有一种使用二进制进行的计算,效率相当的高。感兴趣的朋友可以搜索一下。

本文完



打赏作者

发表评论

电子邮件地址不会被公开。 必填项已用*标注