Skip to content

pl3onasm/Square-sum-problem

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

20 Commits
 
 
 
 
 
 

Repository files navigation

$\color{cadetblue}{\text{\huge Square-sum Problem}}$


The problem as explained by Matt Parker:

Problem


${\color{rosybrown}\text{\Large Program usage}}$

The program makes use of a backtracking algorithm, guided by a heuristic that prioritizes vertices having the least degree (i.e. the least number of edges connecting them to the remaining unvisited ones) in order to avoid potential dead ends. The program is capable of computing Hamiltonian paths for inputs up to 20'000 relatively easily. If no path exists, the output is None.


${\color{darkseagreen}\text{\large Example input}}$

python3 squaresum.py 23

${\color{darkseagreen}\text{\large Example output}}$

[18, 7, 9, 16, 20, 5, 11, 14, 2, 23, 13, 12, 4, 21, 15, 10, 6, 19, 17, 8, 1, 3, 22]

 

If this example leaves you with an appetite for more, have a look at the Hamiltonian path for 21'000: path.

Please note that for large paths, you may have to increase the stack size in order to avoid a segmentation fault. This can be done in the terminal:

ulimit -s unlimited

Releases

No releases published

Packages

No packages published

Languages