1000x1000のNクイーン問題を解く

元々はいくつかのクイーンが置かれた状態で、残りのクイーンを置くことができるかどうかの判定問題が NP完全、#P完全だと主張する論文についての話のようですが、どうしてこんな記事になってしまったのか。

Ian P. Gent, Christopher Jefferson and Peter Nightingale (2017) Complexity of n-Queens Completion

上記のギズモード記事では、1000x1000のNクイーン問題がまるで万物の答えのように書かれていますが、

過去に

PKU3239 Solution to the n Queens Puzzle 3239 -- Solution to the n Queens Puzzle

を解いた際の使ったコードを利用したら、 1000x1000サイズのn-queenが18秒ぐらいで解が1つ出力されました。

バックトラッキングと乱択の組み合わせアルゴリズムになっています。

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

const int NUM = 1001;
int board[NUM];
int perm[NUM];
int cnt = 0;
int limit;

bool put(int k,int n){ 
    if(cnt>limit) {
      return false;
    }
    cnt++;
    if(k==n) { return true; }
    bool flag[n];

    memset(flag,1,sizeof(flag));

    for(int i=0;i<k;i++){
        flag[board[i]] = false;
        if(board[i]-(k-i) >= 0) {
            flag[board[i]-(k-i)] = false;
        }
        if(board[i]+(k-i) < n) {
            flag[board[i]+(k-i)] = false;
        }
    }

    for(int i=0;i<n;i++){ 
        if(flag[perm[i]]){
            board[k] = perm[i];
            if(put(k+1,n)) { return true; }
        }
    }
    return false;
}

int main(){
  int n = 1000;

  for(int i=0;i<n;i++) {
    perm[i] = i;
  }

  limit = 1500; //limit回探索しても見つからなければもう一度置く順番を入れ替え
  do{
    //バックトラックで置く順番をランダムに定める
    random_shuffle(perm,perm+n);
    cnt = 0;
  }while(!put(0,n));

  for(int i=0;i<n-1;i++){
    printf("%d ",board[i]+1);
  }
  printf("%d\n",board[n-1]+1);
  return 0;
}

出力結果

% time ./a.out
354 455 657 762 764 870 656 996 115 647 944 799 792 108 941 497 120 702 711 424 283 74 962 365 300 937 498 343 297 64 296 325 208 797 391 28 470 127 822 546 787 245 14 547 277 282 710 650 648 398 322 508 777 669 52 124 286 855 732 88 188 504 499 437 274 949 635 593 101 22 927 901 626 612 555 938 779 299 636 10 462 608 57 54 279 836 289 479 126 773 971 859 439 493 513 294 978 967 197 20 599 768 646 738 831 747 561 305 664 617 819 579 329 288 988 235 342 766 684 832 566 302 981 471 420 952 782 942 606 222 846 821 221 730 512 874 79 776 888 189 529 987 488 806 868 700 760 310 601 123 538 469 427 728 58 772 697 500 46 903 257 397 375 231 567 936 873 585 485 502 681 556 290 292 340 56 552 155 614 463 676 183 634 989 55 630 172 521 335 861 955 947 259 137 539 419 421 194 735 881 620 602 920 857 909 363 173 461 443 898 609 411 610 919 407 631 530 266 580 563 18 489 753 584 61 186 432 860 103 140 853 824 699 994 31 871 911 794 410 896 472 232 791 17 320 157 87 511 935 258 4 577 900 318 377 592 769 62 624 595 248 316 164 518 65 813 865 370 633 344 239 161 382 119 736 817 347 838 812 750 741 76 622 262 540 230 454 9 308 27 170 643 827 387 442 823 149 677 212 351 402 490 32 717 270 147 616 446 333 600 138 82 770 673 800 378 195 670 714 476 156 662 191 464 53 742 452 843 572 582 35 91 255 219 596 722 473 752 912 204 893 783 815 729 102 293 658 653 198 565 253 690 86 744 116 598 637 275 168 223 209 81 891 718 328 814 478 972 524 965 705 146 337 625 199 396 383 847 910 591 693 3 185 767 401 818 33 523 505 324 409 534 29 525 166 349 37 510 809 694 418 203 979 939 1 993 206 959 570 268 715 78 528 652 879 246 825 632 26 263 468 135 514 413 830 326 399 597 651 559 460 458 844 237 261 319 134 932 256 233 301 820 628 400 180 228 94 153 449 70 13 751 784 252 210 385 25 364 918 641 317 202 642 660 894 84 796 448 264 961 704 487 841 678 867 726 40 691 483 883 605 484 957 445 558 272 125 629 775 958 885 515 875 384 285 404 109 755 554 906 187 96 357 175 659 826 991 708 687 890 66 128 1000 851 247 905 668 309 331 519 930 587 696 334 803 244 107 568 388 284 808 553 371 997 433 899 453 549 496 804 271 48 849 321 361 588 940 743 840 224 672 2 763 707 441 491 118 759 436 852 506 105 129 456 111 315 943 291 352 348 945 110 604 904 537 426 12 49 975 575 45 139 907 689 71 430 535 698 428 181 184 964 466 921 536 922 998 544 970 884 923 706 6 889 933 39 977 790 739 723 980 254 236 551 801 174 60 757 85 16 336 176 121 160 793 243 950 234 132 50 674 999 144 465 260 104 196 908 307 501 545 171 386 543 63 586 531 811 925 229 459 287 667 178 265 241 876 303 447 41 982 749 795 372 19 594 774 745 897 330 603 862 880 93 798 227 615 34 829 928 24 576 695 215 80 746 666 816 359 963 781 193 451 526 915 516 97 756 771 683 150 306 788 934 162 358 562 435 7 854 366 95 414 304 665 882 727 480 895 434 217 42 154 645 38 748 618 778 913 581 431 136 412 833 444 394 712 902 267 892 68 986 92 807 327 569 785 192 211 122 83 571 492 179 682 482 837 623 77 214 276 542 43 51 557 638 985 177 946 517 842 152 856 151 780 948 312 969 148 269 368 415 564 679 533 200 360 30 835 251 190 845 976 218 373 425 917 655 834 422 573 589 685 701 866 639 89 475 133 509 737 131 225 130 640 709 163 332 278 627 59 143 201 924 995 167 703 142 613 429 213 929 280 169 968 724 393 719 440 350 106 250 850 877 273 675 765 353 503 805 36 205 380 688 992 416 494 527 408 713 956 238 381 574 654 864 417 338 953 423 621 686 158 590 313 560 886 914 99 457 67 374 720 887 810 872 973 295 828 786 960 974 346 583 716 113 848 481 376 72 926 117 984 207 44 951 406 671 367 474 141 734 369 226 733 112 75 550 216 405 548 858 355 983 477 467 740 298 607 863 114 242 990 522 802 311 450 663 680 249 954 789 15 47 379 761 758 21 339 220 520 240 11 100 403 90 619 649 878 389 611 5 165 362 392 541 532 839 395 495 356 692 725 8 182 145 931 159 721 341 314 73 323 661 281 345 731 754 486 507 69 578 916 869 644 438 98 390 966 23
./a.out  17.80s user 0.05s system 99% cpu 17.922 total