aardio扩展库 - 数独解析库

By jerryxjr1220 at 2021-09-15 • 0人收藏 • 560人看过

台风天,闲来无事,改写了python的数独解析程序,做了aardio的扩展库

捕获.PNG

解析速度要比python更快

//数独解析库Sudoku
class sudoku {
	ctor (matrix) {
		this = {};
		this.matrix = ..table.clone(matrix);
		this.step = 0;
		this.solved = false;
	};
	
	get_next_zero = function(){
		for i=1;9 {
			for j=1;9 {
				if this.matrix[i][j] == 0 {
					return i,j;
				}
			}
		}
		return -1,-1;
	};
	
	get_candidates = function(x, y){
		res = {};
		for v=1;9 {
			if ..table.find(this.matrix[x],v) {
				continue;
			};
			for i=1;9 {
				if this.matrix[i][y] == v {
					continue 2;
				}
			};
			for i=..math.modf((x-1)/3)*3+1;..math.modf((x-1)/3)*3+3 {
				for j=..math.modf((y-1)/3)*3+1;..math.modf((y-1)/3)*3+3 {
					if this.matrix[i][j] == v {
						continue 3;
					}
				}
			};
			..table.push(res, v);
		};
		return res;
	};
	
	try_value = function(x, y, list){
		for k,v in list {
			this.matrix[x][y] = v;
			next_x, next_y = this.get_next_zero();
			if next_x == -1 {
				return true;
			}
			candidates = this.get_candidates(next_x, next_y);
			this.step += 1;
			if this.try_value(next_x, next_y, candidates) {
				this.solved = true;
				return true; 
			} else {
				this.matrix[x][y] = 0;
				this.solved = false;
			}
		}
	}
}

namespace sudoku{
	
}

做个GUI可能更好玩,以后有空再写

3 个回复 | 最后更新于 2021-09-16
2021-09-15   #1

解析库调用:

import console; 
import sudoku;
import time;

sdk = sudoku({
    {6; 0; 0; 1; 0; 0; 7; 0; 8};
    {0; 0; 0; 8; 0; 0; 2; 0; 0};
    {2; 3; 8; 0; 5; 0; 1; 0; 0};
    {0; 0; 0; 0; 4; 0; 0; 9; 2};
    {0; 0; 4; 3; 0; 8; 6; 0; 0};
    {3; 7; 0; 0; 1; 0; 0; 0; 0};
    {0; 0; 3; 0; 7; 0; 5; 2; 6};
    {0; 0; 2; 0; 0; 4; 0; 0; 0};
    {9; 0; 7; 0; 0; 6; 0; 0; 4}
})

tm = time.tick();
x,y = sdk.get_next_zero()
list = sdk.get_candidates(x, y)
sdk.try_value(x, y, list)
duration = time.tick() - tm
if sdk.solved {
	console.log("解析成功,总共尝试了",sdk.step ,"种组合");
	console.log("用时", duration, "毫秒")
	for i=1;9 {
		console.print("[",sdk.matrix[i][1],sdk.matrix[i][2],sdk.matrix[i][3],
		                  sdk.matrix[i][4],sdk.matrix[i][5],sdk.matrix[i][6],
		                  sdk.matrix[i][7],sdk.matrix[i][8],sdk.matrix[i][9],"]")
	}
} else {
	console.log("本题无解")
}


console.pause(true);


2021-09-15   #2

2021-09-16   #3

更新数独解析,可以解多重解的数独

# -*- coding: utf-8 -*-
"""
Created on Wed Sep 15 09:51:40 2021

@author: xuj59
"""

m = [
    [6, 0, 0, 1, 0, 0, 7, 0, 8],
    [0, 0, 0, 8, 0, 0, 2, 0, 0],
    [2, 0, 8, 0, 5, 0, 0, 0, 0],
    [0, 0, 0, 0, 4, 0, 0, 9, 2],
    [0, 0, 4, 3, 0, 8, 6, 0, 0],
    [3, 7, 0, 0, 1, 0, 0, 0, 0],
    [0, 0, 3, 0, 7, 0, 5, 2, 6],
    [0, 0, 2, 0, 0, 4, 0, 0, 0],
    [9, 0, 7, 0, 0, 6, 0, 0, 4]]

from copy import deepcopy
import sys
sys.setrecursionlimit(1000000) # 发现python默认的递归深度是很有限的
                              #(默认是1000),因此当递归深度超过999的
                              # 样子,就会引发这样的一个异常。

class Sudoku():
    def __init__(self, m):
        self.init_m = deepcopy(m)
        self.m = m
        self.multi_results = []
        self.solved = False
        
    def get_next_pos(self, m=None, x=None, y=None):
        if m is None:
            m = self.m
        if (x is not None) and (y is not None):
            for i in range(9):
                if m[x][i] == 0:
                    return x,i
            for i in range(9):
                if m[i][y] == 0:
                    return i,y
        for i in range(9):
            for j in range(9):
                if m[i][j] == 0:
                    return i,j
        return -1,-1
    
    def get_candidates(self, x, y, m=None):
        if m is None:
            m = self.m
        return list(set(range(1,10)) - set(m[x]) - set([m[j][y] for j in range(9)]) - set([m[i][j] for i in range(x//3*3, x//3*3+3) for j in range(y//3*3, y//3*3+3)]))
    
    def print_results(self):
        print(f"Total {len(self.multi_results)} solution(s)")
        for c, res in enumerate(self.multi_results):
            print(f"Solution {c+1}:")
            for i in range(9):
                print(res[i])
            print("--------------------------------")
        
    def solve(self, x, y, candidates, m=None):
        if m is None:
            m = self.m
        for v in candidates:
            self.m[x][y] = v
            m[x][y] = v
            next_x, next_y = self.get_next_pos(m, x, y)
            if next_x == -1:
                if m not in self.multi_results:
                    self.multi_results.append(m)
                self.m = deepcopy(self.init_m)
                return True
            if self.solve(next_x, next_y, self.get_candidates(next_x, next_y, m), m):
                self.solved = True
                return True
            else:
                m[x][y] = 0
                self.m[x][y] = 0
                self.solved = False
            
    def multi_solve(self):
        start_pos = []
        for i in range(9):
            for j in range(9):
                if self.m[i][j] == 0:
                    start_pos.append((i,j))
        for pos in start_pos:
            x, y = pos
            self.m = deepcopy(self.init_m)
            values = self.get_candidates(x, y)
            self.solve(x, y, values)
        self.print_results()


s = Sudoku(m)
s.multi_solve()

结果:

Total 3 solution(s)
Solution 1:
[6, 9, 5, 1, 2, 3, 7, 4, 8]
[7, 4, 1, 8, 6, 9, 2, 5, 3]
[2, 3, 8, 4, 5, 7, 9, 6, 1]
[8, 1, 6, 7, 4, 5, 3, 9, 2]
[5, 2, 4, 3, 9, 8, 6, 1, 7]
[3, 7, 9, 6, 1, 2, 4, 8, 5]
[4, 8, 3, 9, 7, 1, 5, 2, 6]
[1, 6, 2, 5, 3, 4, 8, 7, 9]
[9, 5, 7, 2, 8, 6, 1, 3, 4]
--------------------------------
Solution 2:
[6, 3, 5, 1, 2, 9, 7, 4, 8]
[7, 4, 1, 8, 6, 3, 2, 5, 9]
[2, 9, 8, 4, 5, 7, 1, 6, 3]
[8, 1, 6, 7, 4, 5, 3, 9, 2]
[5, 2, 4, 3, 9, 8, 6, 7, 1]
[3, 7, 9, 6, 1, 2, 4, 8, 5]
[4, 8, 3, 9, 7, 1, 5, 2, 6]
[1, 6, 2, 5, 8, 4, 9, 3, 7]
[9, 5, 7, 2, 3, 6, 8, 1, 4]
--------------------------------
Solution 3:
[6, 9, 5, 1, 2, 3, 7, 4, 8]
[7, 4, 1, 8, 6, 9, 2, 5, 3]
[2, 3, 8, 4, 5, 7, 1, 6, 9]
[8, 1, 6, 7, 4, 5, 3, 9, 2]
[5, 2, 4, 3, 9, 8, 6, 7, 1]
[3, 7, 9, 6, 1, 2, 4, 8, 5]
[4, 8, 3, 9, 7, 1, 5, 2, 6]
[1, 6, 2, 5, 8, 4, 9, 3, 7]
[9, 5, 7, 2, 3, 6, 8, 1, 4]
--------------------------------


登录后方可回帖

登 录
信息栏
公 告:

专注分享

谢绝纯提问

谢谢合作!
本站域名:HtmLayout.Cn
aardio可以快速开发上位机,本站主要记录了学习过程中遇到的问题和解决办法及aardio代码分享

这里主要专注于aardio学习交流和经验分享.
纯私人站,当笔记本用的,学到哪写到哪.

Aardio 官方站:Aardio官方
Aardio最新功能:Aardio官方更新日志
本 站 主 站:Stm32cube中文网
Sciter中文在线文档Sciter在线学习文档
空间赞助:才仁机械
打赏本站
Loading...