【AI】使用Cluade 3.5 Sonnet封装一个aardio数独库

qiufuxing 4月前 669

Cluade 3.5 Sonnet感觉应该是目前对aardio支持最好的模型了,非常强大,大家可以试试

用JS实现了一个解数独的库,媲美DLX算法,原理如下,使用Cluade 3.5 Sonnet将代码转为aardio,几乎不用怎么修改,唯一修改的地方就是将字符串拆分为表,其他地方没有修改,完美运行,平均速度8ms

  • 约束传播(Constraint Propagation): 这个算法使用了强大的约束传播技术。每次为一个格子分配值时,它都会立即消除相关格子(同行、同列、同宫)的候选值。这大大减少了搜索空间,因为许多无效的分支会在早期被剪枝。

  • 最小剩余值启发式(Minimum Remaining Values Heuristic): 算法总是选择候选值最少的格子来进行尝试。这种策略能够最大限度地减少分支因子,使得搜索树更窄,从而提高效率。

  • 单一候选值推理(Single Candidate Inference): 当一个格子只剩下一个可能的值时,算法会立即填入这个值,并进一步传播这个约束。这种快速推理能够在不需要回溯的情况下填入大量格子。

  • 隐含单一候选值推理(Hidden Single Candidate Inference): 算法会检查每个单元(行、列、宫)中是否有某个值只能放在一个位置。这种推理能够发现一些不那么明显的必然填入。

  • 深度优先搜索(Depth-First Search): 使用递归的深度优先搜索策略,结合上述启发式方法,能够快速找到解或确定无解。

  • 高效的数据结构: 使用了高效的数据结构来表示候选值和约束关系,使得约束传播和推理操作能够快速执行。

  • 预处理和初始化: 在开始解题之前,算法会预先计算所有的单元和相关格子(peers),这样在解题过程中就可以快速访问这些信息。

import console; 

class Sudoku {
    ctor() {
        this.DIGITS = "123456789"; // 允许的数字
        this.ROWS = "ABCDEFGHI"; // 行标签
        this.COLS = this.DIGITS; // 列标签
        this.SQUARES = null; // 方格 ID
        
        this.UNITS = null; // 所有单元(行、列或宫)
        this.SQUARE_UNITS_MAP = null; // 方格 -> 单元映射
        this.SQUARE_PEERS_MAP = null; // 方格 -> 同伴映射
        
        this.MIN_GIVENS = 17; // 最少给定数字
        this.NR_SQUARES = 81; // 方格总数
        
        this.BLANK_CHAR = "."; // 空白字符和棋盘表示
    }
    
    initialize = function() {
        this.SQUARES = this.cross(this.ROWS, this.COLS);
        this.UNITS = this.getAllUnits(this.ROWS, this.COLS);
        this.SQUARE_UNITS_MAP = this.getSquareUnitsMap(this.SQUARES, this.UNITS);
        this.SQUARE_PEERS_MAP = this.getSquarePeersMap(this.SQUARES, this.SQUARE_UNITS_MAP);
    }
    
    solve = function(board, reverse = false) {
        this.initialize();
        var report = this.validateBoard(board);
        if (report !== true) {
            error(report);
        }
        
        var nrGivens = 0;
        var newBoard = ..string.split(board)
        for(i=1;#newBoard;1){
            if (newBoard[i] != this.BLANK_CHAR && this.isin(newBoard[i], this.DIGITS)) {
                nrGivens++;
            }
        }
        
        if (nrGivens < this.MIN_GIVENS) {
            error("Too few givens. Minimum givens is " + this.MIN_GIVENS);
        }

        
        var candidates = this.getCandidatesMap(board);
        var result = this.search(candidates, reverse);

        
        if (result) {
            var solution = "";
            for(k,v in this.SQUARES){
            	solution = solution ++ tostring(result[v]);
            }
            
            return solution;
        }
        return false;
    } 
    ...
}


上传的附件:
最新回复 (4)
  • netfox 4月前
    0 2

  • 光庆 4月前
    0 3

  • murphey 4月前
    0 4

  • aardio 4月前
    0 5
    厉害,(๑•̀ㅂ•́)و✧
返回