题目96：开发一种解决数独问题的算法

欧拉计划

Su Doku

Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear, but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares. The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column, and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.

A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.

The 6K text file, sudoku.txt (right click and 'Save Link/Target As...'), contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions (the first puzzle in the file is the example above).

By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid; for example, 483 is the 3-digit number found in the top left corner of the solution grid above.

题目：

数独（日文意思是数字的位置）是一种流行的解谜游戏。其起源不详，但是 Leonhard Euler 的功劳不可不提，他发明了一种类似的但是更难的游戏叫做拉丁方块。数独游戏的目的是将一个 9×9 的网格中空白的（或者为 0 的）格子填上适当的数字，使得网格中每一行，每一列以及每个 3×3 的格子中都包含 1 到 9 中的每个数字。以下为一个数独游戏的初始状态及其解。

一个构造良好的数独游戏有且只有一个解并可通过逻辑推理得到，虽然有时需要使用“猜测加证实”的方法来减少可能性（该意见目前让具有很大争议）。搜索的复杂性决定了游戏的难度；以上例子是一个简单的数独游戏，因为其解可以通过直接推理得到。

p096_sudoku.txt (4.78 KB, 下载次数: 26)

2016-8-11 23:29 上传

点击文件名下载附件

包含 50 个难度不同的数独游戏且每个都具有唯一解，其中第一个就是上面的例子。

将 50 个数独游戏全部解出，并求每个解出的网格左上角的三位数之和；例如，上面例子中网格左上角的三位数是 483。

jerryxjr1220

数独算法：

class point:  
    def __init__(self,x,y):  
        self.x=x  
        self.y=y  
        self.available=[]  
        self.value=0  
  
def rowNum(p,sudoku):  
    row=set(sudoku[p.y*9:(p.y+1)*9])  
    row.remove(0)  
    return row #set type  
  
def colNum(p,sudoku):  
    col=[]  
    length=len(sudoku)  
    for i in range(p.x,length,9):  
        col.append(sudoku[i])  
    col=set(col)  
    col.remove(0)  
    return col #set type  
  
def blockNum(p,sudoku):  
    block_x=p.x//3  
    block_y=p.y//3  
    block=[]  
    start=block_y*3*9+block_x*3  
    for i in range(start,start+3):  
        block.append(sudoku[i])  
    for i in range(start+9,start+9+3):  
        block.append(sudoku[i])  
    for i in range(start+9+9,start+9+9+3):  
        block.append(sudoku[i])  
    block=set(block)  
    block.remove(0)  
    return block #set type  
  
def initPoint(sudoku):  
    pointList=[]  
    length=len(sudoku)  
    for i in range(length):  
        if sudoku[i]==0:  
            p=point(i%9,i//9)  
            for j in range(1,10):  
                if j not in rowNum(p,sudoku) and j not in colNum(p,sudoku) and j not in blockNum(p,sudoku):  
                    p.available.append(j)  
            pointList.append(p)  
    return pointList  
  
  
def tryInsert(p,sudoku):  
    availNum=p.available  
    for v in availNum:  
        p.value=v  
        if check(p,sudoku):  
            sudoku[p.y*9+p.x]=p.value  
            if len(pointList)<=0:  
                showSudoku(sudoku)
                exit()  
            p2=pointList.pop()
            tryInsert(p2,sudoku)
            sudoku[p2.y*9+p2.x]=0  
            sudoku[p.y*9+p.x]=0  
            p2.value=0  
            pointList.append(p2)  
        else:  
            pass      
  
def check(p,sudoku):  
    if p.value==0:  
        print('not assign value to point p!!')  
        return False  
    if p.value not in rowNum(p,sudoku) and p.value not in colNum(p,sudoku) and p.value not in blockNum(p,sudoku):  
        return True  
    else:  
        return False  
  
def showSudoku(sudoku):  
    for j in range(9):  
        for i in range(9):  
            print('%d '%(sudoku[j*9+i]),end='')  
        print('')     
  
if __name__=='__main__':  
    sudoku=[3,0,0,2,0,0,0,0,0,0,0,0,1,0,7,0,0,0,7,0,6,0,3,0,5,0,0,0,7,0,0,0,9,0,8,0,9,0,0,0,2,0,0,0,4,0,1,0,8,0,0,0,5,0,0,0,9,0,4,0,3,0,1,0,0,0,7,0,2,0,0,0,0,0,0,0,0,8,0,0,6]  
    pointList=initPoint(sudoku)  
    showSudoku(sudoku)  
    print('\n')  
    p=pointList.pop()  
    tryInsert(p,sudoku) 

jerryxjr1220

结果： 24702

gunjang

事先声明，网上的算法，采用Exact cover算法
妖风阵阵，完全看不懂。。。
例子就是那个有名针对暴力回溯法采取的解
[9, 8, 7, 6, 5, 4, 3, 2, 1]
[2, 4, 6, 1, 7, 3, 9, 8, 5]
[3, 5, 1, 9, 2, 8, 7, 4, 6]
[1, 2, 8, 5, 3, 7, 6, 9, 4]
[6, 3, 4, 8, 9, 2, 1, 5, 7]
[7, 9, 5, 4, 6, 1, 8, 3, 2]
[5, 1, 9, 2, 8, 6, 4, 7, 3]
[4, 7, 2, 3, 1, 9, 5, 6, 8]
[8, 6, 3, 7, 4, 5, 2, 1, 9]
欢迎大神给出注释

#!/usr/bin/env python3

# Author: Ali Assaf <ali.assaf.mail@gmail.com>
# Copyright: (C) 2010 Ali Assaf
# License: GNU General Public License <http://www.gnu.org/licenses/>

from itertools import product

def solve_sudoku(size, grid):
    R, C = size
    N = R * C
    X = ([("rc", rc) for rc in product(range(N), range(N))] +
         [("rn", rn) for rn in product(range(N), range(1, N + 1))] +
         [("cn", cn) for cn in product(range(N), range(1, N + 1))] +
         [("bn", bn) for bn in product(range(N), range(1, N + 1))])
    Y = dict()
    for r, c, n in product(range(N), range(N), range(1, N + 1)):
        b = (r // R) * R + (c // C) # Box number
        Y[(r, c, n)] = [
            ("rc", (r, c)),
            ("rn", (r, n)),
            ("cn", (c, n)),
            ("bn", (b, n))]
    X, Y = exact_cover(X, Y)
    for i, row in enumerate(grid):
        for j, n in enumerate(row):
            if n:
                select(X, Y, (i, j, n))
    for solution in solve(X, Y, []):
        for (r, c, n) in solution:
            grid[r][c] = n
        yield grid

def exact_cover(X, Y):
    X = {j: set() for j in X}
    for i, row in Y.items():
        for j in row:
            X[j].add(i)
    return X, Y

def solve(X, Y, solution):
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()

def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols

def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

if __name__ == "__main__":
    #A Sudoku designed to work against the brute force algorithm. in wikipedia
    grid = [
    [0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,3,0,8,5],
    [0,0,1,0,2,0,0,0,0],
    [0,0,0,5,0,7,0,0,0],
    [0,0,4,0,0,0,1,0,0],
    [0,9,0,0,0,0,0,0,0],
    [5,0,0,0,0,0,0,7,3],
    [0,0,2,0,1,0,0,0,0],
    [0,0,0,0,4,0,0,0,9]]
    for solution in solve_sudoku((3, 3), grid):
         print(*solution, sep='\n')

jerryxjr1220

gunjang 发表于 2017-8-26 21:28
事先声明，网上的算法，采用Exact cover算法
妖风阵阵，完全看不懂。。。
例子就是那个有名针对暴力回溯 ...

给你看个更牛的第三方库来求解数独问题。
同样求解你的例题，0.3s出答案。

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

from pymprog import model, iprod
p = model("sudoku")
I = range(1,10)
J = range(1,10)
K = range(1,10)
T = iprod(I,J,K) #create Indice tuples
x = p.var('x', T, bool)
#x[i,j,k] = 1 means cell [i,j] is assigned number k 
#assign pre-defined numbers using the "givens"
[x[i,j,k] == (1 if g[i-1][j-1] == k else 0) 
       for (i,j,k) in T if g[i-1][j-1] > 0 ]

#each cell must be assigned exactly one number
[sum(x[i,j,k] for k in K)==1 for i in I for j in J]

#cells in the same row must be assigned distinct numbers
[sum(x[i,j,k] for j in J)==1 for i in I for k in K]

#cells in the same column must be assigned distinct numbers
[sum(x[i,j,k] for i in I)==1 for j in J for k in K]

#cells in the same region must be assigned distinct numbers
[sum(x[i,j,k] for i in range(r,r+3) for j in range(c, c+3))==1
    for r in range(1,10,3) for c in range(1,10,3) for k in K]
   
#there is no need for an objective function here

p.solve()

for i in I:
   if i in range(1,10,3):
      print(" +-------+-------+-------+")
   print('', end=' ')
   for j in J:
      if j in range(1,10,3): print("|", end=' ')
      print("%g"%sum(x[i,j,k].primal*k for k in K), end=' ')
      if j==9: print("|")
   if i == 9:
      print(" +-------+-------+-------+")
p.end()

有空我会详细介绍这个超牛逼的第三方库，可以解决很多普通方法无法解决的线性规划问题。
先卖个关子

guosl

/*
本题用深度搜索，结果秒出
结果：24702
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>

char r[9][10], c[9][10], b[3][3][10];
int a[9][9];
int nSum = 0;

void dfs(int k)
{
  if (k == 81)//已经填好了
  {
    char str[4];
    str[0] = a[0][0] + '0';
    str[1] = a[0][1] + '0';
    str[2] = a[0][2] + '0';
    str[3] = 0;
    nSum += atoi(str);//统计结果
    return;
  }
  int nr = k / 9;//计算出当前的行和列
  int nc = k % 9;
  if (a[nr][nc] != 0)//这个格子已经有数字跳过
  {
    dfs(k + 1);
    return;
  }
  int nbr = nr / 3;//计算出所在块的位置
  int nbc = nc / 3;
  for (int i = 1; i <= 9; ++i)//试填数字
  {
    if (r[nr][i] == 0 && c[nc][i] == 0 && b[nbr][nbc][i] == 0)//检查这个数字是否已经被用过了
    {
      //在这个格子填
      r[nr][i] = 1;
      c[nc][i] = 1;
      b[nbr][nbc][i] = 1;
      a[nr][nc] = i;
      dfs(k + 1);//继续深入填下一个格子
      //回溯
      a[nr][nc] = 0;
      r[nr][i] = 0;
      c[nc][i] = 0;
      b[nbr][nbc][i] = 0;
    }
  }
}

int main(void)
{
  errno_t err;
  FILE *fp = NULL;
  err = fopen_s(&fp, "p096_sudoku.txt", "r");//打开文件
  if (err != 0)
  {
    printf_s("数据文件未打开\n");
    return 0;
  }
  char str[256];
  while (fgets(str, 255, fp) != NULL)//读数据
  {
    //初始化变量
    memset(r, 0, sizeof(r));
    memset(c, 0, sizeof(c));
    memset(b, 0, sizeof(b));
    for (int i = 0; i < 9; ++i)
    {
      fgets(str, 255, fp);//读入当前行的数据
      for (int j = 0; j < 9; ++j)
      {
        //填充各个格子的数据
        a[i][j] = int(str[j]) - 48;
        r[i][a[i][j]] = 1;
        c[j][a[i][j]] = 1;
        b[i / 3][j / 3][a[i][j]] = 1;
      }
    }
    dfs(0);//开始探索
  }
  fclose(fp);
  printf_s("%d\n", nSum);
  return 0;
}