Ben oui.. le denier, celui avec 17 indices fait parti des plus durs je crois (il n'y a pas de sudoku à 16 indices il me semble)... Il prends 4ms à peu près avec luajit.
Code : Tout sélectionner
$ ./LuaJIT/src/luajit sudoku.lua
input: 1
[ , , , , , , , ,1]
[2,1, , , , ,9, ,4]
[4, ,3,5, , ,6, , ]
[9, , ,2, ,4,5, , ]
[ , ,2,7, ,5,8, , ]
[ , ,1,6, ,8, , ,3]
[ , ,4, , ,7,3, ,9]
[7, ,9, , , , ,6,8]
[1, , , , , , , , ]
solution:
[6,8,5,9,4,2,7,3,1]
[2,1,7,3,8,6,9,5,4]
[4,9,3,5,7,1,6,8,2]
[9,6,8,2,3,4,5,1,7]
[3,4,2,7,1,5,8,9,6]
[5,7,1,6,9,8,2,4,3]
[8,5,4,1,6,7,3,2,9]
[7,2,9,4,5,3,1,6,8]
[1,3,6,8,2,9,4,7,5]
depth: 52
time: 0.013 sec
input: 2
[ ,6, ,2,3, , , , ]
[ , ,8, , ,4, , , ]
[3, ,5, , ,8, ,4,7]
[ , ,2, , , , , ,1]
[5, , , ,6, , , ,9]
[9, , , , , ,7, , ]
[7,4, ,9, , ,5, ,6]
[ , , ,4, , ,9, , ]
[ , , , ,8,3, ,7, ]
solution:
[4,6,1,2,3,7,8,9,5]
[6,9,8,7,5,4,1,3,2]
[3,2,5,1,9,8,6,4,7]
[8,7,2,5,4,9,3,6,1]
[5,3,7,8,6,1,4,2,9]
[9,1,4,3,2,6,7,5,8]
[7,4,3,9,1,2,5,8,6]
[2,8,6,4,7,5,9,1,3]
[1,5,9,6,8,3,2,7,4]
depth: 55
time: 0.01 sec
input: 3
[ , ,3,8,5, , ,9, ]
[ , , , , , ,1, , ]
[6, , , , , , ,2,7]
[ , , ,1, , ,9, , ]
[ ,6, ,5, ,7, ,8, ]
[ , ,8, , ,3, , , ]
[1,5, , , , , , ,3]
[ , ,2, , , , , , ]
[ ,9, , ,8,5,4, , ]
solution:
[4,7,3,8,5,1,6,9,2]
[7,2,5,4,9,6,1,3,8]
[6,8,9,3,1,4,5,2,7]
[8,3,7,1,6,2,9,4,5]
[9,6,1,5,3,7,2,8,4]
[2,1,8,9,4,3,7,5,6]
[1,5,4,7,2,9,8,6,3]
[5,4,2,6,7,8,3,1,9]
[3,9,6,2,8,5,4,7,1]
depth: 58
time: 0.012 sec
input: 4
[ ,7,5, , ,6,8, , ]
[ , , , , , , , ,3]
[3, , ,5,1, ,6, , ]
[ ,2, , , , , , , ]
[ ,5,4,8, ,1,2,9, ]
[ , , , , , , ,5, ]
[ , ,2, ,5,9, , ,6]
[7, , , , , , , , ]
[ , ,3,1, , ,9,8, ]
solution:
[4,7,5,3,9,6,8,1,2]
[5,6,1,9,7,8,4,2,3]
[3,8,7,5,1,2,6,4,9]
[1,2,9,7,4,3,5,6,8]
[6,5,4,8,3,1,2,9,7]
[9,3,8,6,2,4,7,5,1]
[8,1,2,4,5,9,3,7,6]
[7,9,6,2,8,5,1,3,4]
[2,4,3,1,6,7,9,8,5]
depth: 56
time: 0.002 sec
input: 5
[6, ,5, , , , ,4, ]
[ , , , , ,2, ,7,6]
[ , , ,7, , ,3, , ]
[ , , ,6,2, , ,8, ]
[ ,8,7, ,5, ,6,2, ]
[ , , , ,8,4, , , ]
[ , ,1, , ,5, , , ]
[5,2, ,8, , , , , ]
[ ,6, , , , ,9, ,5]
solution:
[6,7,5,1,3,8,2,4,9]
[1,3,8,5,9,2,4,7,6]
[2,1,9,7,4,6,3,5,8]
[3,9,4,6,2,7,5,8,1]
[4,8,7,9,5,1,6,2,3]
[7,5,6,3,8,4,1,9,2]
[9,4,1,2,6,5,8,3,7]
[5,2,3,8,1,9,7,6,4]
[8,6,2,4,7,3,9,1,5]
depth: 56
time: 0.003 sec
input: 6
[ , , ,3,6, ,1, , ]
[ , , , ,8, , , , ]
[9,4,1,5, ,2, , , ]
[ ,5, , , ,8, , ,7]
[ ,6, , ,2, , ,9, ]
[8, , ,9, , , ,5, ]
[ , , ,1, ,6,9,7,8]
[ , , , ,4, , , , ]
[ , ,8, ,9,7, , , ]
solution:
[5,8,7,3,6,4,1,2,9]
[1,2,6,7,8,9,5,3,4]
[9,4,1,5,7,2,6,8,3]
[6,5,9,2,1,8,3,4,7]
[4,6,5,8,2,3,7,9,1]
[8,7,2,9,3,1,4,5,6]
[2,3,4,1,5,6,9,7,8]
[7,9,3,6,4,5,8,1,2]
[3,1,8,4,9,7,2,6,5]
depth: 55
time: 0.022 sec
input: 7
[9,7, , , , , , , ]
[3, ,5, , ,2,9,4, ]
[ , , , ,9,5, , , ]
[ , , ,2, , , , ,5]
[ , ,4, ,8, ,2, , ]
[5, , , , ,9, , , ]
[ , , ,6,7, , , , ]
[ ,8,2,9, , ,7, ,3]
[ , , , , , , ,8,1]
solution:
[9,7,1,8,2,6,5,3,4]
[3,1,5,7,6,2,9,4,8]
[1,4,7,3,9,5,8,2,6]
[6,3,9,2,1,8,4,7,5]
[7,6,4,1,8,3,2,5,9]
[5,2,8,4,3,9,6,1,7]
[8,5,3,6,7,4,1,9,2]
[4,8,2,9,5,1,7,6,3]
[2,9,6,5,4,7,3,8,1]
depth: 57
time: 0.016 sec
input: 8
[ , , , , ,3, , ,9]
[ ,4,8, , ,6, ,7,2]
[1, , , , , ,4, , ]
[7, ,9,4,3, , , , ]
[ , , , ,2, , , , ]
[ , , , ,6,7,2, ,1]
[ , ,2, , , , , ,7]
[9,3, ,7, , ,6,1, ]
[4, , ,6, , , , , ]
solution:
[2,5,4,1,7,3,8,6,9]
[3,4,8,5,9,6,1,7,2]
[1,7,6,2,8,9,4,3,5]
[7,2,9,4,3,1,5,8,6]
[6,8,1,3,2,5,7,9,4]
[5,9,3,8,6,7,2,4,1]
[8,6,2,9,1,4,3,5,7]
[9,3,5,7,4,2,6,1,8]
[4,1,7,6,5,8,9,2,3]
depth: 55
time: 0.002 sec
input: 9
[ , , ,1, , , , ,3]
[ , , , , ,5,8, , ]
[ ,1, , , ,7,6,9,4]
[ , , , ,5,8, , , ]
[ ,5,4,9, ,2,3,8, ]
[ , , ,7,1, , , , ]
[6,7,8,3, , , ,2, ]
[ , ,3,5, , , , , ]
[9, , , , ,1, , , ]
solution:
[7,8,6,1,9,4,2,5,3]
[4,2,1,6,7,5,8,3,9]
[5,1,2,8,3,7,6,9,4]
[3,9,7,2,5,8,4,1,6]
[1,5,4,9,6,2,3,8,7]
[2,6,9,7,1,3,5,4,8]
[6,7,8,3,4,9,1,2,5]
[8,4,3,5,2,6,9,7,1]
[9,3,5,4,8,1,7,6,2]
depth: 54
time: 0.004 sec
input: 10
[ , , , , , ,6, ,8]
[5,6,9,3, , , , , ]
[ , ,7,6, , , , , ]
[1, , , , , ,5, , ]
[ ,8, ,9,7,5, ,2, ]
[ ,5, , , , , , ,4]
[ , , , , ,7,2, , ]
[ , , , , ,4,7,5,3]
[9, ,3, , , , , , ]
solution:
[7,3,1,5,4,2,6,9,8]
[5,6,9,3,2,1,4,8,7]
[2,4,7,6,8,9,3,1,5]
[1,9,6,4,3,8,5,7,2]
[3,8,4,9,7,5,1,2,6]
[8,5,2,7,1,3,9,6,4]
[4,1,5,8,6,7,2,3,9]
[6,2,8,1,9,4,7,5,3]
[9,7,3,2,5,6,8,4,1]
depth: 57
time: 0.003 sec
input: 11
[ ,8, , , , ,1, ,3]
[7, ,9, , , ,8,2,4]
[ , ,5, , , , , ,7]
[ ,2, ,8, ,9, , , ]
[ , , ,4, ,1, , , ]
[ , , ,2, ,6, ,8, ]
[2, , , , , ,5, , ]
[4,5,1, , , ,3, ,2]
[8, ,7, , , , ,6, ]
solution:
[6,8,2,7,9,4,1,5,3]
[7,1,9,5,6,3,8,2,4]
[9,4,5,1,8,2,6,3,7]
[1,2,3,8,5,9,7,4,6]
[5,6,8,4,3,1,2,7,9]
[3,7,4,2,1,6,9,8,5]
[2,3,6,9,4,7,5,1,8]
[4,5,1,6,7,8,3,9,2]
[8,9,7,3,2,5,4,6,1]
depth: 54
time: 0.034 sec
input: 12
[ , ,6, , ,7,5,9, ]
[ , , , , , , ,2, ]
[ , , , ,6,3,1, , ]
[ ,9,5,8,7, , , ,2]
[ , , , ,4, , , , ]
[1, , , ,3,5,9,6, ]
[ , ,7,3,8, , , , ]
[ ,4, , , , , , , ]
[ ,5,9,7, , ,6, , ]
solution:
[8,3,6,2,1,7,5,9,4]
[3,6,1,9,5,4,7,2,8]
[7,2,4,5,6,3,1,8,9]
[6,9,5,8,7,1,4,3,2]
[2,7,3,1,4,9,8,5,6]
[1,8,2,4,3,5,9,6,7]
[9,1,7,3,8,6,2,4,5]
[5,4,8,6,9,2,3,7,1]
[4,5,9,7,2,8,6,1,3]
depth: 55
time: 0.003 sec
input: 13
[ , ,3, , ,9, ,6, ]
[7, ,8, , , ,4, ,9]
[5, , , , , ,2, , ]
[ , ,1,2, , , , , ]
[ , , ,8, ,5, , , ]
[ , , , , ,6,1, , ]
[ , ,5, , , , , ,4]
[8, ,4, , , ,3, ,7]
[ ,2, ,5, , ,9, , ]
solution:
[2,4,3,1,8,9,7,6,5]
[7,6,8,3,5,2,4,1,9]
[5,8,6,7,9,4,2,3,1]
[4,7,1,2,6,3,5,9,8]
[9,1,2,8,4,5,6,7,3]
[3,5,9,4,7,6,1,8,2]
[6,3,5,9,1,7,8,2,4]
[8,9,4,6,2,1,3,5,7]
[1,2,7,5,3,8,9,4,6]
depth: 58
time: 0.005 sec
input: 14
[ , , ,7,8, , , , ]
[ ,7, , , , ,2, , ]
[ ,1, ,5, , ,4,9,7]
[8, , , ,1,2,5, , ]
[5, , , , , , , ,6]
[ , ,6,3,5, , , ,4]
[4,3,2, , ,5, ,6, ]
[ , ,1, , , , ,5, ]
[ , , , ,3,9, , , ]
solution:
[3,2,4,7,8,6,9,1,5]
[1,7,5,9,6,4,2,3,8]
[6,1,3,5,2,8,4,9,7]
[8,6,9,4,1,2,5,7,3]
[5,4,7,8,9,1,3,2,6]
[2,9,6,3,5,7,1,8,4]
[4,3,2,1,7,5,8,6,9]
[9,8,1,6,4,3,7,5,2]
[7,5,8,2,3,9,6,4,1]
depth: 54
time: 0.011 sec
input: 15
[5, , , , ,7, , , ]
[ , , , , ,8,7, ,3]
[3,7, , ,1, , , ,2]
[2, , , , , ,5, , ]
[ , ,5,3,6,2,4, , ]
[ , ,1, , , , , ,8]
[6, , , ,9, , ,4,5]
[1, ,4,5, , , , , ]
[ , , ,2, , , , ,9]
solution:
[5,6,9,1,3,7,2,8,4]
[4,1,6,9,2,8,7,5,3]
[3,7,8,4,1,5,6,9,2]
[2,4,3,8,7,9,5,1,6]
[9,8,5,3,6,2,4,7,1]
[7,9,1,6,5,4,3,2,8]
[6,3,2,7,9,1,8,4,5]
[1,2,4,5,8,3,9,6,7]
[8,5,7,2,4,6,1,3,9]
depth: 55
time: 0.015 sec
input: 16
[ , , , ,5, ,6, , ]
[1, ,3, , , ,7, , ]
[4,5, ,3, , , , , ]
[ ,2, , , ,5, ,6, ]
[ ,4,9, ,2, ,1,8, ]
[ ,3, ,1, , , ,9, ]
[ , , , , ,8, ,1,6]
[ , ,5, , , ,9, ,3]
[ , ,6, ,3, , , , ]
solution:
[7,9,2,8,5,1,6,3,4]
[1,6,3,5,8,2,7,4,9]
[4,5,7,3,6,9,8,2,1]
[8,2,1,9,4,5,3,6,7]
[6,4,9,7,2,3,1,8,5]
[5,3,8,1,7,6,4,9,2]
[3,7,4,2,9,8,5,1,6]
[2,8,5,6,1,4,9,7,3]
[9,1,6,4,3,7,2,5,8]
depth: 55
time: 0.003 sec
input: 17
[ , , , , , , ,1, ]
[ , , , , ,2, , ,3]
[ , , ,4, , , , , ]
[ , , , , , ,5, , ]
[4, ,1,6, , , , , ]
[ , ,7,1, , , , , ]
[ ,5, , , , ,2, , ]
[ , , , ,8, , ,4, ]
[ ,3, ,9,1, , , , ]
solution:
[5,4,9,2,3,7,6,1,8]
[1,8,4,5,6,2,9,7,3]
[8,7,6,4,2,9,3,5,1]
[9,1,8,3,7,4,5,6,2]
[4,2,1,6,5,8,7,3,9]
[3,6,7,1,9,5,8,2,4]
[7,5,3,8,4,1,2,9,6]
[6,9,2,7,8,3,1,4,5]
[2,3,5,9,1,6,4,8,7]
depth: 65
time: 0.004 sec
total time: 0.165 sec
a été résolu chez moi en 5ms... Alors soit j'ai un bug dans l'algo de recherche, soit ce qui est dur pour les humains ne l'est pas forcément pour un algo (triez 10 000 fiches par ordres alphabétiques pour voir), soit les notion de "hardest sudoku" c'est du pipeau total.