View Single Post
Old 2021-07-20, 22:10   #9
Viliam Furik
 
Viliam Furik's Avatar
 
"Viliam Furík"
Jul 2018
Martin, Slovakia

23·5·17 Posts
Default

I have a few updates on this topic.

1. The proof of correctness for the algorithm is not as correct as I thought... But it's incorrect in a way that the proof for one key aspect of the algorithm is missing, which still allows the possibility of it being true, but it's hard to say for sure without good proof.

2. Meanwhile, a friend of our friend helped us find a counterexample, in which the algorithm failed. It was basically a type of infinitely many counterexamples. But we have managed to quickly patch it up by adding a feature (basically error-check), which we actually considered in the creation process, but thought it can not be done in polynomial time, so we ignored it. Turns out, it is doable in polynomial time... So far, we haven't come up with another counterexample.

We are trying to find proof of correctness or another counterexample, but so far no luck with either. So if there is someone with enough free time and willing to help, we will be happy to have another helping hand (brain, actually).

The problem the algorithm is solving is Generalised Sudoku, i.e. Sudoku where the grid is made of n by n squares of n by n cells. The classic newspaper Sudoku is n=3.

We have a working (the updated version works for all tested grids so far) implementation of the algorithm in Python, which is not a fast language, but it is the only one I know well enough and it's quite easy to make such implementations in it.

If you are willing to help in any way, please, send me a PM.
Viliam Furik is offline   Reply With Quote