leetcode: Sudoku Solver

Preface

3 things are discussed: 1) DFS implementation (BFS is an alternative) to solve it; 2) optimization we could do on the basic DFS; 3) remarks regarding the the maths behind Sudoku and some heuristics.

leetcode Sudoku Solver Problem Description:

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.

A sudoku puzzle…

…and its solution numbers marked in red.

leetcode Sudoku Solver Source code:

The algorithm to solve this problem will require using “Backtracking” plus “Pruning”. The basic idea is to try out all the possible fillings (DFS to search all the possible candidates) and determine to stop at an unsatisfactory partial state/configuration of the board as early as possible (Pruning to decide the valid fillings) or terminate at the final state of the board with all the cells filled without any invalidation. My first initial basic implementation is as follows, and I later on refactor and update the code to achieve (copyright @sigmainfy) a more compact and simplified version. Let’s see the basic one first:

class Solution {
public:
	const int board_size = 9;

	vector<vector<bool> > is_empty;
	bool isValid(const vector<vector<char> > &board, int i, int j) {
		int row = 0, row2 = 0, a = 0;
		int col = 0, col2 = 0, b = 0;
		int squ = 0, squ2 = 0, c = 0;
		for (int k = 0; k < board_size; ++k) {
			a = board[i][k] - '0';
			b = board[k][j] - '0';
			c = board[3 * (i / 3) + k / 3][3 * (j / 3) + k % 3] - '0';

			if (a > 0) row2 = row ^ (1 << a);
			if (b > 0) col2 = col ^ (1 << b);
			if (c > 0) squ2 = squ ^ (1 << c);

			if (row2 < row || col2 < col || squ2 < squ) return false;
			row = row2, col = col2, squ = squ2;
		}
		return true;
	}
	bool dfs(vector<vector<char> > &board, int n) {
		if (board_size * board_size == n)
			return true;
		int i = n / board_size;
		int j = n % board_size;
		if (!is_empty[i][j])
			return dfs(board, n + 1);
		for (char c = '1'; c <= '9'; ++c) {
			board[i][j] = c;
			if (!isValid(board, i, j)) continue;
			if (dfs(board, n + 1)) return true;
		}
		board[i][j] = '.';
		return false;
	}
        void solveSudoku(vector<vector<char> > &board) {
		is_empty.resize(board_size);
		for (int i = 0; i < board_size; ++i)
			for (int j = 0; j < board_size; ++j) {
				is_empty[i].resize(board_size);
				is_empty[i][j] = (board[i][j] == '.') ? true : false;
			}
		dfs(board, 0);
    }
};

There are two drawbacks. First, note the above code just adopt the exact the same code as in my previous post “leetcode: Valid Sudoku” to check whether a try of filling a number into an empty cell result in a valid partial board of not. It turns out to be not necessary. Instead, we only need to check the newly filled number whether this newly filled number has any conflict within the row, column or block it resides (Think about why?). Secondly, the extra is_empty vector is not needed either because we can test the original one stead. At the very first time, I just thought the original board would be destroyed so I have to keep a separate copy to test the current (copyright @sigmainfy)  cell is empty or not which is wrong. (Think about why again.) . Both of these two noted points could improve the time and space efficiency and result in the following simplified code:

class Solution {
public:
	const int board_size = 9;
	bool isValid(const vector<vector<char> > &board, int i, int j) {
		char c = board[i][j];
		int tmpi, tmpj;
		for (int k = 0; k < board_size; ++k) {  
			if (k != j && c == board[i][k]) return false;
			if (k != i && c == board[k][j]) return false;
			tmpi = 3 * (i / 3) + k / 3, tmpj = 3 * (j / 3) + k % 3;
			if ( !(tmpi == i && tmpj == j) && c == board[tmpi][tmpj]) return false;
		} 
		return true;
	}
	bool dfs(vector<vector<char> > &board, int n) {
		if (board_size * board_size == n) 
			return true;  				
		int i = n / board_size;
		int j = n % board_size;
		if ('.' != board[i][j]) return dfs(board, n + 1);
		for (char c = '1'; c <= '9'; ++c) {
			board[i][j] = c;
			if (!isValid(board, i, j)) continue;
			if (dfs(board, n + 1)) return true;
		}
		board[i][j] = '.';
		return false;
	}
        void solveSudoku(vector<vector<char> > &board) {
		bool ret = dfs(board, 0);
        }
};

There are still some other algorithm or different implementations: a) Dancing Link approach (quite complicated); b) BFS instead DFS to store all the partial state until we found the fully filled configuration of that board; You can google search them to find the details.

leetcode Sudoku Solver Remarks:

1. Try possible candidates for each empty cell, and don’t forget to set it back to empty cell when trying out all the valid candidates for that cell but failed.

  1. As far as I know, a partial sudoku board with 17 could have unique solution if it has a solution, if less than 17 cells are filled, it might have multiple solutions.
  2. There is no clear way to me to fast determine if a Sudoku has solution or not, it seems we have to use dfs to check anyways, i.e., we have to find exactly what the solution is to determine if a sudoku has a solution of not. I am just curious and if anyone could comment on this to tell whether a Sudoku has a solution or not without actually DFS the whole board, that would be awesome and please let me know, and that would be highly appreciated! Thanks a lot!

(全文完,原创文章,转载时请注明作者和出处)


(转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com,请勿用于任何商业用途)

Written on May 26, 2013