Skip to content

b1f6c1c4/MineSweeperProb

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

MineSweeperProb

A deterministic Minesweeper solver

Click here for online demo & technical details.

The algorithm is described in the paper on AAAI Workshop 2017.

Build

sudo pacman -S cmake ninja boost  # For Arch Linux
cmake -S MineSweeperSolver -B cmake-bulid-release -DCMAKE_BUILD_TYPE=Release -DCMAKE_CXX_FLAGS='-march=native' -G Ninja
cmake --build cmake-build-release
# To run:
./cmake-build-release/MineSweeperSolver <config> <number>

Performance

  • SFAR / Safe first action rule: The first-clicked block is guaranteed no mine
  • SNR / Safe neighbourhood rule: The first-clicked block AND its surrounding blocks are guaranteed no mine
Board Size Rule Strategy Rate Cmd
8x8
10 mines
SFAR PSEQ 81.6351±0.0034%
./MineSweeperSolver FL@[1,1]-PSEQ-8-8-T10-SFAR 500000000
Approx. takes 98 minutes to run on an 8-core machine.
PSEQ-D256 81.7711±0.0076%
./MineSweeperSolver FL@[1,1]-PSEQ-D256-8-8-T10-SFAR 100000000
Approx. takes 250 hours to run on an 8-core machine.
SNR PSEQ 90.1456±0.0026%
./MineSweeperSolver FL@[3,3]-PSEQ-8-8-T10-SNR 500000000
Approx. takes 48 minutes to run on an 8-core machine.
PSEQ-D256 90.3448±0.0058%
./MineSweeperSolver FL@[3,3]-PSEQ-D256-8-8-T10-SNR 100000000
Approx. takes 231 hours to run on an 8-core machine.
9x9
10 mines
SFAR PSEQ 91.6775±0.0024%
./MineSweeperSolver FL@[1,1]-PSEQ-9-9-T10-SFAR 500000000
Approx. takes 74 minutes to run on an 8-core machine.
PSEQ-D256 91.6949±0.0054%
./MineSweeperSolver FL@[1,1]-PSEQ-D256-9-9-T10-SFAR 100000000
Approx. takes 24 hours to run on an 8-core machine.
SNR PSEQ 97.1453±0.0015%
./MineSweeperSolver FL@[3,3]-PSEQ-9-9-T10-SNR 500000000
Approx. takes 42 minutes to run on an 8-core machine.
PSEQ-D256 97.1669±0.0033%
./MineSweeperSolver FL@[3,3]-PSEQ-D256-9-9-T10-SNR 100000000
Approx. takes 19 hours to run on an 8-core machine.
16x16
40 mines
SFAR PSEQ 78.1228±0.0057%
./MineSweeperSolver FL@[1,1]-PSEQ-16-16-T40-SFAR 200000000
Approx. takes 109 minutes to run on an 8-core machine.
PSEQ-D256 78.2295±0.0081%
./MineSweeperSolver FL@[1,1]-PSEQ-D256-16-16-T40-SFAR 100000000
Approx. takes 116 hours to run on an 8-core machine.
SNR PSEQ 88.9267±0.0043%
./MineSweeperSolver FL@[3,3]-PSEQ-16-16-T40-SNR 200000000
Approx. takes 80 minutes to run on an 8-core machine.
PSEQ-D256 89.0757±0.0061%
./MineSweeperSolver FL@[3,3]-PSEQ-D256-16-16-T40-SNR 100000000
Approx. takes 122 hours to run on an 8-core machine.
30x16
99 mines
SFAR PSEQ 39.6158±0.0068%
./MineSweeperSolver FL@[1,1]-PSEQ-30-16-T99-SFAR 200000000
Approx. takes 15 hours to run on an 8-core machine.
PSEQ-D256 40.0468±0.0096%
./MineSweeperSolver FL@[1,1]-PSEQ-D256-30-16-T99-SFAR 100000000
Approx. takes 537 hours to run on an 8-core machine.
SNR PSEQ 52.7838±0.0069%
./MineSweeperSolver FL@[4,4]-PSEQ-30-16-T99-SNR 200000000
Approx. takes 15 hours to run on an 8-core machine.
PSEQ-D256 53.4502±0.0098%
./MineSweeperSolver FL@[4,4]-PSEQ-D256-30-16-T99-SNR 100000000
Approx. takes 812 hours to run on an 8-core machine.

Winning Rate by First Move

8x8, 10 mines

SFAR

1 2 3 4 5 6 7 8
1 81.6351
±0.0034%
78.6597
±0.0036%
78.8076
±0.0036%
78.7913
±0.0036%
78.7922
±0.0036%
78.8037
±0.0036%
78.6608
±0.0036%
81.6389
±0.0034%
2 78.6609
±0.0036%
78.6958
±0.0036%
78.1597
±0.0036%
78.1267
±0.0036%
78.1218
±0.0036%
78.1532
±0.0036%
78.6979
±0.0036%
78.6605
±0.0036%
3 78.8074
±0.0036%
78.1562
±0.0036%
74.4041
±0.0038%
74.0769
±0.0038%
74.0774
±0.0038%
74.4021
±0.0038%
78.1555
±0.0036%
78.8041
±0.0036%
4 78.7912
±0.0036%
78.1219
±0.0036%
74.0730
±0.0038%
73.7547
±0.0039%
73.7587
±0.0039%
74.0753
±0.0038%
78.1226
±0.0036%
78.7901
±0.0036%
5 78.7921
±0.0036%
78.1195
±0.0036%
74.0796
±0.0038%
73.7561
±0.0039%
73.7588
±0.0039%
74.0733
±0.0038%
78.1234
±0.0036%
78.7892
±0.0036%
6 78.8086
±0.0036%
78.1562
±0.0036%
74.4014
±0.0038%
74.0748
±0.0038%
74.0775
±0.0038%
74.4068
±0.0038%
78.1565
±0.0036%
78.8043
±0.0036%
7 78.6624
±0.0036%
78.6971
±0.0036%
78.1601
±0.0036%
78.1259
±0.0036%
78.1251
±0.0036%
78.1547
±0.0036%
78.7023
±0.0036%
78.6627
±0.0036%
8 81.6413
±0.0034%
78.6581
±0.0036%
78.8069
±0.0036%
78.7876
±0.0036%
78.7945
±0.0036%
78.8075
±0.0036%
78.6635
±0.0036%
81.6398
±0.0034%

SNR

1 2 3 4 5 6 7 8
1 88.2804
±0.0028%
89.2807
±0.0027%
89.9004
±0.0026%
89.8625
±0.0026%
89.8673
±0.0026%
89.9024
±0.0026%
89.2897
±0.0027%
88.2820
±0.0028%
2 89.2805
±0.0027%
89.0536
±0.0027%
89.8287
±0.0026%
89.7500
±0.0027%
89.7544
±0.0027%
89.8338
±0.0026%
89.0611
±0.0027%
89.2876
±0.0027%
3 89.9019
±0.0026%
89.8280
±0.0026%
90.1456
±0.0026%
90.0168
±0.0026%
90.0189
±0.0026%
90.1495
±0.0026%
89.8260
+0.0026-0.0027%
89.8990
±0.0026%
4 89.8633
±0.0026%
89.7546
±0.0027%
90.0137
±0.0026%
89.8105
±0.0027%
89.8144
±0.0027%
90.0183
±0.0026%
89.7526
±0.0027%
89.8633
±0.0026%
5 89.8685
±0.0026%
89.7539
±0.0027%
90.0168
±0.0026%
89.8129
±0.0027%
89.8128
±0.0027%
90.0186
±0.0026%
89.7548
±0.0027%
89.8666
±0.0026%
6 89.8998
±0.0026%
89.8306
±0.0026%
90.1488
±0.0026%
90.0168
±0.0026%
90.0225
±0.0026%
90.1479
±0.0026%
89.8333
±0.0026%
89.9019
±0.0026%
7 89.2890
±0.0027%
89.0614
±0.0027%
89.8283
±0.0026%
89.7537
±0.0027%
89.7540
±0.0027%
89.8313
±0.0026%
89.0660
±0.0027%
89.2942
±0.0027%
8 88.2833
±0.0028%
89.2826
±0.0027%
89.9014
±0.0026%
89.8620
±0.0026%
89.8675
±0.0026%
89.9022
±0.0026%
89.2917
±0.0027%
88.2877
±0.0028%

9x9, 10 mines

SFAR

1 2 3 4 5 6 7 8 9
1 91.6775
±0.0024%
89.4787
±0.0027%
89.5941
±0.0027%
89.5376
±0.0027%
89.4769
±0.0027%
89.5401
±0.0027%
89.5984
±0.0027%
89.4775
±0.0027%
91.6795
±0.0024%
2 89.4805
±0.0027%
88.1115
±0.0028%
87.8834
±0.0029%
87.7447
±0.0029%
87.6834
±0.0029%
87.7445
±0.0029%
87.8791
±0.0029%
88.1134
±0.0028%
89.4793
±0.0027%
3 89.5957
±0.0027%
87.8805
±0.0029%
86.6276
±0.0030%
86.6270
±0.0030%
86.5647
±0.0030%
86.6269
±0.0030%
86.6329
±0.0030%
87.8806
±0.0029%
89.5974
±0.0027%
4 89.5376
±0.0027%
87.7405
±0.0029%
86.6242
±0.0030%
86.5339
±0.0030%
86.4815
±0.0030%
86.5337
±0.0030%
86.6246
±0.0030%
87.7427
±0.0029%
89.5390
±0.0027%
5 89.4806
±0.0027%
87.6825
±0.0029%
86.5676
±0.0030%
86.4841
±0.0030%
86.4306
±0.0030%
86.4827
±0.0030%
86.5660
±0.0030%
87.6801
±0.0029%
89.4808
±0.0027%
6 89.5391
±0.0027%
87.7456
±0.0029%
86.6247
±0.0030%
86.5347
±0.0030%
86.4839
±0.0030%
86.5345
±0.0030%
86.6249
±0.0030%
87.7437
±0.0029%
89.5372
±0.0027%
7 89.5963
±0.0027%
87.8817
±0.0029%
86.6319
±0.0030%
86.6247
±0.0030%
86.5680
±0.0030%
86.6233
±0.0030%
86.6311
±0.0030%
87.8819
±0.0029%
89.5967
±0.0027%
8 89.4808
±0.0027%
88.1106
±0.0028%
87.8792
±0.0029%
87.7423
±0.0029%
87.6810
±0.0029%
87.7468
±0.0029%
87.8839
±0.0029%
88.1159
±0.0028%
89.4819
±0.0027%
9 91.6762
±0.0024%
89.4810
±0.0027%
89.5954
±0.0027%
89.5373
±0.0027%
89.4776
±0.0027%
89.5373
±0.0027%
89.5990
±0.0027%
89.4812
±0.0027%
91.6791
±0.0024%

SNR

1 2 3 4 5 6 7 8 9
1 96.2181
±0.0017%
96.7581
±0.0016%
97.0212
±0.0015%
96.9511
±0.0015%
96.7144
±0.0016%
96.9519
±0.0015%
97.0244
±0.0015%
96.7594
±0.0016%
96.2182
±0.0017%
2 96.7571
±0.0016%
96.7878
±0.0015%
97.0644
±0.0015%
96.9618
±0.0015%
96.5502
±0.0016%
96.9620
±0.0015%
97.0671
±0.0015%
96.7884
±0.0015%
96.7584
±0.0016%
3 97.0227
±0.0015%
97.0653
±0.0015%
97.1453
±0.0015%
97.0104
±0.0015%
96.5788
±0.0016%
97.0105
±0.0015%
97.1489
±0.0015%
97.0629
±0.0015%
97.0229
±0.0015%
4 96.9532
±0.0015%
96.9619
±0.0015%
97.0102
±0.0015%
96.8457
±0.0015%
96.5254
±0.0016%
96.8482
±0.0015%
97.0132
±0.0015%
96.9636
±0.0015%
96.9515
±0.0015%
5 96.7147
±0.0016%
96.5497
±0.0016%
96.5776
±0.0016%
96.5243
±0.0016%
96.2491
±0.0017%
96.5251
±0.0016%
96.5810
±0.0016%
96.5517
±0.0016%
96.7145
±0.0016%
6 96.9520
±0.0015%
96.9624
±0.0015%
97.0101
±0.0015%
96.8472
±0.0015%
96.5238
±0.0016%
96.8485
±0.0015%
97.0132
±0.0015%
96.9631
±0.0015%
96.9532
±0.0015%
7 97.0240
±0.0015%
97.0671
±0.0015%
97.1472
±0.0015%
97.0124
±0.0015%
96.5803
±0.0016%
97.0117
±0.0015%
97.1507
±0.0015%
97.0684
±0.0015%
97.0258
±0.0015%
8 96.7571
±0.0016%
96.7888
±0.0015%
97.0640
±0.0015%
96.9609
±0.0015%
96.5509
±0.0016%
96.9620
±0.0015%
97.0677
±0.0015%
96.7920
±0.0015%
96.7614
±0.0016%
9 96.2175
±0.0017%
96.7586
±0.0016%
97.0223
±0.0015%
96.9513
±0.0015%
96.7165
±0.0016%
96.9513
±0.0015%
97.0260
±0.0015%
96.7614
±0.0016%
96.2222
±0.0017%

16x16, 40 mines

SFAR

1 2 3 4 5 6 7 8
1 78.1228
±0.0057%
75.3061
±0.0060%
75.6851
±0.0059%
75.5737
±0.0060%
75.4819
±0.0060%
75.4991
±0.0060%
75.4816
±0.0060%
75.4806
±0.0060%
2 75.3103
±0.0060%
75.1871
±0.0060%
75.0593
±0.0060%
74.8811
±0.0060%
74.8240
±0.0060%
74.9170
±0.0060%
74.9153
±0.0060%
74.9287
±0.0060%
3 75.6815
±0.0059%
75.0549
±0.0060%
72.1353
±0.0062%
71.5990
+0.0062-0.0063%
71.5643
±0.0063%
71.5860
±0.0063%
71.6182
±0.0062%
71.6227
±0.0062%
4 75.5759
±0.0060%
74.8762
±0.0060%
71.6000
+0.0062-0.0063%
70.9050
±0.0063%
70.8347
±0.0063%
70.8575
±0.0063%
70.8579
±0.0063%
70.8599
±0.0063%
5 75.4769
±0.0060%
74.8194
±0.0060%
71.5641
±0.0063%
70.8302
±0.0063%
70.7772
±0.0063%
70.7967
±0.0063%
70.7991
±0.0063%
70.8029
±0.0063%
6 75.4979
±0.0060%
74.9062
±0.0060%
71.5819
±0.0063%
70.8431
±0.0063%
70.7928
±0.0063%
70.7872
±0.0063%
70.7888
±0.0063%
70.7937
±0.0063%
7 75.4842
±0.0060%
74.9167
±0.0060%
71.6123
±0.0062%
70.8511
±0.0063%
70.7922
±0.0063%
70.7896
±0.0063%
70.7867
±0.0063%
70.7824
±0.0063%
8 75.4784
±0.0060%
74.9205
±0.0060%
71.6201
±0.0062%
70.8644
±0.0063%
70.7947
±0.0063%
70.7870
±0.0063%
70.7808
±0.0063%
70.7810
±0.0063%

SNR

1 2 3 4 5 6 7 8
1 85.4942
±0.0049%
87.0977
±0.0046%
87.7933
±0.0045%
87.8463
±0.0045%
87.4697
±0.0046%
87.5105
±0.0046%
87.5398
±0.0046%
87.4916
±0.0046%
2 87.0982
±0.0046%
87.8506
±0.0045%
88.5926
±0.0044%
88.5942
±0.0044%
87.9034
±0.0045%
87.9166
±0.0045%
87.9338
±0.0045%
87.8641
±0.0045%
3 87.7811
±0.0045%
88.5908
±0.0044%
88.9267
±0.0043%
88.8635
±0.0044%
88.1142
±0.0045%
88.1082
±0.0045%
88.1172
±0.0045%
88.0401
±0.0045%
4 87.8495
±0.0045%
88.5989
±0.0044%
88.8583
±0.0044%
88.7111
±0.0044%
88.0816
±0.0045%
88.0521
±0.0045%
88.0442
±0.0045%
87.9901
±0.0045%
5 87.4703
±0.0046%
87.9047
±0.0045%
88.1090
±0.0045%
88.0770
±0.0045%
87.5345
±0.0046%
87.5350
±0.0046%
87.5304
±0.0046%
87.4774
±0.0046%
6 87.5119
±0.0046%
87.9162
±0.0045%
88.0952
±0.0045%
88.0451
±0.0045%
87.5308
±0.0046%
87.5167
±0.0046%
87.5179
±0.0046%
87.4774
±0.0046%
7 87.5402
±0.0046%
87.9331
±0.0045%
88.1091
±0.0045%
88.0402
±0.0045%
87.5319
±0.0046%
87.5226
±0.0046%
87.5215
±0.0046%
87.4768
±0.0046%
8 87.4926
±0.0046%
87.8598
±0.0045%
88.0294
±0.0045%
87.9902
±0.0045%
87.4839
±0.0046%
87.4753
±0.0046%
87.4732
±0.0046%
87.4350
±0.0046%

30x16, 99 mines

SFAR

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 39.6158
±0.0068%
38.7505
±0.0095%
37.5650
±0.0095%
37.2672
±0.0095%
37.2545
±0.0095%
37.3288
±0.0095%
37.3516
±0.0095%
37.3704
±0.0095%
37.3988
±0.0095%
37.4118
±0.0095%
37.4255
±0.0095%
37.4378
±0.0095%
37.4400
±0.0095%
37.4399
±0.0095%
37.4386
±0.0095%
2 38.7453
±0.0095%
38.0543
±0.0095%
38.1629
±0.0095%
38.0384
±0.0095%
37.9725
±0.0095%
38.0739
±0.0095%
38.0853
±0.0095%
38.0979
±0.0095%
38.1258
±0.0095%
38.1355
±0.0095%
38.1410
±0.0095%
38.1529
±0.0095%
38.1552
±0.0095%
38.1576
±0.0095%
38.1615
±0.0095%
3 37.5578
±0.0095%
38.1637
±0.0095%
36.3193
±0.0094%
36.1271
±0.0094%
36.0816
±0.0094%
36.1255
±0.0094%
36.1716
±0.0094%
36.1935
±0.0094%
36.2079
±0.0094%
36.2287
±0.0094%
36.2356
±0.0094%
36.2419
±0.0094%
36.2623
±0.0094%
36.2535
±0.0094%
36.2535
±0.0094%
4 37.2754
±0.0095%
38.0326
±0.0095%
36.1159
±0.0094%
35.8690
±0.0094%
35.8111
±0.0094%
35.8670
±0.0094%
35.8720
±0.0094%
35.8873
±0.0094%
35.9028
±0.0094%
35.9219
±0.0094%
35.9313
±0.0094%
35.9314
±0.0094%
35.9458
±0.0094%
35.9477
±0.0094%
35.9441
±0.0094%
5 37.2529
±0.0095%
37.9653
±0.0095%
36.0816
±0.0094%
35.8092
±0.0094%
35.7653
±0.0094%
35.8221
±0.0094%
35.8212
±0.0094%
35.8454
±0.0094%
35.8758
±0.0094%
35.8865
±0.0094%
35.8775
±0.0094%
35.9065
±0.0094%
35.9032
±0.0094%
35.9063
±0.0094%
35.9042
±0.0094%
6 37.3162
±0.0095%
38.0552
±0.0095%
36.1073
±0.0094%
35.8418
±0.0094%
35.8023
±0.0094%
35.8428
±0.0094%
35.8363
±0.0094%
35.8614
±0.0094%
35.8693
±0.0094%
35.8892
±0.0094%
35.8886
±0.0094%
35.9039
±0.0094%
35.9104
±0.0094%
35.9090
±0.0094%
35.9097
±0.0094%
7 37.3312
±0.0095%
38.0618
±0.0095%
36.1449
±0.0094%
35.8455
±0.0094%
35.8178
±0.0094%
35.8266
±0.0094%
35.8368
±0.0094%
35.8495
±0.0094%
35.8663
±0.0094%
35.8748
±0.0094%
35.8865
±0.0094%
35.8766
±0.0094%
35.9019
±0.0094%
35.8906
±0.0094%
35.9010
±0.0094%
8 37.3394
±0.0095%
38.0617
±0.0095%
36.1446
±0.0094%
35.8573
±0.0094%
35.8297
±0.0094%
35.8445
±0.0094%
35.8348
±0.0094%
35.8546
±0.0094%
35.8680
±0.0094%
35.8752
±0.0094%
35.8812
±0.0094%
35.8961
±0.0094%
35.9063
±0.0094%
35.9014
±0.0094%
35.8971
±0.0094%

SNR

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
1 46.7470
±0.0098%
48.9491
±0.0098%
50.0923
±0.0098%
50.3836
±0.0098%
50.0144
±0.0098%
50.1361
±0.0098%
50.2167
±0.0098%
50.1836
±0.0098%
50.2298
±0.0098%
50.2542
±0.0098%
50.2571
±0.0098%
50.2624
±0.0098%
50.2713
±0.0098%
50.2763
±0.0098%
50.2801
±0.0098%
2 48.9188
±0.0098%
50.1038
±0.0098%
51.4913
±0.0098%
51.8195
±0.0098%
51.0733
±0.0098%
51.2316
±0.0098%
51.2887
±0.0098%
51.2470
±0.0098%
51.2553
±0.0098%
51.2681
±0.0098%
51.2644
±0.0098%
51.2779
±0.0098%
51.2807
±0.0098%
51.2843
±0.0098%
51.2825
±0.0098%
3 50.0949
±0.0098%
51.4983
±0.0098%
52.4287
±0.0098%
52.6958
±0.0098%
51.8480
±0.0098%
51.9813
±0.0098%
52.0251
±0.0098%
51.9536
±0.0098%
51.9557
±0.0098%
51.9754
±0.0098%
51.9545
±0.0098%
51.9672
±0.0098%
51.9689
±0.0098%
51.9735
±0.0098%
51.9696
±0.0098%
4 50.3687
±0.0098%
51.7994
±0.0098%
52.6707
±0.0098%
52.7838
±0.0069%
52.0216
±0.0098%
52.1141
±0.0098%
52.1527
±0.0098%
52.0896
±0.0098%
52.0913
±0.0098%
52.0996
±0.0098%
52.0877
±0.0098%
52.0867
±0.0098%
52.0862
±0.0098%
52.1024
±0.0098%
52.0926
±0.0098%
5 49.9929
±0.0098%
51.0695
±0.0098%
51.8357
±0.0098%
52.0133
±0.0098%
51.2472
±0.0098%
51.3606
±0.0098%
51.4007
±0.0098%
51.3256
±0.0098%
51.3406
±0.0098%
51.3497
±0.0098%
51.3431
±0.0098%
51.3401
±0.0098%
51.3464
±0.0098%
51.3548
±0.0098%
51.3509
±0.0098%
6 50.1103
±0.0098%
51.1860
±0.0098%
51.9445
±0.0098%
52.0990
±0.0098%
51.3517
±0.0098%
51.4280
±0.0098%
51.4679
±0.0098%
51.4124
±0.0098%
51.4098
±0.0098%
51.4203
±0.0098%
51.4035
±0.0098%
51.4114
±0.0069%
51.4246
±0.0098%
51.4243
±0.0098%
51.4109
±0.0098%
7 50.1871
±0.0057%
51.2811
±0.0057%
52.0332
±0.0057%
52.1450
±0.0057%
51.3995
±0.0057%
51.4722
±0.0069%
51.5044
±0.0069%
51.4442
±0.0098%
51.4516
±0.0098%
51.4568
±0.0069%
51.4482
±0.0098%
51.4519
±0.0069%
51.4563
±0.0098%
51.4519
±0.0098%
51.4555
±0.0098%
8 50.1325
±0.0098%
51.1912
±0.0098%
51.9285
±0.0098%
52.0685
±0.0098%
51.3169
±0.0098%
51.3864
±0.0098%
51.4315
±0.0098%
51.3558
±0.0098%
51.3773
±0.0098%
51.3716
±0.0069%
51.3704
±0.0098%
51.3733
±0.0069%
51.3737
±0.0098%
51.3844
±0.0069%
51.3815
±0.0098%