Do Place & Route algorithms of modern FPGA design tools ( Qaurtus / Vivado / etc... ) have inbuilt randomness in them ?
I.E: Would it be possible to get 2 different results when compiling the same design twice ( given the same software version ) ?
TL;DR; The answer may depend on the synthesis tools, but most likely the answer is no unless you use randomised seeds.
Certainly for modern versions of Intel/Altera Quartus (since some time before 12.1), if you compile the exact same source files using the exact same software version (including subversion/patch level) for the same device, you will get the same result each time.
The synthesis tools for Quartus do use randomisation when searching for the best fit - they will try lots of different pathways to fit the design. However they make use of a seed value for their PRNG. This value is a constant which doesn't change from compile to compile. You can of course manually change it in the compilation settings.
The net result of using a fixed seed is that no matter how many times you compile the design, you get deterministic results.
Quartus does have a tool called Design Space Explorer that allows the design to be compiled multiple times with different seed values to try to find one that results in a better fitting. But that will allow you to save the seed value once found for future deterministic compiles.
This is actually very useful behaviour. Say you want to use source control to keep all of your source files safe, but don't want to check in the compiled netlists - you need to be able to recreate the netlists/bitstreams from source without them changing. Or you want to update a memory initialisation file. You don't want the whole design to change just to change a default memory value (e.g. instruction data for a soft processor).
There are two separate issues here, the issue of determinism and of pseudo random results.
Speaking to Quartus: Quartus Does initial operations off of random seeds. If you change nothing and build again you get the same result however there are two comments: In your QSF file if you change even a file path (relative to absolute, etc.) you will get a different result. Such things inherently change the seed. You can explicitly set the seed in the project settings or QSF.
Vivado: Vivado does not have explicitly accessible randomization as such. I find my builds in vivado are inherently deterministic but I suspect Xilinx may still do some deterministic seed based pseudo randomization on initial placements / routing decisions. One notion that supports this is that if you make one very minor change to the design you could get wildly differing results. I find the best way to achieve different design results it to sweep design strategies (of which there are ~32).
In both tools by rebuilding and changing nothing the same build result is achieved. That said many build environments do things (such as stage builds in dated folders) that would cause Quartus to take on a new seed.