数独

不觉的我的代码有什么问题，题目说了是9x9,然后测试用例居然有9x1是几个意思!

import java.util.Scanner;

/**
 * 数独是一个非常有名的游戏。整个是一个9X9的大宫格，其中又被划分成9个3X3的小宫格。
 * 要求在每个小格中放入1-9中的某个数字。要求是：每行、每列、每个小宫格中数字不能重复。
 * 现要求用计算机求解数独。
 *
 * @author shijiacheng
 */
public class SudokuSolution {

    private int[][] sudoku;
    public SudokuSolution(int[][] sudoku){
        this.sudoku = sudoku;
    }

    public static void main(String[] args){
        // 号称世界上最难数独
        int[][] suduku = new int[9][9];
        /*int[][] suduku = {
                {8, 0, 0, 0, 0, 0, 0, 0, 0},
                {0, 0, 3, 6, 0, 0, 0, 0, 0},
                {0, 7, 0, 0, 9, 0, 2, 0, 0},
                {0, 5, 0, 0, 0, 7, 0, 0, 0},
                {0, 0, 0, 0, 4, 5, 7, 0, 0},
                {0, 0, 0, 1, 0, 0, 0, 3, 0},
                {0, 0, 1, 0, 0, 0, 0, 6, 8},
                {0, 0, 8, 5, 0, 0, 0, 1, 0},
                {0, 9, 0, 0, 0, 0, 4, 0, 0}};*/
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                suduku[i][j] = sc.nextInt();
            }
        }
        sc.close();

        SudokuSolution solution = new SudokuSolution(suduku);
        solution.findNumber(0,0);

    }

    private void findNumber(int i, int j){
        if (i == 8 && j==9){
            //success find
            printResult();
            return;
        }

        if (j == 9){
            i++;
            j = 0;
        }

        if (sudoku[i][j] == 0){
            for (int k = 1; k <=9 ; k++) {
                if (canUse(i,j,k)){
                    sudoku[i][j] = k;
                    findNumber(i,j+1);
                }else {
                    sudoku[i][j] = 0;
                }
            }

        }else {
            findNumber(i,j+1);
        }
    }


    private boolean canUse(int row,int line,int number){
        for (int i = 0; i < 9; i++) {
            if (sudoku[row][i] == number || sudoku[i][line] == number){
                return false;
            }
        }

        //判断小九宫格是否有重复
        int eachRow = row / 3;
        int eachLine = line / 3;
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (sudoku[eachRow * 3 + i][eachLine * 3 + j] == number) {
                    return false;
                }
            }
        }

        return true;
    }

    private void printResult(){

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (j<8){
                    System.out.print(sudoku[i][j] + " ");
                }else {
                    System.out.print(sudoku[i][j]);
                }

            }
            System.out.println();
        }
        System.out.println();
    }
}

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[][] sudoku = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String[] strs = br.readLine().split(" ");
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = Integer.parseInt(strs[j]);
            }
        }

        dfs(sudoku, 0, 0);
    }

    private static boolean dfs(int[][] sudoku, int i, int j) {
        if (i == 8 && j == 9) {
            prtSudoku(sudoku);
            return true;
        }
        if (j == 9) {
            i++;
            j = 0;
        }

        boolean res = false;
        if (sudoku[i][j] == 0) {
            boolean[] options = optionalNumber(sudoku, i, j);
            for (int k = 1; k < options.length; k++) {
                if (!res && !options[k]) {
                    sudoku[i][j] = k;
                    res = dfs(sudoku, i, j + 1);
                }
            }
            if (!res) sudoku[i][j] = 0;
        } else {
            dfs(sudoku, i, j + 1);
        }
        return res;
    }

    private static void prtSudoku(int[][] sudoku) {
        for (int i = 0; i < sudoku.length; i++) {
            for (int j = 0; j < sudoku[0].length - 1; j++) {
                System.out.print(sudoku[i][j] + " ");
            }
            System.out.println(sudoku[i][sudoku[0].length - 1]);
        }
    }

    private static boolean[] optionalNumber(int[][] sudoku, int x, int y) {
        boolean[] options = new boolean[10];
        for (int i = 0; i < sudoku.length; i++) {
            options[sudoku[x][i]] = true;
            options[sudoku[i][y]] = true;
        }
        int row = x / 3 * 3, col = y / 3 * 3;
        for (int i = row; i < row + 3; i++) {
            for (int j = col; j < col + 3; j++) {
                options[sudoku[i][j]] = true;
            }
        }
        return options;
    }
}

/*
本来我和一楼认为的一样怎么输入是一维的..
结果我发现只是牛客网有bug没有打印全所有的输入输出而已

写bug半小时,解bug两小时... 本质就是一个dfs不过是带返回值判断的,只要找到一组解就返回
一开始写的少了一个乘法... 结果过了25%,一看给的输入好生气,后来dubug花了两个小时.....

下面有第二个测试的输入和正确输出, 第一个就是给的例子
*/


#include <bits/stdc++.h>
using namespace std;

class Solution
{
    public:
    vector<vector<int>>gg;
    vector<vector<int>>c;
    vector<vector<int>>line;


    bool cheak(int val, int m, int n)
    {
        if (m < 0 || n < 0 || m >= 9 || n > 9)
        {
            return false;
        }
        if (!gg[m / 3 * 3 + n / 3][val] && !line[n][val] && !c[m][val])
            return true;
        return false;
    }

    vector<vector<int>>res;
    bool dfs(vector<vector<int>>&ret, int m, int n)
    {
        if (n == 9)
        {
            m++;
            n = 0;
        }
        if (m == 9)
        {
            res = ret;
            return true;
        }
        // 表示当前是已经弄好的数字
        if (ret[m][n] != 0)
        {

            n++;
            return dfs(ret, m, n);
        }

        for (int i = 1; i <= 9; i++)
        {
            if (cheak(i, m, n))
            {
                ret[m][n] = i;
                line[n][i] = 1;

                c[m][i] = 1;
                gg[m / 3 * 3 + n / 3][i] = 1;
                // 表示是有效数字
                if (dfs(ret, m, n + 1))
                    return true;
                line[n][i] = 0;
                c[m][i] = 0;
                gg[m / 3  * 3 + n / 3][i] = 0;
                ret[m][n] = 0;
            }
        }
        return false;
    }

};


/*
                0 0 4 5 0 0 9 7 0                      8 2 4 5 3 1 9 7 6
                0 6 0 8 2 9 0 0 3                       5 6 7 8 2 9 1 4 3
                1 0 0 0 0 0 5 0 0                      1 9 3 4 6 7 5 2 8
                9 0 0 0 5 6 0 0 2                      9 0 0 0 5 6 0 0 2
                0 7 0 2 0 8 0 1 0
                0 1 6 3 7 4 0 0 0
                4 0 9 6 1 2 3 8 7
                0 8 0 9 4 3 0 0 5
                6 3 2 7 8 5 4 9 1



                8 2 4 5 3 1 9 7 6
                5 6 7 8 2 9 1 4 3
                1 9 3 4 6 7 5 2 8
                9 4 8 1 5 6 7 3 2
                3 7 5 2 9 8 6 1 4
                2 1 6 3 7 4 8 5 9
                4 5 9 6 1 2 3 8 7
                7 8 1 9 4 3 2 6 5
                6 3 2 7 8 5 4 9 1
                */

int main()
{
    ios::sync_with_stdio(false);
    vector<vector<int>>matrix(9, vector<int>(9, 0));
    vector<vector<int>>line(9, vector<int>(10, 0));
    vector<vector<int>>clu(9, vector<int>(10, 0));
    vector<vector<int>>gongge(9, vector<int>(10, 0));
    int tmp;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            cin >> tmp;
            matrix[i][j] = tmp;

            clu[i][tmp] = 1;
            line[j][tmp] = 1;
            gongge[i / 3 * 3 + j / 3][tmp] = 1;
        }
    }
    // 此时已经完成了输入
    Solution s1;
    s1.gg = gongge;
    s1.c = clu;
    s1.line = line;
    s1.dfs(matrix, 0, 0);
    for (int i = 0; i < 9; i++)
    {
        int j = 0;
        for (;j < 8; j++)
        {
            cout << s1.res[i][j] << " ";

        }
        cout << s1.res[i][j] << endl;
    }
    return 0;
}

##栈实现DFS？ 
board=[]
for _ in range(9):
    board.append(input().replace(' ',''))
#print(board)
def isV(board,x,y,c):
    for i in range(9):
        if board[x][i]==c or board[i][y]==c:
            return False
    for j in range(3*(x//3),3*(x//3)+3):
        for k in range(3*(y//3),3*(y//3)+3):
            if board[j][k]==c: return False
    return True
num=[]
for i in range(9):
    for j in range(9):
        if board[i][j]=='0':
            num.append([i,j])
q=[[board,0]]
res='#'
while q:
    board,idx=q.pop()
    if idx==len(num): 
        res=board[:]
        break
    i,j=num[idx]
    for c in '123456789':
        if isV(board,i,j,c):
            tmp=board[i]
            cur=tmp[:j]+c+tmp[j+1:]
            board[i]=cur
            q.append([board[:],idx+1])
for i in range(9):
    s1=[]
    for c in res[i]:
        s1.append(c)
    print(' '.join(s1))
    

import java.util.Scanner;
public class Main {
    private int[][] numMap = new int[9][9];
    private int staLen;
    private Coordinate[] stack = new Coordinate[81];

    public void run() {
        init();
        find(0);
    }
       //dfs
    private void find(int step) {
        if (step == staLen) {
                     //判断是否找到一个解
            show();
                     System.exit(0);
        } else {
            for (int i = 1; i <= 9; i++) {
               int x = stack[step].x;
               int y = stack[step].y;
                if (tryNum(x, y, i)) {
                    numMap[y][x] = i;
                                   find(step + 1);//若可填入，继续尝试下一个空
                    numMap[y][x] = 0;//回溯时把原来填的数字归0
                }
            }
        }
    }
       //判断坐标（x,y）能否填入num
    private boolean tryNum(int x, int y, int num) {
              //先判断同行同列有无重复
        for (int i = 0; i < 9; i++) {
            if (numMap[y][i] == num || numMap[i][x] == num) {
                return false;
            }
        }
              //分组判断
        x /= 3;
        y /= 3;
        for (int i = y * 3; i < y * 3 + 3; i++) {
            for (int j = x * 3; j < x * 3 + 3; j++) {
                if (numMap[i][j] == num) {
                    return false;
                }
            }
        }
        return true;
    }
       //初始化读入数据
    private void init() {
              Scanner sc = new Scanner(System.in);
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                numMap[y][x] = sc.nextInt();
                if (numMap[y][x] == 0) {
                    stack[staLen++] = new Coordinate(x, y);
                }
            }
        }
        sc.close();
    }
       //输出
    private void show() {
        for (int y = 0; y < 9; y++) {
            for (int x = 0; x < 9; x++) {
                               //每行第一个数字前面没有空格
                if(x == 0){
                    System.out.print(numMap[y][x]);
                }else{
                    System.out.print(" " + numMap[y][x]);
                }
            }
            System.out.println();
        }
    }
       //坐标类
    static class Coordinate {
        int x;
        int y;
        Coordinate(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    
    public static void main(String[] args){
        new Main().run();
    }
} 

#include<iostream>
#include<vector>

using namespace std;

bool check(vector<vector<int>> & soduku,int x,int y,int n){
    for(int i = 0;i<9;i++){
        if(soduku[i][y] == n)return false;
        if(soduku[x][i] == n)return false;
    }
    for(int i = 0;i<3;i++){
        for(int j = 0;j<3;j++){
            if(soduku[x/3*3+i][y/3*3+j] == n)return false;
            
        }
    }
    return true;
}

bool solvesudo(vector<vector<int>> & soduku,int cur){
    if(cur == 81)return true;
    int x = cur/9;
    int y = cur%9;
    if(soduku[x][y]!=0)return solvesudo(soduku, cur+1);
    for(int i = 1;i<10;i++){
        if(check(soduku,x,y,i)){
            soduku[x][y] = i;
            if(solvesudo(soduku,cur+1))return true;
            soduku[x][y] = 0;
        }
    }return false;
}


int main(){
    vector<vector<int>>soduku(9,vector<int>(9,0));
    for(int i = 0;i<9;i++){
        for(int j = 0;j<9;j++){
            cin>>soduku[i][j];
        }
    }
    solvesudo(soduku, 0);
    for(int i = 0;i<9;i++){
        for(int j = 0;j<9;j++){
            if(j!=8)cout<<soduku[i][j]<<" ";
            else cout<<soduku[i][j];
        }
        cout<<endl;
    }
    return 0;
}

def dfs(matrix,zero_index):
    
    if not zero_index:
        for line in matrix:
            line = list(map(str,line))
            print(' '.join(line))
        return
    else:
        x,y = zero_index[0]
        
        value_not_be = []
        for y1 in range(9):
            value_not_be.append(matrix[x][y1])
        for x1 in range(9):
            value_not_be.append(matrix[x1][y])
        x2 = x//3*3
        y2 = y//3*3
        value_not_be.extend([matrix[x2+i][y2+j] for i in range(3) for j in range(3)])
        value_not_be = [i for i in value_not_be if i != 0]
        value_not_be = set(value_not_be)
        if len(value_not_be) == 9:
            return
        
        for i in range(1,10):
            if i not in value_not_be:
                matrix1 = [i.copy() for i in matrix]
                matrix1[x][y] = i
                dfs(matrix1,zero_index[1:])
                
import sys

matrix = []
for _ in range(9):
    line = list(map(int,sys.stdin.readline().strip().split(' ')))
    matrix.append(line)
zero_index = []

for i in range(9):
    for j in range(9):
        if matrix[i][j] == 0:
            zero_index.append((i,j))

dfs(matrix,zero_index)
    

def isValid(board,row,col,c):
    flag = True
    for i in range(9):
        if board[row][i] == c:
            flag = False
            break
    for i in range(9):
        if board[i][col] == c:
            flag = False
            break
    for i in range(3*(row/3),3*(row/3)+3):
        for j in range(3*(col/3),3*(col/3)+3):
            if board[i][j] == c:
                flag = False
                break
        if flag == False:
            break    
    return flag

def solve(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == '0':
                for c in range(1,10):
                    if isValid(board,i,j,str(c)):
                        board[i][j] = str(c)
                        if solve(board):
                            return True
                        else:
                            board[i][j] = '0'
                return False
    return True
                        

if __name__ == "__main__":
    matrix = [[] for i in range(9)]
    for i in range(9):
        line = raw_input()
        lines = line.split()
        for item in lines:
            matrix[i].append(item)
    solve(matrix)
    for i in range(9):
        print " ".join(matrix[i])

import java.util.*;

public class Main {
    public static int[][] sudo = new int[9][9];//创建数组
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sudo[i][j] = sc.nextInt(); //创建数独
                }
            }
            if (backTracking(sudo)) {
                for (int i = 0; i < 9; i++) {
                    for (int j = 0; j < 9; j++) {
                        if (j == 8) {
                            //最后一位数需要换行输出
                            System.out.println(sudo[i][j]);
                        } else {
                            System.out.print(sudo[i][j] + " ");
                        }
                    }
                }
            }
        }
    }

    public static boolean backTracking(int[][] sudo) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) { //遍历数组
                if (sudo[i][j] != 0) { //如果不需要填数字直接continue
                    continue;
                }
                for (int k = 1; k <= 9; k++) { //循环填数字
                    if (isValid(i, j, k, sudo)) { //判断填入数字是否符合要求
                        sudo[i][j] = k; //填数字
                        if (backTracking(sudo)) { //递归
                            return true;
                        }
                        sudo[i][j] = 0; //回溯
                    }
                }
                return false;//如果没有符合要求的数字返回false
            }
        }
        return true;
    }

    public static boolean isValid(int row, int col, int k, int[][] sudo) {
        for (int i = 0; i < 9; i++) { //检查行
            if (sudo[row][i] == k) {
                return false;
            }
        }
        for (int i = 0; i < 9; i++) { //检查列
            if (sudo[i][col] == k) {
                return false;
            }
        }
        int startRow = (row / 3) * 3;
        int endCol = (col / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++) { //检查九宫格
            for (int j = endCol; j < endCol + 3; j++) {
                if (sudo[i][j] == k) {
                    return false;
                }
            }
        }
        return true;
    }
}

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 10;
char g[N][N];
bool row[N][N], col[N][N], cell[3][3][N];


bool dfs(int x, int y)
{
    if(y == 9) x ++, y = 0;
    if(x == 9)
    {
        for(int i = 0; i < 9;i ++) 
        {
            for(int j = 0;j < 9;j ++)
            {
                cout << g[i][j] << ' ';
            }
            cout << endl;
        }
        return true;
    }
    
    if(g[x][y] != '.') return dfs(x ,y + 1);
    for(int i = 0;i < 9 ;i ++)
    {
        if(!row[x][i] && !col[y][i] && !cell[x / 3][y / 3][i])
        {
            g[x][y] = i + '1';
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = true;
            if(dfs(x, y + 1)) return true;
            row[x][i] = col[y][i] = cell[x / 3][y / 3][i] = false;
            g[x][y] = '.';
        }
    }
    return false;
}
int main()
{
    for(int i = 0;i < 9;i ++) 
    {
        
        for(int j = 0;j < 9;j ++)
        {
            cin >> g[i][j];
            if(g[i][j] != '.')
            {
                int t = g[i][j] - '1';
                row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
            }
        }
    }
    dfs(0, 0);
    return 0;
}

华为2016研发工程师编程题

华为该套试卷中的数独有两个答案，而后台对比程序只有一个，所以一直返回有问题

用例为：

0 0 8 7 1 9 2 4 5
9 0 5 2 3 4 0 8 6
0 7 4 8 0 6 1 0 3
7 0 3 0 9 2 0 0 0
5 0 0 0 0 0 0 0 0
8 6 1 4 0 3 5 2 9
4 0 0 0 2 0 0 0 8
0 0 0 0 0 0 0 7 0
1 0 7 0 6 8 0 5 0

答案为(第7，8行不一样)：

6 3 8 7 1 9 2 4 5
9 1 5 2 3 4 7 8 6
2 7 4 8 5 6 1 9 3
7 4 3 5 9 2 8 6 1
5 9 2 6 8 1 4 3 7
8 6 1 4 7 3 5 2 9
4 5 6 3 2 7 9 1 8
3 8 9 1 4 5 6 7 2
1 2 7 9 6 8 3 5 4

6 3 8 7 1 9 2 4 5
9 1 5 2 3 4 7 8 6
2 7 4 8 5 6 1 9 3
7 4 3 5 9 2 8 6 1
5 9 2 6 8 1 4 3 7
8 6 1 4 7 3 5 2 9
4 5 9 3 2 7 6 1 8
3 8 6 1 4 5 9 7 2
1 2 7 9 6 8 3 5 4

对应第二个答案的代码如下：

#!/usr/bin/env python

#ret = [[i for i in range(9)] for i in range(9)]
nums = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

ret = []

for i in range(9):
    ret1 = map(int, raw_input().split())
    ret.append(ret1)


#ret = [[5, 0, 0, 9, 2, 0, 7, 0, 0], [0, 7, 0, 3, 4, 0, 8, 0, 0], [0, 2, 0, 0, 1, 0, 0, 5, 0], [7, 0, 4, 0, 6, 0, 1, 0, 0], [6, 0, 2, 1, 8, 3, 9, 4, 0], [0, 9, 0, 7, 5, 4, 0, 0, 8], [0, 0, 5, 8, 3, 6, 0, 7, 9], [0, 3, 9, 0, 7, 2, 6, 0, 1], [8, 0, 0, 4, 9, 1, 5, 2, 3]]

def func1(arr):
    for i in range(len(arr)):
        if 0 in arr[i]:
            return False

    return True


#get existed num set, including 0
def func2(arr, row, col):
    lst = list(arr[row])
    i1 = ((row+3)/3 - 1) * 3
    j1 = ((col+3)/3 - 1) * 3

    for i in range(9):
        lst.append(arr[i][col])

    for i in range(i1, i1+3):
        for j in range(j1, j1+3):
            lst.append(arr[i][j])

    #print "func2----------------------"
    #print row, col, lst
    lst = list(set(lst))
    return lst

def print_matrix(arr):
    for i in range(9):
        print ' '.join(map(str, arr[i]))


def func(arr, row, col):
    if func1(arr):
        lst = func2(arr, row, col)
        if len(lst) == 9:
            #print_matrix(arr)
            return True
        else:
            return False
    else:
        #arr1 = copy.deepcopy(arr)
        for i in range(9):
            for j in range(9):
                if arr[i][j] == 0:
                    lst = func2(arr, i, j)
                    lst_rest = list(set(nums) - set(lst))
                    #print i, j, lst, lst_rest
                    if not lst_rest:
                        return False
                    for n in lst_rest:
                        arr[i][j] = n
                        if func(arr, i, j):
                            return True
                        else:
                            arr[i][j] = 0
                    return False

func(ret, 0, 0)
print_matrix(ret)

import java.util.*;
public class Test{
    public static void main(String[] args){
        Scanner scanner=new Scanner(System.in);
        List<Set<Integer>> listRow=new ArrayList<Set<Integer>>();
        List<Set<Integer>> listCol=new ArrayList<Set<Integer>>();
        List<Set<Integer>> listGroup=new ArrayList<Set<Integer>>();
        int[][] Soduku=new int[9][9];
        for(int i=0;i<9;i++) {
            listRow.add(new TreeSet<Integer>());
            listCol.add(new TreeSet<Integer>());
            listGroup.add(new TreeSet<Integer>());
        }
        for(int i=0;i<9;i++) {
            for(int j=0;j<9;j++) {
                Soduku[i][j]=scanner.nextInt();
                listRow.get(i).add(Soduku[i][j]);
                listCol.get(j).add(Soduku[i][j]);
                listGroup.get(i/3*3+j/3).add(Soduku[i][j]);
            }
        }
        soduku(Soduku,listRow,listCol,listGroup,0);
        for(int i=0;i<9;i++){
            for(int j=0;j<9;j++){
            	if(j!=8) {
            		System.out.print(Soduku[i][j]+" ");
            	}else {
            		System.out.println(Soduku[i][j]);
            	} 
            } 
        }
    }
    public static Boolean soduku(int[][] Soduku,List<Set<Integer>> listRow,List<Set<Integer>> listCol,List<Set<Integer>> listGroup,int index){
    	Set<Integer> temp=new TreeSet<Integer>();
        Set<Integer> set1=new TreeSet<Integer>();
        Set<Integer> set2=new TreeSet<Integer>();
        int row=index/9;
        int col=index%9;
        int group=row/3*3+col/3;
//        System.out.println(index);
        if(index>80) {
        	return true;
        }
        for(int i=0;i<10;i++) {
        	temp.add(i);
        }
        if(Soduku[row][col]!=0) {
        	return soduku(Soduku, listRow, listCol, listGroup, index+1);
        }else {
        	set1.addAll(listRow.get(row));
        	set1.addAll(listCol.get(col));
        	set1.addAll(listGroup.get(group));
        	set2.addAll(temp);
        	set2.removeAll(set1);
        	if(set2.size()==0) {
        		return false;
        	}
//        	System.out.print(set2+"--->"+set2.size());
        	for(Iterator<Integer> it=set2.iterator();it.hasNext();) {
        		int t=it.next();
//        		System.out.println("-------->"+t);
//        		System.out.println(t);
        		Soduku[row][col]=t;
        		listRow.get(row).add(t);
        		listCol.get(col).add(t);
        		listGroup.get(row/3*3+col/3).add(t);
        		if(soduku(Soduku, listRow, listCol, listGroup, index+1)) {
        			return true;
        		}
//        		System.out.println(index+"------>"+t);
        		Soduku[row][col]=0;
        		listRow.get(row).remove(t);
        		listCol.get(col).remove(t);
        		listGroup.get(row/3*3+col/3).remove(t);
        	}
        	set1.clear();
        	set2.clear();
	        return false;
        }
    }
}

import java.util.Scanner;

/**
 * @Author qgfzzzzzz
 * @Date 2019/8/19
 * @Version 1.0
 * <p>
 *
 * </p>
 */
public class Main {
    public static int[][] board;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        board = new int[9][9];
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                board[i][j] = scanner.nextInt();
            }
        }
        solve(board);
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(j == 8) System.out.println(board[i][j]);
                else System.out.print(board[i][j] + " ");
            }
        }
    }
    public static boolean solve(int[][] board){
        for(int i = 0; i < 9; i++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] == 0){
                    for(int k = 1; k <= 9; k++) {
                        if(isValid(i, j, board, k)){
                            board[i][j] = k;
                            if(solve(board))
                                return true;
                            else board[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    public static boolean isValid(int row, int col, int[][] board, int target){
        for(int i = 0; i < 9; i++){
            if(board[row][i] != 0 && board[row][i] == target) return false;
            if(board[i][col] != 0 && board[i][col] == target) return false;
            if(board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] != 0 && board[(row / 3) * 3 + i / 3][(col / 3) * 3 + i % 3] == target) return false;
        }
        return true;
    }
}

import java.util.*;
public class Main{
    static int[][] map = new int[9][9];
    static boolean[][] rows = new boolean[9][10];
    static boolean[][] cols = new boolean[9][10];
    static boolean[][] blocks = new boolean[9][10];
    static Scanner sc = new Scanner(System.in);
    public static void main(String[] args){
        // 解析数据
        inputNum();
        // 深度优先搜索
        dfs(0, 0);
        // 输出结果
        printNum();
    }
    
    private static void inputNum(){
        for (int i = 0; i < 9; i++){
            for (int j = 0; j < 9; j++){
                int tmp = sc.nextInt();
                map[i][j] = tmp;
                rows[i][tmp] = true;
                cols[j][tmp] = true;
                int index = i / 3 * 3 + j / 3;
                blocks[index][tmp] = true;
            }
        }
    }
    
    private static void printNum(){
        for (int i = 0; i < 9; i++){
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 9; j++){
                sb.append(map[i][j] + " ");
            }
            sb.deleteCharAt(sb.length() - 1);
            System.out.println(sb);
        }
    }
    
    private static boolean dfs(int i, int j){
        while (map[i][j] != 0){
            j++;
            if (j == 9){
                if (i == 8){
                    return true;
                }
                i++;
                j = 0;
            }
        }
        int index = i / 3 * 3 + j / 3;
        for (int k = 1; k <= 9; k++){
            if (canPutNum(i, j, index, k)){
                putNum(i, j, index, k);
                if (dfs(i, j)){
                    return true;
                }
                // 回溯
                map[i][j] = 0;
                rows[i][k] = false;
                cols[j][k] = false;
                blocks[index][k] = false;
            }
        }
        return false;
    }
    
    private static boolean canPutNum(int i, int j, int index, int k){
        return !rows[i][k] && !cols[j][k] && !blocks[index][k];
    }
    
    private static void putNum(int i, int j, int index, int k){
        map[i][j] = k;
        rows[i][k] = true;
        cols[j][k] = true;
        blocks[index][k] = true;
    }
}