sys.argv : ['sudoku_tut.py', '778'] INDICE : 778 *************************************************************** * * * Problem definition * * * *************************************************************** The n×n Sudoku problem is defined over a grid of n^2 × n^2 cells that each contains a number between 1 and n^2. This grid is subdivided in n^2 sub-grids of size n × n. A solved Sudoku grid is such that the numbers in every row, column and n × n sub-grids are all different. In the particular case of n= 3 , n^2= 9 The 3 × 3 Sudoku problem is defined over a grid of 9 × 9 = 81 cells that each contains a number between 1 and 9 . This grid is subdivided in 9 sub-grids of size 3 × 3 . A solved Sudoku grid is such that the numbers in every row, column and 3 × 3 sub-grids are all different. *************************************************************** * * * Builds the problem * * *************************************************************** -> Create 81 variables : X1.1 X1.2 X1.3 X1.4 X1.5 X1.6 X1.7 X1.8 X1.9 X2.1 X2.2 X2.3 X2.4 X2.5 X2.6 X2.7 X2.8 X2.9 X3.1 X3.2 X3.3 X3.4 X3.5 X3.6 X3.7 X3.8 X3.9 X4.1 X4.2 X4.3 X4.4 X4.5 X4.6 X4.7 X4.8 X4.9 X5.1 X5.2 X5.3 X5.4 X5.5 X5.6 X5.7 X5.8 X5.9 X6.1 X6.2 X6.3 X6.4 X6.5 X6.6 X6.7 X6.8 X6.9 X7.1 X7.2 X7.3 X7.4 X7.5 X7.6 X7.7 X7.8 X7.9 X8.1 X8.2 X8.3 X8.4 X8.5 X8.6 X8.7 X8.8 X8.9 X9.1 X9.2 X9.3 X9.4 X9.5 X9.6 X9.7 X9.8 X9.9 ... with such indices : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 -> Keep those 81 variables indices in rows, columns and cells (each listing 9 lists of 9 variables indices). Those 3* 9 = 27 lists of 9 indices correspond with the sets of variables whose values have to be different (every row, every column and every sub-grids). rows = [ [0, 1, 2, 3, 4, 5, 6, 7, 8] [9, 10, 11, 12, 13, 14, 15, 16, 17] [18, 19, 20, 21, 22, 23, 24, 25, 26] [27, 28, 29, 30, 31, 32, 33, 34, 35] [36, 37, 38, 39, 40, 41, 42, 43, 44] [45, 46, 47, 48, 49, 50, 51, 52, 53] [54, 55, 56, 57, 58, 59, 60, 61, 62] [63, 64, 65, 66, 67, 68, 69, 70, 71] [72, 73, 74, 75, 76, 77, 78, 79, 80] ] columns = [ [0, 9, 18, 27, 36, 45, 54, 63, 72] [1, 10, 19, 28, 37, 46, 55, 64, 73] [2, 11, 20, 29, 38, 47, 56, 65, 74] [3, 12, 21, 30, 39, 48, 57, 66, 75] [4, 13, 22, 31, 40, 49, 58, 67, 76] [5, 14, 23, 32, 41, 50, 59, 68, 77] [6, 15, 24, 33, 42, 51, 60, 69, 78] [7, 16, 25, 34, 43, 52, 61, 70, 79] [8, 17, 26, 35, 44, 53, 62, 71, 80] ] cells = [ [0, 1, 2, 9, 10, 11, 18, 19, 20] [3, 4, 5, 12, 13, 14, 21, 22, 23] [6, 7, 8, 15, 16, 17, 24, 25, 26] [27, 28, 29, 36, 37, 38, 45, 46, 47] [30, 31, 32, 39, 40, 41, 48, 49, 50] [33, 34, 35, 42, 43, 44, 51, 52, 53] [54, 55, 56, 63, 64, 65, 72, 73, 74] [57, 58, 59, 66, 67, 68, 75, 76, 77] [60, 61, 62, 69, 70, 71, 78, 79, 80] ] -> Add the clique constraints on rows, columns and cells : addCliqueAllDiff for each row, each column, each cell. *************************************************************** * * * Solving some grids * * * *************************************************************** Here are some prefilled grids/solutions coming from the validation set of the RRN paper (0 meaning unknown) : List of 18000 hints : hints = ['802100050190600040000020073004508910789230500010094000500306200230070000000010700' '000004021084000000000900040025030069300096800006100000000380900400009700200000000' '000073000630800050874010030205009803040530600000000705087000502000400090103000000' ... '380900650020000790000006000860305007000400000070000000519000008008072409000010000' '000608000200010007800200000000090065018000000000300000900530000040000180000000200' '100050400200000090000400000000809070372000000500000000080700000000000201000043500'] List of their solutions : sols = ['872143659193657842456829173324568917789231564615794328547386291231975486968412735' '973864521684521397512973648125738469347296815896145273761382954458619732239457186' '952673184631824957874915236215769843748532619369148725487391562526487391193256478' ... '387924651426158793195736842864395127251487936973261584519643278638572419742819365' '193678524264915837875243691427891365318456972659327418981532746542769183736184259' '169257438254138796837496152416829375372564819598371624685712943743985261921643587'] Let's solve one of those cases, hints[i] where i in 0 ... 17999 . *************************************************************** Here, let's solve hints[ 778 ] : hints[ 778 ] = 040800002100000060000105790020507400060090010008001000900010500600000870200603000 grid = [0, 4, 0, 8, 0, 0, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 1, 0, 5, 7, 9, 0, 0, 2, 0, 5, 0, 7, 4, 0, 0, 0, 6, 0, 0, 9, 0, 0, 1, 0, 0, 0, 8, 0, 0, 1, 0, 0, 0, 9, 0, 0, 0, 1, 0, 5, 0, 0, 6, 0, 0, 0, 0, 0, 8, 7, 0, 2, 0, 0, 6, 0, 3, 0, 0, 0] -> Creation of costs functions to represent the values predefinition : Predefined values into grid (0 for undefined) are : 0 4 0 8 0 0 0 0 2 1 0 0 0 0 0 0 6 0 0 0 0 1 0 5 7 9 0 0 2 0 5 0 7 4 0 0 0 6 0 0 9 0 0 1 0 0 0 8 0 0 1 0 0 0 9 0 0 0 1 0 5 0 0 6 0 0 0 0 0 8 7 0 2 0 0 6 0 3 0 0 0 (memo) Variables names are : X1.1 X1.2 X1.3 X1.4 X1.5 X1.6 X1.7 X1.8 X1.9 X2.1 X2.2 X2.3 X2.4 X2.5 X2.6 X2.7 X2.8 X2.9 X3.1 X3.2 X3.3 X3.4 X3.5 X3.6 X3.7 X3.8 X3.9 X4.1 X4.2 X4.3 X4.4 X4.5 X4.6 X4.7 X4.8 X4.9 X5.1 X5.2 X5.3 X5.4 X5.5 X5.6 X5.7 X5.8 X5.9 X6.1 X6.2 X6.3 X6.4 X6.5 X6.6 X6.7 X6.8 X6.9 X7.1 X7.2 X7.3 X7.4 X7.5 X7.6 X7.7 X7.8 X7.9 X8.1 X8.2 X8.3 X8.4 X8.5 X8.6 X8.7 X8.8 X8.9 X9.1 X9.2 X9.3 X9.4 X9.5 X9.6 X9.7 X9.8 X9.9 (memo) Variables indices are : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 For each variable whose value is known (predefined into grid), creation of a cost function equal to 0 for its value and equal to UB else. For example : => A cost function created for variables and their indices : ['X1.2', 'X1.4', 'X1.9', 'X2.1', 'X2.8', 'X3.4', 'X3.6', 'X3.7', 'X3.8', 'X4.2', 'X4.4', 'X4.6', 'X4.7', 'X5.2', 'X5.5', 'X5.8', 'X6.3', 'X6.6', 'X7.1', 'X7.5', 'X7.7', 'X8.1', 'X8.7', 'X8.8', 'X9.1', 'X9.4', 'X9.6'] [1, 3, 8, 9, 16, 21, 23, 24, 25, 28, 30, 32, 33, 37, 40, 43, 47, 50, 54, 58, 60, 63, 69, 70, 72, 75, 77] -> Solve... => Solution found : 7 4 9 8 3 6 1 5 2 1 5 2 4 7 9 3 6 8 8 3 6 1 2 5 7 9 4 3 2 1 5 6 7 4 8 9 4 6 7 3 9 8 2 1 5 5 9 8 2 4 1 6 3 7 9 8 3 7 1 4 5 2 6 6 1 4 9 5 2 8 7 3 2 7 5 6 8 3 9 4 1 (memo) Predefined values into grid : 0 4 0 8 0 0 0 0 2 1 0 0 0 0 0 0 6 0 0 0 0 1 0 5 7 9 0 0 2 0 5 0 7 4 0 0 0 6 0 0 9 0 0 1 0 0 0 8 0 0 1 0 0 0 9 0 0 0 1 0 5 0 0 6 0 0 0 0 0 8 7 0 2 0 0 6 0 3 0 0 0 (memo) The solution given with grid was : 7 4 9 8 3 6 1 5 2 1 5 2 4 7 9 3 6 8 8 3 6 1 2 5 7 9 4 3 2 1 5 6 7 4 8 9 4 6 7 3 9 8 2 1 5 5 9 8 2 4 1 6 3 7 9 8 3 7 1 4 5 2 6 6 1 4 9 5 2 8 7 3 2 7 5 6 8 3 9 4 1 ***************************************************************