用js写了一个解数独的算法,使用舞蹈链算法,目前已知最快的方法,js里面1ms可以解出来,封装成aardio后需要15ms,速度有点慢,有没有大佬出手把js代码翻译成aardio代码,我失败了,没有成功![](https://aardio.online/upload/files/20240625/1719279619.gif)
用法
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); // 恢复其他相关的约束条件
}
}
}
}