Human intelligence is superior to that of an algorithm
22/06/2023
The development presented in the previous article has been an opportunity to discover an interesting difficulty. The sudoku with the following constraints has no solution!
But it takes 1,873,812,290 iterations for the C-written program applying the algorithm presented in the article comparing different languages to reach this conclusion. More than a billion iterations is not a problem in itself for a computer, but the issue is that numerunique's server takes more than 47 seconds to execute them. And 47 seconds is an infinite time for a user who will have already decided after 2 seconds that the program is crashed.
Hence the need to optimize the automatic search processing for a sudoku solution. The new algorithm, inspired by the strategy implicitly proposed to the user of the proactive sudoku, finds a solution in 1,447 iterations to the sudoku chosen as an example for the comparison of different languages, while 1,453,557 iterations are necessary for the old algorithm. In this example, the processing time goes from 0.05 s to 0.02 s; more than twice as fast.
But for the particular case considered above, it's a disaster!
The new, "optimized" algorithm finds that there is no solution in only 26,440,176 iterations but takes more than 2 minutes to return its result :-((
The problem is bypassed by deciding on a maximum number of iterations chosen arbitrarily to leave room for the discovery of a solution if it exists but to give up deciding that there is no solution if it was too long to confirm. The user is then informed of the situation by a message such as:
"There are 248 alternatives left… but an improbable solution."
Thus assisted by the machine, human intelligence will make the right decision.
The corollary of this story is that optimizing an algorithm is a complex process…