Coverage for moptipy/examples/bitstrings/nqueens.py: 22%

1"""

2The N-Queens problem.

4The N-Queens problem is defined for bit strings of length n = N ** 2.

5A bit string `x` is mapped to a chess board and a queen is placed for any bit

6of value 1. The goal is to place N queens such that they cannot attack each

7other. The total number of queens on the board be Q(x) is the number of `True`

8bits, which might be more or less than N.

9We also count the number ez(x) of queens in every single row, column, and

10diagonal z of the chess board. The minimization version of the N-Queens

11problem is then `N - Q(x) + N sum_(all z) max(0, ez(x) - 1)`.

12The N-Queens problems are attested moderate difficulty in [1].

14Here, `N` is stored in the `k`-value of the benchmark function instances.

16The best possible objective value of this function is achieved if exactly

17`k=N` queens are positioned such that none can beat any other queen. The

18objective function then returns 0.

20The worst case is if a queen is placed on every single field, i.e., if we have

21`n = k*k` queens on the field. Then, the objective value will be

22`(((((k - 2) * 4) + 1) * k) + 3) * k`.

241. Carola Doerr, Furong Ye, Naama Horesh, Hao Wang, Ofer M. Shir, and Thomas

25 Bäck. Benchmarking Discrete Optimization Heuristics with IOHprofiler.

26 Applied Soft Computing Journal. 88:106027. 2020.

27 doi: https://doi.org/10.1016/j.asoc.2019.106027

282. Thomas Weise, Zhize Wu, Xinlu Li, Yan Chen, and Jörg Lässig. Frequency

29 Fitness Assignment: Optimization without Bias for Good Solutions can be

30 Efficient. *IEEE Transactions on Evolutionary Computation (TEVC)*.

31 27(4):980-992. August 2023.

32 doi: https://doi.org/10.1109/TEVC.2022.3191698

34This is code is part of the research work of Mr. Jiazheng ZENG (曾嘉政),

35a Master's student at the Institute of Applied Optimization

36(应用优化研究所) of the School of Artificial

37Intelligence and Big Data (人工智能与大数据学院) at

38Hefei University (合肥大学) in

39Hefei, Anhui, China (中国安徽省合肥市) under the supervision of

40Prof. Dr. Thomas Weise (汤卫思教授).

41"""

42from typing import Callable, Final, Iterator, cast

44import numba # type: ignore

45import numpy as np

46from pycommons.types import check_int_range

48from moptipy.examples.bitstrings.bitstring_problem import (

49 SquareBitStringProblem,

50)

53@numba.njit(nogil=True, cache=True)

54def nqueens(x: np.ndarray, k: int) -> int:

55 """

56 Evaluate the N-Queens objective function.

58 :param x: the np array representing the board (bit string)

59 :param k: the total number of queens (dimension of the problem)

60 :return: the penalty score

62 >>> nqueens(np.array([False, True, False, False,

63 ... False, False, False, True,

64 ... True, False, False, False,

65 ... False, False, True, False]), 4)

66 0

68 >>> nqueens(np.array([False, False, True, False,

69 ... True, False, False, False,

70 ... False, False, False, True,

71 ... False, True, False, False]), 4)

72 0

74 >>> nqueens(np.array([False, False, False, False,

75 ... False, False, False, False,

76 ... False, False, False, False,

77 ... False, False, False, False]), 4)

78 4

80 >>> nqueens(np.array([ True, False, False, False,

81 ... False, False, False, False,

82 ... False, False, False, False,

83 ... False, False, False, False]), 4)

84 3

86 # two queens, but in the same row, which gives 2 + 4

87 >>> nqueens(np.array([ True, True, False, False,

88 ... False, False, False, False,

89 ... False, False, False, False,

90 ... False, False, False, False]), 4)

91 6

93 # three queens, but 2 in the same row, 2 in the same column, and 2 in one

94 # diagonal, which gives 1 + 4 + 4 + 4

95 >>> nqueens(np.array([ True, True, False, False,

96 ... True, False, False, False,

97 ... False, False, False, False,

98 ... False, False, False, False]), 4)

99 13

100

101 # four queens, but 3 in the same row, 2 in the same column, and 2 in one

102 # diagonal, which gives 0 + 8 + 4 + 4

103 >>> nqueens(np.array([ True, True, True, False,

104 ... True, False, False, False,

105 ... False, False, False, False,

106 ... False, False, False, False]), 4)

107 16

108

109 # five queens, but 4 in the same row, 2 in the same column, and 2 in one

110 # diagonal, which gives -1 + 12 + 4 + 4

111 >>> nqueens(np.array([ True, True, True, True,

112 ... True, False, False, False,

113 ... False, False, False, False,

114 ... False, False, False, False]), 4)

115 19

116

117 >>> nqueens(np.array([

118 ... False, False, False, True, False, False, False, False,

119 ... False, False, False, False, False, True, False, False,

120 ... False, False, False, False, False, False, False, True,

121 ... False, True, False, False, False, False, False, False,

122 ... False, False, False, False, False, False, True, False,

123 ... True, False, False, False, False, False, False, False,

124 ... False, False, True, False, False, False, False, False,

125 ... False, False, False, False, True, False, False, False,]), 8)

126 0

127

128 # five queens, but 4 in the same row, 2 in the same column, and 2 in one

129 # diagonal, which gives -1 + 12 + 4 + 4

130 >>> nqueens(np.array([1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4)

131 19

132

133 # 16 bits, board width = 4, and 2 queens

134 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 4)

135 6

136

137 # 16 bits, board width = 4, and 2 queens

138 >>> nqueens(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]), 4)

139 2

140

141 # 16 bits, board width = 4, and 2 queens

142 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0]), 4)

143 2

144

145 # 16 bits, board width = 4, and 3 queens

146 >>> nqueens(np.array([0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]), 4)

147 5

148

149 # 16 bits, board width = 4, and 4 queens

150 >>> nqueens(np.array([0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 4)

151 12

152

153 # 16 bits, board width = 4, and 4 queens

154 >>> nqueens(np.array([0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 4)

155 12

156

157 # 16 bits, board width = 4, and 4 queens

158 >>> nqueens(np.array([0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0]), 4)

159 12

160

161 # 16 bits, board width = 4, and 4 queens

162 >>> nqueens(np.array([0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0]), 4)

163 20

164

165 # 16 bits, board width = 4, and 11 queens

166 >>> nqueens(np.array([1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]), 4)

167 85

168

169 # 16 bits, board width = 4, and 8 queens

170 >>> nqueens(np.array([0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0]), 4)

171 52

172

173 # 16 bits, board width = 4, and 9 queens

174 >>> nqueens(np.array([1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0]), 4)

175 67

176

177 # 16 bits, board width = 4, and 10 queens

178 >>> nqueens(np.array([0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1]), 4)

179 78

180

181 # 16 bits, board width = 4, and 0 queens

182 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 4)

183 4

184

185 # 16 bits, board width = 4, and 16 queens

186 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 4)

187 156

188

189 # 25 bits, board width = 5, and 3 queens

190 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0,

191 ... 0, 0, 1, 0, 0, 0, 0, 0]), 5)

192 17

193

194 # 25 bits, board width = 5, and 1 queen

195 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

196 ... 0, 0, 0, 0, 0, 0, 0, 0]), 5)

197 4

198

199 # 25 bits, board width = 5, and 4 queens

200 >>> nqueens(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,

201 ... 0, 0, 0, 0, 1, 1, 0, 0]), 5)

202 16

203

204 # 25 bits, board width = 5, and 1 queen

205 >>> nqueens(np.array([0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

206 ... 0, 0, 0, 0, 0, 0, 0, 0]), 5)

207 4

208

209 # 25 bits, board width = 5, and 5 queens

210 >>> nqueens(np.array([1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

211 ... 0, 0, 0, 1, 0, 0, 1, 0]), 5)

212 25

213

214 # 25 bits, board width = 5, and 5 queens

215 >>> nqueens(np.array([0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0,

216 ... 0, 0, 0, 0, 0, 0, 0, 0]), 5)

217 30

218

219 # 25 bits, board width = 5, and 5 queens

220 >>> nqueens(np.array([0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,

221 ... 0, 0, 0, 0, 0, 0, 0, 1]), 5)

222 15

223

224 # 25 bits, board width = 5, and 5 queens

225 >>> nqueens(np.array([0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1,

226 ... 0, 1, 0, 0, 0, 0, 0, 0]), 5)

227 20

228

229 # 25 bits, board width = 5, and 15 queens

230 >>> nqueens(np.array([1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1,

231 ... 1, 1, 0, 1, 1, 0, 1, 1]), 5)

232 160

233

234 # 25 bits, board width = 5, and 22 queens

235 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0,

236 ... 1, 1, 1, 1, 1, 1, 1, 1]), 5)

237 283

238

239 # 25 bits, board width = 5, and 18 queens

240 >>> nqueens(np.array([1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1,

241 ... 1, 1, 1, 1, 1, 1, 0, 1]), 5)

242 217

243

244 # 25 bits, board width = 5, and 21 queens

245 >>> nqueens(np.array([0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1,

246 ... 1, 1, 1, 1, 1, 1, 1, 1]), 5)

247 274

248

249 # 25 bits, board width = 5, and 0 queens

250 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

251 ... 0, 0, 0, 0, 0, 0, 0, 0]), 5)

252 5

253

254 # 25 bits, board width = 5, and 25 queens

255 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

256 ... 1, 1, 1, 1, 1, 1, 1, 1]), 5)

257 340

258

259 # 36 bits, board width = 6, and 2 queens

260 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

261 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 6)

262 4

263

264 # 36 bits, board width = 6, and 2 queens

265 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

266 ... 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 6)

267 4

268

269 # 36 bits, board width = 6, and 4 queens

270 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1,

271 ... 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 6)

272 14

273

274 # 36 bits, board width = 6, and 3 queens

275 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

276 ... 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 6)

277 3

278

279 # 36 bits, board width = 6, and 6 queens

280 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,

281 ... 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]), 6)

282 42

283

284 # 36 bits, board width = 6, and 6 queens

285 >>> nqueens(np.array([1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0,

286 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]), 6)

287 42

288

289 # 36 bits, board width = 6, and 6 queens

290 >>> nqueens(np.array([1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

291 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0]), 6)

292 36

293

294 # 36 bits, board width = 6, and 6 queens

295 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,

296 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1]), 6)

297 42

298

299 # 36 bits, board width = 6, and 17 queens

300 >>> nqueens(np.array([0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0,

301 ... 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1]), 6)

302 223

303

304 # 36 bits, board width = 6, and 13 queens

305 >>> nqueens(np.array([1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

306 ... 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0]), 6)

307 137

308

309 # 36 bits, board width = 6, and 20 queens

310 >>> nqueens(np.array([0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1,

311 ... 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1]), 6)

312 274

313

314 # 36 bits, board width = 6, and 11 queens

315 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1,

316 ... 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0]), 6)

317 103

318

319 # 36 bits, board width = 6, and 0 queens

320 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

321 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 6)

322 6

323

324 # 36 bits, board width = 6, and 36 queens

325 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

326 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 6)

327 630

328

329 # 49 bits, board width = 7, and 1 queen

330 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

331 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

332 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

333 6

334

335 # 49 bits, board width = 7, and 2 queens

336 >>> nqueens(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

337 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

338 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

339 5

340

341 # 49 bits, board width = 7, and 3 queens

342 >>> nqueens(np.array([0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

343 ... 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

344 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

345 4

346

347 # 49 bits, board width = 7, and 4 queens

348 >>> nqueens(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

349 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,

350 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

351 17

352

353 # 49 bits, board width = 7, and 7 queens

354 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1,

355 ... 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,

356 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

357 70

358

359 # 49 bits, board width = 7, and 7 queens

360 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

361 ... 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,

362 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 7)

363 35

364

365 # 49 bits, board width = 7, and 7 queens

366 >>> nqueens(np.array([0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,

367 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

368 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 0]), 7)

369 42

370

371 # 49 bits, board width = 7, and 7 queens

372 >>> nqueens(np.array([0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0,

373 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

374 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

375 63

376

377 # 49 bits, board width = 7, and 25 queens

378 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0,

379 ... 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0,

380 ... 1, 0, 0, 0, 0, 1, 0, 0, 0, 0]), 7)

381 437

382

383 # 49 bits, board width = 7, and 33 queens

384 >>> nqueens(np.array([1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0,

385 ... 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1,

386 ... 1, 1, 1, 1, 0, 1, 0, 1, 1, 0]), 7)

387 625

388

389 # 49 bits, board width = 7, and 24 queens

390 >>> nqueens(np.array([1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1,

391 ... 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0,

392 ... 0, 0, 1, 0, 0, 1, 1, 0, 0, 0]), 7)

393 403

394

395 # 49 bits, board width = 7, and 15 queens

396 >>> nqueens(np.array([0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1,

397 ... 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

398 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 1]), 7)

399 209

400

401 # 49 bits, board width = 7, and 0 queens

402 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

403 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

404 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 7)

405 7

406

407 # 49 bits, board width = 7, and 49 queens

408 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

409 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

410 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 7)

411 1050

412

413 # 64 bits, board width = 8, and 1 queen

414 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,

415 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

416 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

417 ... 0, 0, 0]), 8)

418 7

419

420 # 64 bits, board width = 8, and 1 queen

421 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

422 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,

423 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

424 ... 0, 0, 0]), 8)

425 7

426

427 # 64 bits, board width = 8, and 3 queens

428 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

429 ... 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

430 ... 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

431 ... 0, 0, 0]), 8)

432 21

433

434 # 64 bits, board width = 8, and 6 queens

435 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

436 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,

437 ... 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

438 ... 0, 0, 0]), 8)

439 42

440

441 # 64 bits, board width = 8, and 8 queens

442 >>> nqueens(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,

443 ... 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

444 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,

445 ... 0, 1, 0]), 8)

446 64

447

448 # 64 bits, board width = 8, and 8 queens

449 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1,

450 ... 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,

451 ... 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,

452 ... 0, 0, 0]), 8)

453 72

454

455 # 64 bits, board width = 8, and 8 queens

456 >>> nqueens(np.array([0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

457 ... 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

458 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,

459 ... 0, 1, 0]), 8)

460 56

461

462 # 64 bits, board width = 8, and 8 queens

463 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

464 ... 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

465 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

466 ... 0, 0, 0]), 8)

467 64

468

469 # 64 bits, board width = 8, and 20 queens

470 >>> nqueens(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

471 ... 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,

472 ... 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1,

473 ... 0, 0, 0]), 8)

474 348

475

476 # 64 bits, board width = 8, and 46 queens

477 >>> nqueens(np.array([0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0,

478 ... 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1,

479 ... 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1,

480 ... 1, 0, 1]), 8)

481 1074

482

483 # 64 bits, board width = 8, and 29 queens

484 >>> nqueens(np.array([1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,

485 ... 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0,

486 ... 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0,

487 ... 0, 0, 1]), 8)

488 579

489

490 # 64 bits, board width = 8, and 20 queens

491 >>> nqueens(np.array([1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1,

492 ... 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

493 ... 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1,

494 ... 0, 0, 0]), 8)

495 300

496

497 # 64 bits, board width = 8, and 0 queens

498 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

499 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

500 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

501 ... 0, 0, 0]), 8)

502 8

503

504 # 64 bits, board width = 8, and 64 queens

505 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

506 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

507 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

508 ... 1, 1, 1]), 8)

509 1624

510

511 # 81 bits, board width = 9, and 1 queen

512 >>> nqueens(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

513 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

514 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

515 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 9)

516 8

517

518 # 81 bits, board width = 9, and 7 queens

519 >>> nqueens(np.array([0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

520 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1,

521 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

522 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0]), 9)

523 56

524

525 # 81 bits, board width = 9, and 8 queens

526 >>> nqueens(np.array([0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1,

527 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

528 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0,

529 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 9)

530 73

531

532 # 81 bits, board width = 9, and 3 queens

533 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,

534 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

535 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

536 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0]), 9)

537 15

538

539 # 81 bits, board width = 9, and 9 queens

540 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0,

541 ... 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,

542 ... 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,

543 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 9)

544 81

545

546 # 81 bits, board width = 9, and 9 queens

547 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

548 ... 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,

549 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

550 ... 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 9)

551 63

552

553 # 81 bits, board width = 9, and 9 queens

554 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1,

555 ... 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

556 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0,

557 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0]), 9)

558 90

559

560 # 81 bits, board width = 9, and 9 queens

561 >>> nqueens(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

562 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1,

563 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

564 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 9)

565 72

566

567 # 81 bits, board width = 9, and 22 queens

568 >>> nqueens(np.array([0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0,

569 ... 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1,

570 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1,

571 ... 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1]), 9)

572 428

573

574 # 81 bits, board width = 9, and 43 queens

575 >>> nqueens(np.array([0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0,

576 ... 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0,

577 ... 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1,

578 ... 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0]), 9)

579 1091

580

581 # 81 bits, board width = 9, and 18 queens

582 >>> nqueens(np.array([0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0,

583 ... 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0,

584 ... 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0,

585 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0]), 9)

586 288

587

588 # 81 bits, board width = 9, and 24 queens

589 >>> nqueens(np.array([0, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0,

590 ... 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0,

591 ... 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0,

592 ... 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1]), 9)

593 444

594

595 # 81 bits, board width = 9, and 0 queens

596 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

597 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

598 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

599 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 9)

600 9

601

602 # 81 bits, board width = 9, and 81 queens

603 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

604 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

605 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

606 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 9)

607 2376

608

609 # 100 bits, board width = 10, and 6 queens

610 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

611 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

612 ... 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,

613 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

614 ... 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

615 34

616

617 # 100 bits, board width = 10, and 7 queens

618 >>> nqueens(np.array([0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

619 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

620 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,

621 ... 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

622 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0]), 10)

623 43

624

625 # 100 bits, board width = 10, and 8 queens

626 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0,

627 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0,

628 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,

629 ... 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,

630 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

631 72

632

633 # 100 bits, board width = 10, and 6 queens

634 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

635 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0,

636 ... 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0,

637 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

638 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0]), 10)

639 34

640

641 # 100 bits, board width = 10, and 10 queens

642 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

643 ... 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

644 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0,

645 ... 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,

646 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

647 140

648

649 # 100 bits, board width = 10, and 10 queens

650 >>> nqueens(np.array([0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,

651 ... 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0,

652 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

653 ... 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,

654 ... 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

655 80

656

657 # 100 bits, board width = 10, and 10 queens

658 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0,

659 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

660 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

661 ... 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0,

662 ... 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0]), 10)

663 130

664

665 # 100 bits, board width = 10, and 10 queens

666 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0,

667 ... 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,

668 ... 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0,

669 ... 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

670 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

671 100

672

673 # 100 bits, board width = 10, and 50 queens

674 >>> nqueens(np.array([0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0,

675 ... 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 0,

676 ... 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1,

677 ... 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0,

678 ... 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0]), 10)

679 1430

680

681 # 100 bits, board width = 10, and 42 queens

682 >>> nqueens(np.array([0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0,

683 ... 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1,

684 ... 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0,

685 ... 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0,

686 ... 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0]), 10)

687 1138

688

689 # 100 bits, board width = 10, and 93 queens

690 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

691 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1,

692 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0,

693 ... 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,

694 ... 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 10)

695 3067

696

697 # 100 bits, board width = 10, and 92 queens

698 >>> nqueens(np.array([1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

699 ... 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

700 ... 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

701 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1,

702 ... 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1]), 10)

703 3018

704

705 # 100 bits, board width = 10, and 0 queens

706 >>> nqueens(np.array([0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

707 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

708 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

709 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,

710 ... 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]), 10)

711 10

712

713 # 100 bits, board width = 10, and 100 queens

714 >>> nqueens(np.array([1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

715 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

716 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

717 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,

718 ... 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]), 10)

719 3330

720

721 >>> nqueens(np.array([True] * 16), 4)

722 156

723 """

724 n: Final[int] = len(x)

725

726 # The chess board is stored row-by-row.

727 # Count the total number of queens on the chess board. It should be k.

728 queens_total: int = 0

729

730 # Since we need to go through the board row by row anyway, we

731 # can also check how many queens are in each row while we are at

732 # it.

733 must_be_one_1: int = 0 # queens per row

734 penalty: int = 0

735

736 # The last row goes from index n-1 to index n-k, the row before

737 # from n-k-1 to n-2k, ..., the first row goes from k-1 to 0.

738 next_row_reset = k - 1

739 for i in range(n):

740 if x[i]:

741 queens_total += 1

742 must_be_one_1 += 1

743

744 if i >= next_row_reset: # We reached the end of a row.

745 next_row_reset += k

746

747 # If there is at most one queen in the row, the penalty is zero.

748 # Otherwise, the penalty for the row is number of queens in it

749 # minus 1.

750 if must_be_one_1 > 1:

751 penalty += must_be_one_1 - 1

752 must_be_one_1 = 0

753

754 # Count the number of queens in the columns and check if there

755 # is more than one queen in a column.

756 # col be the column index, it goes from 1 to k.

757 for col in range(k):

758 must_be_one_1 = 0

759 # The cells in column j have indices k-j, 2k-j, 3k-j, ...,

760 # k*k-j=n-j in x and we iterate them from the back.

761 for i in range(col, n, k):

762 if x[i]:

763 must_be_one_1 += 1

764 # If there is at most one queen in the column, the penalty is zero.

765 # Otherwise, the penalty for the column is number of queens in

766 # it minus 1.

767 if must_be_one_1 > 1:

768 penalty += must_be_one_1 - 1

769

770 # There are 1 + 2*(k-2) = 2*k-3 diagonals of any kind.

771 # The diagonal in the "middle" is unique, the others can be

772 # mirrored.

773

774 # We have two types of diagonals.

775 # One goes from top-left to bottom-right, for which we use index

776 # i1 and count collisions in must_be_one_1 and must_be_one_2 and whose

777 # indices step in k-1 increments.

778 # The other one goes from bottom-left to top-right, for which we

779 # use index i2 and count collisions in must_be_one_3 and must_be_one_4

780 # and whose indices step in k+1 increments.

781 # Both have the central, non-mirrored version and the others

782 # which are mirrored around the central diagonal.

783 diagonal_step_1: Final[int] = k - 1

784 diagonal_step_2: Final[int] = k + 1

785 other_diagonal_start: Final[int] = n - 1

786

787 # First process unique center diagonal.

788 must_be_one_1 = 0

789 must_be_one_3: int = 0

790 d: int = k - 1

791 i1: int = k * d

792 i2: int = i1 + diagonal_step_1

793 while i1 > 0:

794 if x[i1]:

795 must_be_one_1 += 1

796 if x[i2]:

797 must_be_one_3 += 1

798 i1 -= diagonal_step_1

799 i2 -= diagonal_step_2

800 if must_be_one_1 > 1:

801 penalty += must_be_one_1 - 1

802 if must_be_one_3 > 1:

803 penalty += must_be_one_3 - 1

804

805 # Now process the mirrored diagonals

806 d -= 1

807 while d > 0:

808 must_be_one_1 = 0

809 must_be_one_3 = 0

810 must_be_one_2: int = 0

811 must_be_one_4: int = 0

812

813 i1 = k * d

814 if i1 > other_diagonal_start:

815 i1 -= diagonal_step_1 * (

816 (i1 - other_diagonal_start) // diagonal_step_1)

817 i2 = i1 + diagonal_step_1

818

819 while i1 > 0:

820 if x[i1]:

821 must_be_one_1 += 1

822 if x[other_diagonal_start - i1]:

823 must_be_one_2 += 1

824 if x[i2]:

825 must_be_one_3 += 1

826 if x[other_diagonal_start - i2]:

827 must_be_one_4 += 1

828 i1 -= diagonal_step_1

829 i2 -= diagonal_step_2

830

831 if must_be_one_1 > 1:

832 penalty += must_be_one_1 - 1

833 if must_be_one_2 > 1:

834 penalty += must_be_one_2 - 1

835 if must_be_one_3 > 1:

836 penalty += must_be_one_3 - 1

837 if must_be_one_4 > 1:

838 penalty += must_be_one_4 - 1

839 d -= 1

840

841 # penalty now holds the total number of collisions in the rows, columns,

842 # and all diagonals.

843 # queens_total is the number of queens.

844 # The minimization version of the IOHprofiler N queens problem is then:

845 return k - queens_total + (k * penalty)

846

847

848class NQueens(SquareBitStringProblem):

849 """The N-Queens problem."""

850

851 def __init__(self, n: int) -> None:

852 """

853 Initialize the n-queens problem.

854

855 :param n: the dimension of the problem (must be a perfect square)

856 and at least 16

857 """

858 super().__init__(check_int_range(n, "n", 16))

859

860 def evaluate(self, x: np.ndarray) -> int:

861 """

862 Evaluate a solution to the N-Queens problem.

863

864 :param x: the bit string to evaluate

865 :returns: the value of the N-Queens problem for the string

866 """

867 return nqueens(x, self.k)

868

869 def __str__(self) -> str:

870 """

871 Get the name of the N-Queens problem.

872

873 :return: `NQueens_` + dimension of the board

874

875 >>> NQueens(16)

876 nqueens_16

877 """

878 return f"nqueens_{self.n}"

879

880 def upper_bound(self) -> int:

881 """

882 Compute the upper bound of the N-Queens objective function.

883

884 >>> NQueens(4 * 4).upper_bound()

885 156

886

887 >>> NQueens(5 * 5).upper_bound()

888 340

889

890 >>> NQueens(6 * 6).upper_bound()

891 630

892

893 >>> NQueens(7 * 7).upper_bound()

894 1050

895

896 >>> NQueens(8 * 8).upper_bound()

897 1624

898

899 >>> NQueens(9 * 9).upper_bound()

900 2376

901

902 >>> NQueens(10 * 10).upper_bound()

903 3330

904

905 >>> NQueens(20 * 20).upper_bound()

906 29260

907

908 >>> NQueens(30 * 30).upper_bound()

909 101790

910

911 >>> NQueens(100 * 100).upper_bound()

912 3930300

913

914 >>> NQueens(6241).upper_bound()

915 1928706

916

917 >>> NQueens(4225).upper_bound()

918 1069120

919 """

920 k: Final[int] = self.k

921 return (((((k - 2) * 4) + 1) * k) + 3) * k

922

923 @classmethod

924 def default_instances(

925 cls: type, scale_min: int = 16, scale_max: int = 144) \

926 -> Iterator[Callable[[], "NQueens"]]:

927 """

928 Get the 9 default instances of the :class:`NQueens` problem.

929

930 :param scale_min: the minimum permitted scale, by default `16`

931 :param scale_max: the maximum permitted scale, by default `144`

932 :returns: a sequence of default :class:`NQueens` instances

933

934 >>> len(list(NQueens.default_instances()))

935 9

936

937 >>> [x() for x in NQueens.default_instances()]

938 [nqueens_16, nqueens_25, nqueens_36, nqueens_49, nqueens_64, \

939nqueens_81, nqueens_100, nqueens_121, nqueens_144]

940 """

941 return cast("Iterator[Callable[[], NQueens]]",

942 super().default_instances( # type: ignore

943 scale_min, scale_max))

Coverage for moptipy / examples / bitstrings / nqueens.py: 22%

91 statements