#include #include #include #include #include class NQueensSolver $\{$ private: std::random$\_$device rd; std::mt$19937$ gen; int getConflicts$($const std::vector& board, int row, int col, int n$)\{$ int conflicts $=0$; for $($int i $=0$; i $<$ n; i$++)\{$ if $($i $==$ row$)$ continue; if $($board$[$i$]==$ col $||$ abs$($i $-$ row$)==$ abs$($board$[$i$]-$ col$))\{$ conflicts$++$; $\}\}$ return conflicts; $\}$ public: NQueensSolver$()$ : gen$($rd$())\{\}$ std::vector solve$($int n$,$ int maxSteps $=100)\{$ auto start $=$ std::chrono::high$\_$resolution$\_$clock::now$()$; $//$ Initial random placement std::vector board$($n$)$; std::uniform$\_$int$\_$distribution$<>$ dis$(0,$ n$-1)$; for $($int i $=0$; i $<$ n; i$++)\{$ board$[$i$]=$ dis$($gen$)$; $\}//$ MinConflicts algorithm for $($int step $=0$; step $<$ maxSteps $*$ n; step$++)\{//$ Find a queen with conflicts int row $=$ dis$($gen$)$; int currentConflicts $=$ getConflicts$($board$,$ row, board$[$row$],$ n$)$; if $($currentConflicts $==0)$ continue; $//$ Find position with minimum conflicts int minConflicts $=$ n; std::vector bestCols; for $($int col $=0$; col $<$ n; col$++)\{$ int conflicts $=$ getConflicts$($board$,$ row, col, n$)$; if $($conflicts $<$ minConflicts$)\{$ minConflicts $=$ conflicts; bestCols.clear$()$; bestCols.push$\_$back$($col$)$; $\}$ else if $($conflicts $==$ minConflicts$)\{$ bestCols.push$\_$back$($col$)$; $\}\}//$ Move queen to random best position board$[$row$]=$ bestCols$[$dis$($gen$)\%$ bestCols.size$()]$; $//$ Check if solved bool solved $=$ true; for $($int i $=0$; i $<$ n && solved; i$++)\{$ if $($getConflicts$($board$,$ i$,$ board$[$i$],$ n$)>0)\{$ solved $=$ false; $\}\}$ if $($solved$)\{$ if $($n $>100)\{$ auto end $=$ std::chrono::high$\_$resolution$\_$clock::now$()$; std::chrono::duration diff $=$ end $-$ start; std::cout $<<$ std::fixed $<<$ std::setprecision$(2)<<$ diff.count$()<<$ std::endl; $\}$ return board; $\}\}$ return std::vector$()$; $//$ Empty vector indicates failure $\}$ void printBoard$($const std::vector& board$)\{$ if $($board$.$empty$())\{$ std::cout $<<-1<<$ std::endl; return; $\}$ int n $=$ board.size$()$; if $($n $<=100)\{$ for $($int i $=0$; i $<$ n; i$++)\{$ for $($int j $=0$; j $<$ n; j$++)\{$ std::cout $<<($board$[$i$]==$ j $?\text{'}*\text{'}$ : $\text{'}\_\text{'})<<\text{'}\text{'}$; $\}$ std::cout $<<$ std::endl; $\}\}\}\}$; int main$()\{$ int n; std::cin $>>$ n; NQueensSolver solver; std::vector solution $=$ solver.solve$($n$)$; $//$ For testing tool std::cout $<<"["$; for $($size$\_$t i $=0$; i $<$ solution.size$()$; i$++)\{$ if $($i $>0)$ std::cout $<<","$; std::cout $<<$ solution$[$i$]$; $\}$ std::cout $<<"]"<<$ std::endl; $//$ Print board visualization solver.printBoard$($solution$)$; return $0$; $\}$ this algorithms is too slow. optimize it as max as possible using also minconflicts to work with N$=10000$ for less than one second