九宫格算法实现(C语言版本)

九宫格算法实现(C语言版本)

九宫格算法实现(C语言版本)

环境:VS2008下调试通过,以0表示需要填的数字,用回溯法进行“蛮算”

#include "stdafx.h"
#include <iostream>
using namespace std;

static int pu[9][9]=
    {
        {0,8,0,0,0,3,0,9,0},
        {0,0,7,6,4,0,0,5,0},
        {3,2,0,0,0,7,4,6,0},
        {0,4,0,0,0,1,0,3,0},
        {2,0,3,0,0,6,8,0,1},
        {0,5,0,7,0,9,0,4,0},
        {0,7,1,3,0,0,0,8,9},
        {0,3,0,0,1,4,7,0,0},
        {0,6,0,9,0,0,0,1,0} };

int isvalid(const int i, const int j)//验证函数当期i,j坐标是否符合游戏规则,不重复
{
    const int n = pu[i][j];
    const static int query[] = {0, 0, 0, 3, 3, 3, 6, 6, 6};
    int t, u;

    for (t = 0; t < 9; t++)
        if ((t != i && pu[t][j] == n) || (t != j && pu[i][t] == n))//0-9的数字,每行每列都不能重复
            return 0;

    for (t = query[i]; t < query[i] + 3; t++)  //9个宫的3×3里也不能重复
        for (u = query[j]; u < query[j] + 3; u++)
            if ((t != i || u != j) && pu[t][u] == n)
               return 0;    

    return 1;
}

void output(void)//输入函数
{
    static int n;

    cout << "Solution " << ++n << " : " < < e n d l;
    f or(int i = 0; i < 9; i++)
 {
        for (int j = 0; j < 9; j++)
            cout<< pu[i][j] << " ";
        cout << endl;
    }

    cout << endl;
}

void Try(const int n)//核心函数,回溯算法
{
    if (n == 81) 
 {
  //是否已经是最后一个格子
        output();
        return;
    }

    const int i = n / 9, j = n % 9;

    if (pu[i][j] != 0) 
 {
  //如果当前格子不需要填数字,就跳到下一个格子
        Try(n + 1);
        return;
    }

    for (int k = 0; k < 9; k++) {
        pu[i][j]++;//当前格子进行尝试所有解
        if (isvalid(i, j))
  {
   Try(n + 1);//验证通过,就继续下一个
   //output();
  }
    }

    pu[i][j] = 0;  //如果上面的单元无解,就回溯
}

int main(void)
{
 int temp;
    Try(0);
 cin>>temp;
}