Судоку

Задача:

Определить является ли заданый судоку правельным. Правела судоку можна посмотреть здесь.

Доска судоку будет не полностью заполнена, где пустые клетки будут позначены как '.'.

Например, на картинке показан частично заполненный судоку, который является правельным:

Замечание: Судоку не обязательно должен быть решонным, только заполненные клетки должны быть правельными.

Можно решить даную проблему в лоб, как это показано в следующем примере:

public static boolean isValidSudoku(char[][] board) {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    int value;
    char key;
    for(int i = 0; i < 9; i++) {        	
       	//check horizontal line
    	for(int j = 0; j < 9; j++) {
    		key = board[i][j];
    		if (key != '.') {
    			if (map.containsKey(key)) {
    				value = map.get(key);
        			if (value >= 1) {
        				return false;
        			} 
    			} else {
    				map.put(key, 1);
    			}
    		}
    	}
    	map.clear();
    	//check vertical line
    	for(int j = 0; j < 9; j++) {
    		key = board[j][i];
    		if (key != '.') {
    			if (map.containsKey(key)) {
    				value = map.get(key);
        			if (value >= 1) {
        				return false;
        			}
    			} else {
    				map.put(key, 1);
    			}
    		}
    	}
    	map.clear();
    }
    //check Sudoku in square 3x3
    for (int i = 0; i < 9; i+=3) {
    	for (int j = 0; j < 9; j+=3) {
    		for (int x = i; x < i+3; x++) {
        		for (int y = j; y < j+3; y++) {
        			key = board[x][y];
        			if (key != '.') {
        				if (map.containsKey(key)) {
        					value = map.get(key);
        	    			if (value >= 1) {
        	    				return false;
        	    			}
       				} else {
       					map.put(key, 1);
       				}
       			}
            	}
       	}
 	map.clear();
       }
   }
    	
   return true;
}

Либо же немножко подумаем и применим банальной математики))

Пример на Java:

public boolean isValidSudoku(char[][] board) {
    for(int i = 0; i<9; i++){
        HashSet<Character> rows = new HashSet<Character>();
        HashSet<Character> columns = new HashSet<Character>();
        HashSet<Character> cube = new HashSet<Character>();
        for (int j = 0; j < 9;j++){
            if(board[i][j]!='.' && !rows.add(board[i][j]))
                return false;
            if(board[j][i]!='.' && !columns.add(board[j][i]))
                return false;
            if(board[3*(i/3) + j/3][3*(i%3) + j%3]!='.' && !cube.add(board[3*(i/3) + j/3][3*(i%3) + j%3]))
                return false;
        }
    }
    return true;
}

Пример использования:

public static void main(String[] args) {
    char[][] board = {
    	{'5','3','.','.','7','.','.','.','.'},
    	{'6','.','2','1','9','5','.','.','.'},
    	{'.','9','8','.','.','.','.','6','.'},
    	{'8','.','.','.','6','.','.','.','3'},
    	{'4','.','.','8','.','3','.','.','1'},
    	{'7','.','.','.','2','.','.','.','6'},
    	{'.','6','.','.','.','.','2','8','.'},
    	{'.','.','.','4','1','9','.','.','5'},
    	{'.','.','.','.','8','.','.','7','9'},
    };
    boolean isValid = SolutionHashtable.isValidSudoku(board);
    System.out.println(isValid?"It is valid Sudoku!":"It is not valid Sudoku!!!");
}
LikeMe: