On Killer Sudoku Online, (http://www.killersudokuonline.com/) there is a very interesting Sudoku variant — Greater Than Sudoku. The right figure shows a Greater Than Su- doku puzzle. As you can see, there is abso- lutely no number to start with! There are only “greater-than signs” (>) between the cells. Beside usual Sudoku rules, there is an extra one: all greater-than signs must be satisfied, i.e. each of them must point from a larger number to a smaller one. If there is no number given, then where shall we begin? Look at the partial puzzle shown in the left. Note that the centre cell (coloured in blue) is the only cell in its “big square” with all its greater-than signs pointing inwards. There- fore, it must contain the smallest number, i.e. 1 (one). Together with the usual Sudoku skills and some new tricks, we can solve the puzzle completely. Input This sample puzzle is discussed in great detail in ReallyEvilCanine’s blog (A Day in the Life: Solving Greater Than Sudoku Puzzles — http://stuckinthecube.blogspot.com/2007/05/ solving-greater-than-sudoku-puzzles.html) Write a program that solves Greater Than Sudoku puzzles. In short, for each puzzle, we need to complete the grid so that each row, column and 3 × 3 box contains every digit from 1 to 9 (inclusive), and each greater-than sign points from a larger digit to a smaller one. Input contains less than 10 test cases, each giving the greater-than signs in a Sudoku puzzle. Consecutive cases are separated by a blank line. The sample input below corresponds to the sample puzzle shown in the above figure. All input cases will follow the format of this sample exactly. Output For each test case, output the solution for the puzzle. Adjacent numbers in a row should be separated by a space, and consecutive sets of output should be separated by an empty line. You can be sure that there is one and only one solution for each input puzzle.
2/3 Sample Input ><<<>< v^vv^v^^v <<<><< v^v^vv^^v <<<<>> <>>><> vv^^v^^vv <>><>> ^vvv^vv^v ><<>>> <>>>>< vvvv^^^^^ ><<<<< ^^^^^vvv^ >><><< ><<<>< v^vv^v^^v <<<><< v^v^vv^^v <<<<>> <>>><> vv^^v^^vv <>><>> ^vvv^vv^v ><<>>> <>>>>< vvvv^^^^^ ><<<<< ^^^^^vvv^ >><><< Sample Output 539468217 248197356 167235984 681742593 375916842 924583761 796821435 412359678 853674129 539468217 248197356 167235984 681742593 375916842
3/3 924583761 796821435 412359678 853674129