封装一个js解数独的库

qiufuxing 5月前 510

用js写了一个解数独的算法,使用舞蹈链算法,目前已知最快的方法,js里面1ms可以解出来,封装成aardio后需要15ms,速度有点慢,有没有大佬出手把js代码翻译成aardio代码,我失败了,没有成功


用法

import console; 
import qiufuxing.dlx

var dlx = qiufuxing.dlx()
var answer = dlx.solution(".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7...")
console.dump(answer);

console.pause(true);


aardio代码:

//dlx
//舞蹈链算法

/*****
	1.0 	初步封装
*****/
import web.script;
namespace qiufuxing;
class dlx {
	solution = function(str){
		var grid = this.stringToGrid(str)
		return _vm.json.getAnswer(grid); 
	};
	
	grid81 = function(str){
		var answer = this.solution(str)
		return ..string.split(answer); 
	};
	
	//辅助函数,将字符串转为二维数组
	stringToGrid = function(str){
    	var grid = {{}, {}, {}, {}, {}, {}, {}, {}, {}}; // 创建一个9x9的空二维数组grid
    	var temp = ..string.split(str) // 通过string.split将输入的str字符串转换为数组temp
		
    	// 循环遍历1到9的行
    	for(i=1;9;1){
        	// 循环遍历1到9的列
        	for(j=1;9;1){
            	var pos = (i-1)*9 + j // 计算当前位置在一维数组temp中的索引
            	// 如果temp[pos]为".",则在grid中将对应位置值设为0,否则转换为数字后存入grid
            	if(temp[pos] == "."){
                	grid[i][j] = 0
            	}
            	else {
                	grid[i][j] = tonumber(temp[pos])
            	}
        	}
    	}
    	
    	return grid; // 返回转换后的grid
	};
	
}
namespace dlx {
	_vm = ..web.script("ES6");
	_vm.addCode($"~/lib/qiufuxing/dlx/dlx.js");
}


js代码

function getAnswer(sudoku) {
    solutions = solveSudoku(sudoku);
    return solutions;
};

// 定义一个函数 solveSudoku,用于求解数独问题
function solveSudoku(grid) {
  const size = 9; // 数独的大小是9x9
  const boxSize = Math.sqrt(size); // 每个小方块的大小是3x3
  const X = {}; // 用于存储约束条件
  const Y = {}; // 用于存储解的选择

  // 初始化 X 和 Y
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      for (let n = 1; n <= size; n++) {
        const b = Math.floor(i / boxSize) * boxSize + Math.floor(j / boxSize); // 计算小方块的索引
        const rc = `rc${i}${j}`; // 行列约束
        const rn = `rn${i}${n}`; // 行数字约束
        const cn = `cn${j}${n}`; // 列数字约束
        const bn = `bn${b}${n}`; // 方块数字约束
        const key = `${i}${j}${n}`; // 唯一键

        // 初始化 X 中的集合
        X[rc] = X[rc] || new Set();
        X[rn] = X[rn] || new Set();
        X[cn] = X[cn] || new Set();
        X[bn] = X[bn] || new Set();

        // 向 X 中添加约束
        X[rc].add(key);
        X[rn].add(key);
        X[cn].add(key);
        X[bn].add(key);

        // 向 Y 中添加选择
        Y[key] = [rc, rn, cn, bn];
      }
    }
  }

  // 处理已知的数独格子
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      const n = grid[i][j];
      if (n) {
        select(X, Y, `${i}${j}${n}`);
      }
    }
  }

  // 求解数独
  const solutions = solve(X, Y);

 //将数独解转化为字符串形式
  const newGrid = JSON.parse(JSON.stringify(grid)); // 深拷贝原始网格
  solutions[0].forEach((key) => {
    const i = parseInt(key.charAt(0));
    const j = parseInt(key.charAt(1));
    const n = parseInt(key.charAt(2));
    newGrid[i][j] = n; // 填入数独解
  });
  let str = "";
  for (let i = 0; i < size; i++) {
    for (let j = 0; j < size; j++) {
      str += newGrid[i][j];
    }
  }
  return str;
}

// 递归求解函数
function solve(X, Y, solution = []) {
  if (Object.keys(X).length === 0) {
    // 如果没有剩余的约束条件,返回当前解
    return [solution.slice()];
  } else {
    // 选择具有最少选择项的约束条件
    let c = Object.keys(X).reduce((a, b) => (X[a].size < X[b].size ? a : b));
    let results = [];
    // 遍历选择项
    for (let r of Array.from(X[c])) {
      solution.push(r); // 将选择项添加到解中
      let cols = select(X, Y, r); // 更新约束条件
      results.push(...solve(X, Y, solution)); // 递归求解
      deselect(X, Y, r, cols); // 恢复约束条件
      solution.pop(); // 从解中移除选择项
    }
    return results; // 返回所有解
  }
}

// 选择函数,用于更新约束条件
function select(X, Y, r) {
  let cols = [];
  for (let j of Y[r]) {
    for (let i of Array.from(X[j])) {
      for (let k of Y[i]) {
        if (k !== j) X[k].delete(i); // 更新其他相关的约束条件
      }
    }
    cols.push(X[j]);
    delete X[j];
  }
  return cols;
}

// 取消选择函数,用于恢复约束条件
function deselect(X, Y, r, cols) {
  for (let j of Y[r].slice().reverse()) {
    X[j] = cols.pop();
    for (let i of Array.from(X[j])) {
      for (let k of Y[i]) {
        if (k !== j) X[k].add(i); // 恢复其他相关的约束条件
      }
    }
  }
}


上传的附件:
最新回复 (3)
  • 光庆 5月前
    0 2
    没有测试代码,别人不会用。
  • qiufuxing 5月前
    0 3
    光庆 没有测试代码,别人不会用。
    已更新范例,附件是5万个最难的17数数独
  • 光庆 5月前
    0 4
    qiufuxing 已更新范例,附件是5万个最难的17数数独

    把js代码翻译成aardio代码,我估计这活没人愿意干。

返回