Sudoku

Description

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. 

Input

Output

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

思路：我是直接暴力做的，一开始从左上角开始搜结果T了，改成右下角开始搜就AC了。。。代码写得很凌乱，等知道到怎么优化了再来改吧。

#include <stdio.h>

int a[9][9];
bool end;

void search(int x,int y)
{
    int i,j,k,p,q,flag;

    if(y==-1)
    {
        x--;
        y=8;
    }

    if(!end && x==-1 && y==8)
    {
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                printf("%d",a[i][j]);
            }
            printf("\n");
        }
        end=1;
    }
    else if(!end && !a[x][y])
    {
        for(k=1;k<=9;k++)
        {
            flag=1;
            for(i=0;i<9;i++)//判断行列有没有k
            {
                if(a[x][i]==k) {flag=0;break;}
                if(a[i][y]==k)  {flag=0;break;}
            }
            p=x/3*3;
            q=y/3*3;
            for(i=0;i<3;i++)//判断宫内有没有k
            {
                for(j=0;j<3;j++)
                {
                    if(a[p+i][q+j]==k) {flag=0;break;}
                }
            }

            if(!flag) continue;

            a[x][y]=k;
            search(x,y-1);
            a[x][y]=0;
        }
    }
    else if(!end && a[x][y]) search(x,y-1);
}

int main()
{
    int i,j,t;

    scanf("%d",&t);

    while(t--)
    {
        for(i=0;i<9;i++)
        {
            for(j=0;j<9;j++)
            {
                scanf("%1d",&a[i][j]);
            }
        }

        end=0;
        search(8,8);
    }

    return 0;
}

Sudoku

原文：http://blog.csdn.net/faithdmc/article/details/18781693