{"id":712,"date":"2012-01-20T23:10:54","date_gmt":"2012-01-20T23:10:54","guid":{"rendered":"http:\/\/41j.com\/blog\/?p=712"},"modified":"2012-01-20T23:12:21","modified_gmt":"2012-01-20T23:12:21","slug":"solving-tic-tac-toe-noughts-and-crosses","status":"publish","type":"post","link":"https:\/\/41j.com\/blog\/2012\/01\/solving-tic-tac-toe-noughts-and-crosses\/","title":{"rendered":"Solving tic-tac-toe (Noughts and crosses)"},"content":{"rendered":"<p>The following is a simple recursive solver for tic-tac-toe games, which I used to answer a <a href=\"http:\/\/www.quora.com\/How-many-Xs-winning-solutions-in-a-tic-tac-toe-game-with-this-board-and-what-are-they\">Quora question<\/a>. It&#8217;s hardcoded to solve the board:<\/p>\n<pre class=\"brush: bash; title: ; notranslate\" title=\"\">\r\nOO_\r\n___\r\nXX_\r\n<\/pre>\n<p>Here&#8217;s the code:<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;vector&gt;\r\n#include &lt;iostream&gt;\r\n\r\nusing namespace std;\r\n\r\nvoid dump_board(vector&lt;vector&lt;int&gt; &gt; &amp;board) {\r\n\r\n  for(size_t y=0;y&lt;board.size();y++) {\r\n    for(size_t x=0;x&lt;board.size();x++) {\r\n      if(board&#x5B;x]&#x5B;y] == 0) cout &lt;&lt; &quot;_&quot;;\r\n      if(board&#x5B;x]&#x5B;y] == 1) cout &lt;&lt; &quot;O&quot;;\r\n      if(board&#x5B;x]&#x5B;y] == 2) cout &lt;&lt; &quot;X&quot;;\r\n    }\r\n    cout &lt;&lt; endl;\r\n  }\r\n  cout &lt;&lt; endl;\r\n}\r\n\r\nclass Move {\r\n\r\npublic:\r\n\r\n  Move() {}\r\n\r\n  Move(int x_in,int y_in) : x(x_in), y(y_in) {}\r\n\r\n  int x;\r\n  int y;\r\n};\r\n\r\n\r\nint check_win(vector&lt;vector&lt;int&gt; &gt; &amp;board) {\r\n\r\n  \/\/ cols\r\n  for(int x=0;x&lt;board.size();x++) {\r\n    bool win=true;\r\n    for(int y=0;y&lt;board&#x5B;x].size();y++) {\r\n      if(board&#x5B;x]&#x5B;y] != board&#x5B;x]&#x5B;0]) win = false;\r\n    }\r\n    if((board&#x5B;x]&#x5B;0] != 0) &amp;&amp; (win == true)) return board&#x5B;x]&#x5B;0];\r\n  }\r\n\r\n  \/\/ rows\r\n  for(int y=0;y&lt;board.size();y++) {\r\n    bool win=true;\r\n    for(int x=0;x&lt;board.size();x++) {\r\n      if(board&#x5B;x]&#x5B;y] != board&#x5B;0]&#x5B;y]) win = false;\r\n    }\r\n    if((board&#x5B;0]&#x5B;y] != 0) &amp;&amp; (win == true)) return board&#x5B;0]&#x5B;y];\r\n  }\r\n\r\n  \/\/ diags\r\n  if((board&#x5B;0]&#x5B;0] == board&#x5B;1]&#x5B;1]) &amp;&amp; (board&#x5B;0]&#x5B;0] == board&#x5B;2]&#x5B;2])) return board&#x5B;0]&#x5B;0];\r\n  if((board&#x5B;0]&#x5B;2] == board&#x5B;1]&#x5B;1]) &amp;&amp; (board&#x5B;0]&#x5B;2] == board&#x5B;2]&#x5B;0])) return board&#x5B;0]&#x5B;2];\r\n\r\n  return -1;\r\n}\r\n\r\nvector&lt;Move&gt; get_available_moves(vector&lt;vector&lt;int&gt; &gt; &amp;board) {\r\n\r\n  vector&lt;Move&gt; moves;\r\n\r\n  for(size_t x=0;x&lt;board.size();x++) {\r\n    for(size_t y=0;y&lt;board&#x5B;x].size();y++) {\r\n      if(board&#x5B;x]&#x5B;y] == 0) moves.push_back(Move(x,y));\r\n    }\r\n  }\r\n\r\n  return moves;\r\n}\r\n\r\nint play(int player,vector&lt;vector&lt;int&gt; &gt; board) {\r\n  vector&lt;Move&gt; moves = get_available_moves(board);\r\n\r\n  for(size_t n=0;n&lt;moves.size();n++) {\r\n    vector&lt;vector&lt;int&gt; &gt; n_board = board;\r\n    n_board&#x5B;moves&#x5B;n].x]&#x5B;moves&#x5B;n].y] = player;\r\n    int win = check_win(n_board);\r\n    if(win == 2) dump_board(n_board);\r\n\r\n    if(win == -1) {\r\n\r\n      if(player == 1) player = 2; else player = 1;\r\n      play(player,n_board);\r\n    }\r\n  }\r\n}\r\n\r\n\r\nint main(int argc,char **argv) {\r\n\r\n  vector&lt;vector&lt;int&gt; &gt; board(3,vector&lt;int&gt;(3,0));\r\n\r\n  board&#x5B;0]&#x5B;0] = 1;\r\n  board&#x5B;1]&#x5B;0] = 1;\r\n  board&#x5B;0]&#x5B;2] = 2;\r\n  board&#x5B;1]&#x5B;2] = 2;\r\n\r\n  dump_board(board);\r\n\r\n  play(2,board);\r\n}\r\n<\/pre>\n<p>And the solutions found were:<\/p>\n<pre class=\"brush: bash; title: ; notranslate\" title=\"\">\r\n\r\nOOX\r\nXOO\r\nXXX\r\n\r\nOOX\r\nXO_\r\nXXX\r\n\r\nOO_\r\nXO_\r\nXXX\r\n\r\nOOX\r\nXOX\r\nXXX\r\n\r\nOOX\r\nX_X\r\nXXX\r\n\r\nOOX\r\nXX_\r\nXXO\r\n\r\nOOX\r\nXXO\r\nXXO\r\n\r\nOO_\r\nX__\r\nXXX\r\n\r\nOO_\r\nXO_\r\nXXX\r\n\r\nOO_\r\n_O_\r\nXXX\r\n\r\nOOX\r\nOX_\r\nXX_\r\n\r\nOOX\r\nOOX\r\nXXX\r\n\r\nOOX\r\nO_X\r\nXXX\r\n\r\nOOX\r\nOX_\r\nXXO\r\n\r\nOOX\r\n_X_\r\nXX_\r\n\r\nOOX\r\nOXX\r\nXX_\r\n\r\nOOX\r\nO_X\r\nXXX\r\n\r\nOOX\r\n_XX\r\nXX_\r\n\r\nOOX\r\n__X\r\nXXX\r\n\r\nOOX\r\nXXO\r\nXXO\r\n\r\nOOX\r\nXOO\r\nXXX\r\n\r\nOOX\r\nX_O\r\nXXX\r\n\r\nOOX\r\nOXO\r\nXX_\r\n\r\nOOX\r\nO_O\r\nXXX\r\n\r\nOOX\r\n_XO\r\nXX_\r\n\r\nOOX\r\n__O\r\nXXX\r\n\r\nOO_\r\n___\r\nXXX\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>The following is a simple recursive solver for tic-tac-toe games, which I used to answer a Quora question. It&#8217;s hardcoded to solve the board: OO_ ___ XX_ Here&#8217;s the code: #include &lt;vector&gt; #include &lt;iostream&gt; using namespace std; void dump_board(vector&lt;vector&lt;int&gt; &gt; &amp;board) { for(size_t y=0;y&lt;board.size();y++) { for(size_t x=0;x&lt;board.size();x++) { if(board&#x5B;x]&#x5B;y] == 0) cout &lt;&lt; &quot;_&quot;; if(board&#x5B;x]&#x5B;y] [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-712","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-bu","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/712","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=712"}],"version-history":[{"count":2,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/712\/revisions"}],"predecessor-version":[{"id":714,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/712\/revisions\/714"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=712"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=712"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=712"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}