leetcode—sudoku solver

1.题目描述

Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indicated by the character '.'. You may assume that there will be only one unique solution.

 

2.解法分析

class Solution { public: bool isValid(vector<vector<char> > &board, int x, int y) { int i, j; for (i = 0; i < 9; i++) if (i != x && board[i][y] == board[x][y]) return false; for (j = 0; j < 9; j++) if (j != y && board[x][j] == board[x][y]) return false; for (i = 3 * (x / 3); i < 3 * (x / 3 + 1); i++) for (j = 3 * (y / 3); j < 3 * (y / 3 + 1); j++) if (i != x && j != y && board[i][j] == board[x][y]) return false; return true; } bool solveSudoku(vector<vector<char>> &board) { for(int y=0;y<9;++y) { for(int x=0;x<9;++x) { if(board[y][x]=='.') { for(int i=1;i<=9;++i) { board[y][x]='0'+i; if(isValid(board,y,x)) { // if(x==8)if(mySolveSudoku(board,sh+1))return true; if(solveSudoku(board))return true; } board[y][x]='.'; } return false; } } } return true; } };