【算法大神进】用aardio实现了精确覆盖问题的算法,但是算法遇到了一些问题,大佬能出手帮忙调试一下算法吗

qiufuxing 1月前 200

精确覆盖算法如下,这个测试是正常的,但是改成解数独,大部分题目能正常解出来,少部分解不出来,求算法大神出手!

 import console; 

//精确覆盖问题是指,给定一个集合{1,2,3,4,5,6,7},以及若干个子集
//"A" = {"2", "6"};"B" = {"4", "5", "6"};"C" = {"2", "3", "7"};"D" = {"1", "4", "7"};"E" = {"1", "4"};"F" = {"3", "5", "7"};
//找出若干个子集刚好覆盖住给定的集合{1,2,3,4,5,6,7},比如"A" = {"2", "6"}、"E" = {"1", "4"}、"F" = {"3", "5", "7"}就是一组解
//https://oi-wiki.org/search/dlx/
//https://blog.csdn.net/whereisherofrom/article/details/79220897
//DLX算法是使用双向十字链表,数据结构太过麻烦,我们使用哈希表代替即可,根据给定的集合Y,构造集合X,通过哈希表直接代替双向十字链表的删除和恢复,
//数据结构上更加简单

//第一组测试数据
X = {
	"1" = {"D", "E"};
	"2" = {"A", "C"};
	"3" = {"C", "F"};
	"4" = {"B", "D", "E"};
	"5" = {"B", "F"};
	"6" = {"A", "B"};
	"7" = {"C", "D", "F"};
}

Y = {
	"A" = {"2", "6"};
	"B" = {"4", "5", "6"};
	"C" = {"2", "3", "7"};
	"D" = {"1", "4", "7"};
	"E" = {"1", "4"};
	"F" = {"3", "5", "7"};
}

//第二组测试数据
X = {
	"1" = {"A", "B"};
	"2" = {"E", "F", "G"};
	"3" = {"D", "E"};
	"4" = {"A", "B", "C"};
	"5" = {"C", "D"};
	"6" = {"D", "E"};
	"7" = {"A", "C", "E", "F", "G"};
}

Y = {
	"A" = {"1", "4", "7"};
	"B" = {"1", "4"};
	"C" = {"4", "5", "7"};
	"D" = {"3", "5", "6"};
	"E" = {"2", "3", "6", "7"};
	"F" = {"2", "7"};
	"G" = {"2", "7"};
}

//辅助函数,返回哈希表键值对的数量
hashCount = function(tab){
	var count = 0
	for(k,v in tab){
		count++
	}
	return count; 
}

//辅助函数,返回一个哈希表中,长度最小的键值对的索引
findShortest = function(tab){
	var count = 9
	var result = ""
	for(k,v in tab){
		if(#v != 0 and #v <= count){
			result = k
			count = #v
		}
	}
	return result; 
}

var count = 0;
var loop = 0;

//递归求解
// 定义一个名为solve的函数
// 该函数接受三个参数:X,Y和solution
function solve(X, Y, solution){
	count++;
	console.dump("第"++count++"次递归");
	console.dump("hashCount(X):"++hashCount(X));
	if(hashCount(X) == 0){  // 如果X的哈希计数为0
  		return table.slice(solution);  // 返回solution的切片
	}
	else {  // 否则
  		var c = findShortest(X)  // 寻找X中最短的元素并赋值给c
  		var result = {};  // 声明一个空对象result
  		
  		for(k,v in X[c]){  // 遍历X[c]中的键值对
  			loop++;
  			console.dump("第"++loop++"次循环");
  			
   			table.push(solution, v)  // 将v添加到solution中
   			console.dump("v:", v, "X中最小的列:", c, "solution:", solution, "删除前的X:", X);
   			
   			var cols = xselect(X, Y, v);  // 调用xselect函数,并将返回值赋值给cols
   			console.dump("删除后的X:", X);
   			
   			table.push(result, solve(X, Y, solution))  // 将solve(X, Y, solution)的返回值添加到result中
   			console.dump("result:", result);
   			
   			deselect(X, Y, v, cols)  // 调用deselect函数,传入X、Y、v和cols作为参数
   			console.dump("恢复的X:", X);
   			
   			table.pop(solution)  // 从solution中弹出最后一个元素
   			console.dump("solution:", solution);
  		}
  		
  		return result;   // 返回result
 	}
}

//删除
// 定义一个名为xselect的函数,接受三个参数X、Y、r
xselect = function(X, Y, r){
	var cols = {}; // 创建一个空的cols对象
	for(k,v in Y[r]){ // 遍历Y[r]中的键值对
		for(k2,v2 in X[v]){ // 遍历X[v]中的键值对
			for(k3,v3 in Y[v2]){ // 遍历Y[v2]中的键值对
				if(v3 != v){ // 如果v3不等于v,则从X[v3]中移除v2
					table.removeByValue(X[v3], v2)
				}
			}
		}
		
		table.push(cols, X[v]); // 将X[v]添加到cols中
		X[v] = null // 将X[v]设置为null
	}
    
	return cols; // 返回cols
}


//恢复
// 定义一个名为deselect的函数,接受四个参数X、Y、r、cols
deselect = function(X, Y, r, cols){
    table.reverse(Y[r]) // 反转Y[r]
	
	for(k,v in Y[r]){ // 遍历Y[r]中的键值对
		X[v] = table.pop(cols) // 从cols中弹出一个元素,并将其赋值给X[v]
		for(k2,v2 in X[v]){ // 遍历X[v]中的键值对
			for(k3,v3 in Y[v2]){ // 遍历Y[v2]中的键值对
				if(v3 != v){ // 如果v3不等于v,则将v2添加到X[v3]中
					table.push(X[v3], v2)
				}
			}
		}
	}
}

var result = solve(X, Y, {})
console.dump("result:", result);

console.pause(true);


精确覆盖解数独的算法:

import console; 

//核心函数只有4个
//第一个solveSudoku(grid)负责将grid转为约束条件X、Y,并调用solve()函数求解
//第二个solve()递归解决精确覆盖问题
//第三个xselect()删除相关的行列
//第四个deselect()恢复相关的行列

// 定义一个名为solveSudoku的函数,接受一个参数grid
solveSudoku = function(grid){ 
	var answer = table.clone(grid) // 克隆输入的grid并赋值给answer

	var X = {}; // 创建空的X对象
	var Y = {}; // 创建空的Y对象
	
    // 构建X和Y对象
	for(i=1;9;1){
		for(j=1;9;1){
			for(n=1;9;1){
				var b = ..math.floor((i-1)/3)*3 + ..math.floor((j-1)/3) + 1 // 计算当前单元格所在宫的索引b
				// 生成行-列-数字对应的键
				var rc = ..string.format("%s%s%s", "rc", i, j);
				var rn = ..string.format("%s%s%s", "rn", i, n);
				var cn = ..string.format("%s%s%s", "cn", j, n);
				var bn = ..string.format("%s%s%s", "bn", b, n);
				var key = ..string.format("%s%s%s", i, j, n);
				
				// 初始化X对象中对应的属性
				X[rc] = X[rc] || {};
				X[rn] = X[rn] || {};
				X[cn] = X[cn] || {};
				X[bn] = X[bn] || {};
				
				// 将key添加到X对应属性的值中
				..table.push(X[rc], key);
				..table.push(X[rn], key);
				..table.push(X[cn], key);
				..table.push(X[bn], key);
				
				// 将key对应的行、列、宫信息添加到Y对象中
				Y[key] = {rc, rn, cn, bn};
			}
		}
	}
	//console.dump(X);
    // 遍历输入的grid
	for(i=1;9;1){
		for(j=1;9;1){ 
			var n = grid[i][j] // 获取当前位置的数字n
			var key = ..string.format("%s%s%s", i, j, n); // 生成对应的键key
			// 如果n不为零,则执行xselect操作
			if(n){
				xselect(X, Y, key)
			}
		}
	}

    console.dump(Y);
	var solutions = solve(X, Y, {}) // 调用solve函数求解数独
	
    // 如果存在解决方案
/*
	if(solutions){
        // 将解决方案应用到answer中
		for(k,v in solutions){
			var temp = string.split(v)
			var i = tonumber(temp[1])
			var j = tonumber(temp[2])
			var n = tonumber(temp[3])
			answer[i][j] = n
		}
	}
*/
	
	var str = GridToString(answer)

	return solutions, answer, str; // 返回解决方案和answer
}

var count = 0;
var loop = 0;
// 定义一个名为solve的函数,接受四个参数X、Y、solution、result
solve = function(X, Y, solution){
	count++;
	console.dump("第"++count++"次递归");
	console.dump("hashCount(X):"++hashCount(X));
    // 如果X中的元素数量为0,即已经没有需要处理的元素,返回solution的副本
    if(hashCount(X) == 0){
        return table.slice(solution); 
    }
    else {  
        var c = findShortest(X) // 找到X中剩余元素最少的列c
        var result = {}
		
        // 遍历X[c]中的元素
        for(k,v in X[c]){
            loop++;
            console.dump("第"++loop++"次循环");
            
            table.push(solution, v)	 // 将当前元素v添加到solution中
            //console.dump("v:", v, "X中最小的列:", c, "solution:", solution);
            
            var cols = xselect(X, Y, v); // 选择并删除相关列,并继续递归求解
            //console.dump("删除后的X:", X);

            table.push(result, solve(X, Y, solution)) // 将递归结果添加到tempResult中
            console.dump("result:", result);
            
            deselect(X, Y, v, cols) // 恢复相关列的选择,并将solution中的最后一个元素弹出
            //console.dump("恢复X:", X);
            
            table.pop(solution)
            //console.dump("solution:", solution);
        }
        return result; 
    }
}

//删除相关的行和列
xselect = function(X, Y, r){
	var cols = {};
	for(k,v in Y[r]){
		for(k2,v2 in X[v]){
			for(k3,v3 in Y[v2]){
				if(v3 != v){
					table.removeByValue(X[v3], v2)
				}
			}
		}
		table.push(cols, X[v]);
		X[v] = null
		//console.dump(X);
	}
	
	return cols; 
}

//恢复行和列
deselect = function(X, Y, r, cols){
	..table.reverse(Y[r])
	
	for(k,v in Y[r]){
		X[v] = table.pop(cols)
		for(k2,v2 in X[v]){
			for(k3,v3 in Y[v2]){
				if(v3 != v){
					table.push(X[v3], v2)
				}
			}
		}
	}
}

//辅助函数,返回哈希表键值对的数量
hashCount = function(tab){
	var count = 0
	for(k,v in tab){
		count++
	}
	return count; 
}

//辅助函数,返回一个哈希表中,长度最小的键值对的索引
findShortest = function(tab){
	var count = 9
	var result = ""
	for(k,v in tab){
		if(#v != 0 and #v <= count){
			result = k
			count = #v
		}
	}
	//console.dump(result);
	return result; 
}

//辅助函数,将字符串转为二维数组
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
}

GridToString = function(grid){
	var str = "";
	for(i=1;9;1){
		for(j=1;9;1){
			if(grid[i][j] == 0){
				str = str ++ '.'
			}
			else {
				str = str ++ tostring(grid[i][j])
			}	
		}
	}
	return str; 
}



var question = {
	".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..3";
	".................1.....2.3......3.2...4....5...6.1.....3......6.7..8...952.7.....";
	".................1.....2.3......425...6.......17....8.....7...64...6....9..8...1.";
	".................1.....2.3......45....1.6.....4......7....8.4....9...2..3.61...9.";
	".................1.....2.3......45.6..3.......17...8.....16......8....4..6.5..2..";
	".................1.....2.3.....1...4..3.5.....26....7.14...8...5........7....6.2.";
	".................1.....2.3.....4...5..2.1...6..3..78.....9.32...1.....4..5.......";
	".................1.....2.3.....4...5..3.1.....26....7.15...8...4........7....6.2.";
	".................1.....2.3.....4.2.5..6..7.....8.9...4...8.3.6..4.....9..5.......";
	".................1.....2.3...1..4.....5.....6..6..378..4.....2..7..5.....9..1....";
	".................1.....2.3...1..4.....5.....6..6..782..4.....7..8..5.....9..1....";
	".................1.....2.3...2...4....3.5......41....6.5.6......7.....2..8.91....";
	".................1.....2.3...2...4....3.5......46....7.5.1......8.....2..9.76....";
	".................1.....2.34.....3.....5...16...7..4....4..1.....8..9....23.....8.";
	".................1.....2.34.....4.....5...6....6.3.....3..5.....7..6.8..24......7";
	".................1.....2.34.....4.....5...6....6.3.....3..6.....7..5.8..24......7";
	".................1.....2.34.....4.2...1........5.6.7...2........8..7.9..34..9....";
	".................1.....2.34.....42....1..3.....5.....6....1..7..2..6....38....5..";
	".................1.....2.34.....42....1..3.....5.....6....1..7..2..6....48....5..";
	".................1.....2.34.....5.....1...6....7..38......6.7...4..1....35.4.....";
}

//速度测试
speedTest = function(tab){
	var tick = time.tick()
	for(k,v in tab){
		var grid = stringToGrid(v)
		solution, answer = solveSudoku(grid)
		console.dump(answer);
	}
	console.dump("用时"++(time.tick()-tick)++"ms");
}

//speedTest(question)



var sudokuStr = ".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..." //解不出来
var sudokuStr = ".................1.....2.3......3.2...4....5...6.1.....3......6.7..8...952.7....." //解得出来

var sudokuStr = "8.3761.42562834791417592836746953128381246957295178463138629574.7438521962941738."
var sudokuStr = "..3.6...2.62.3...1..7..2.367.6..3.2.2.164....3.5....6..3....674.743862.962.4.7..."
var sudokuStr = ".................1.....2.3......3.2...1.4......5....6..3......4.7..8...962...7..." //解不出来

var grid = stringToGrid(sudokuStr)
var solution, answer, str = solveSudoku(grid)
console.dump(solution, answer, str);

console.pause(true);


最新回复 (2)
  • 光庆 1月前
    0 2

     太高级了,绕晕了

  • 小肥羊 1月前
    0 3
    算法的问题,过于高端,哈哈
返回