CAJ | 학술논문

数独问题已被证明是一个NP完全问题。采用分布式势博弈方法求解该问题。首先建立其效用函数并证明数独问题可以转化为势博弈模型，然后使用学习动力逐步优化参与者的状态以达到势博弈的最优状态—纳什均衡点。同时势博弈现有大部分研究结果限于计算机仿真，为此给出数独问题一个物理的博弈实现，物理博弈过程参与者通过三个手机体现。实验结果表明新的解决方式能够快速收敛。
수독문제이피증명시일개NP완전문제。채용분포식세박혁방법구해해문제。수선건립기효용함수병증명수독문제가이전화위세박혁모형，연후사용학습동력축보우화삼여자적상태이체도세박혁적최우상태—납십균형점。동시세박혁현유대부분연구결과한우계산궤방진，위차급출수독문제일개물리적박혁실현，물리박혁과정삼여자통과삼개수궤체현。실험결과표명신적해결방식능구쾌속수렴。
Sudoku problem has been proved to be an NP complete problem.We use a distributed potential game method to solve the problem.Firstly, the utility function of the problem is established and the Sudoku problem is proved to be able to convert to a potential game model, and then the learning rule is used to gradually optimise the status of the players in order to achieve the optimal state of potential game which is Nash equilibrium point.Meanwhile, most of the existing research results of potential game are limited to computer simulation.We present a game implementation of Sudoku problem in physical form.Participants in the process of physical game are embodied by three mobile phones.Experimental results show that the new solution can converge quickly.