Liklihood of recovery depends on how the drive was formatted and what was overwritten. If the drive had been partitioned and just the partition table was lost, then successful recovery is likely.
testdisk should be able to locate the encrypted partition. It will not be able to determine the correct size for the partition (there is nothing in the LUKS header that tells the size), so you will have to use a partitioning tool to extend the size manually.
If the entire, unpartitioned drive was encrypted and the LUKS header is now missing, no recovery is possible.
One fairly quick test you can do to see if there is a LUKS header present somewhere on the drive is to run a hex editor tool like
hexedit and search for the hexadecimal sequence "4C 55 4B 53 BA BE" (that's the ASCII characters "LUKS" followed by the hex bytes 0xBA and 0xBE). If that is found, then recovery might be possible. If it is not found, chances for recovery are nil. (It should be at the start of the disk or partition, so waiting several hours for the whole disk to be searched is probably pointless.)