數(shù)獨(dú)是一種小游戲。規(guī)則是在一個(gè)9*9或者其他型號(hào)的板子上填數(shù)字，必須滿足三個(gè)要求：1.每一個(gè)橫排的9個(gè)空格必須是1到9之間的互相不重復(fù)的一個(gè)數(shù)字。2.每一個(gè)豎排的9個(gè)空格必須是1到9之間的互相不重復(fù)的一個(gè)數(shù)字。3.每一個(gè)3*3的小單元（1~3,3~6,6~9）必須是1到9之間的互相不重復(fù)的一個(gè)數(shù)字。

下面是幾個(gè)重要的定義：

定義1（Sudoku Solution）： The solution of a Sudoku puzzle requires that every row, column, and box contain all the numbers in the set [1,2,...,9] and that every cell is occupied by one and only one number.

定義2（Preemptive Sets）: A preemptive?set is composed of numbers from the set [1,2,...,9] and is a set of size m, 2<= m <= 9, whose number are potential occupants of m cells exclusively, where exclusively means that no other numbers in the set [1,2,...,9] other than the members of those m cells.

解數(shù)獨(dú)的算法：

第一步：找到所有forced numbers 在數(shù)獨(dú)中的。（方法： 利用數(shù)獨(dú)的定義，先全部markup，然后判斷每一行，列和九宮格中是否只有唯一的數(shù)，如果有就標(biāo)記為確定的forced）

第二步：Mark up 數(shù)獨(dú)。（把所有的可能值分別填入不同的表格中）

第三步：迭代搜索preemptive sets（先發(fā)制人集合）在所有的行，列和九宮格中，劃掉被排除的數(shù)。

第四步：（a）找到了結(jié)果

? ? ? ? ? ? ? ?（b）必須隨機(jī)選一個(gè)數(shù)繼續(xù)往下找

第五步：如果4（a）成立，那么結(jié)束：如果4（b）成立，那么重新執(zhí)行第三步。