Editing Brute-force search (section)

==Combinatorial explosion==
The main disadvantage of the brute-force method is that, for many real-world problems, the number of natural candidates is prohibitively large. For instance, if we look for the divisors of a number as described above, the number of candidates tested will be the given number ''n''. So if ''n'' has sixteen decimal digits, say, the search will require executing at least 10<sup>15</sup> computer instructions, which will take several days on a typical [[personal computer|PC]]. If ''n'' is a random 64-[[binary digit|bit]] natural number, which has about 19 decimal digits on the average, the search will take about 10 years. This steep growth in the number of candidates, as the size of the data increases, occurs in all sorts of problems. For instance, if we are seeking a particular rearrangement of 10 letters, then we have 10! = 3,628,800 candidates to consider, which a typical PC can generate and test in less than one second. However, adding one more letter{{snd}}which is only a 10% increase in the data size{{snd}}will multiply the number of candidates by 11, a 1000% increase. For 20 letters, the number of candidates is 20!, which is about 2.4×10<sup>18</sup> or 2.4 [[quintillion]]; and the search will take about 10 years. This unwelcome phenomenon is commonly called the [[combinatorial explosion]], or the [[curse of dimensionality]].

One example of a case where combinatorial complexity leads to solvability limit is in [[solving chess]]. Chess is not a [[solved game]]. In 2005, all chess game endings with six pieces or less were solved, showing the result of each position if played perfectly. It took ten more years to complete the tablebase with one more chess piece added, thus completing a 7-piece tablebase. Adding one more piece to a chess ending (thus making an 8-piece tablebase) is considered intractable due to the added combinatorial complexity.<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=Lomonosov Endgame Tablebases |url=http://chessok.com/?page_id=27966 |website=ChessOK |archive-url= https://web.archive.org/web/20190406123519/http://chessok.com/?page_id=27966|archive-date=April 6, 2019}}</ref><ref name="8manestimate">{{cite web |last1=de Man |first1=Ronald |title=What is the best way to obtain the 7-piece tablebases? - Page 3 - TalkChess.com |url=http://talkchess.com/forum3/viewtopic.php?f=2&t=74185&sid=016570559fa97e785404dd65020c0ad6&start=20#p848245 |website=talkchess.com |access-date=9 November 2022 |archive-url=https://archive.today/20221109020208/http://talkchess.com/forum3/viewtopic.php?f=2&t=74185&sid=016570559fa97e785404dd65020c0ad6&start=20%23p848245 |archive-date=9 November 2022 |url-status=live}}</ref>