数独问题的一个分布式物理博弈求解

摘要

数独问题已被证明是一个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.