basic/n_queen.py example

 1# --------------------------------------------------------------------------
 2# Source file provided under Apache License, Version 2.0, January 2004,
 3# http://www.apache.org/licenses/
 4# (c) Copyright IBM Corp. 2015, 2022
 5# --------------------------------------------------------------------------
 6
 7"""
 8The eight queens puzzle is the problem of placing eight chess queens on an 8x8
 9chessboard so that no two queens threaten each other. Thus, a solution requires
10that no two queens share the same row, column, or diagonal.
11
12The eight queens puzzle is an example of the more general n-queens problem of
13placing n queens on an nxn chessboard, where solutions exist for all natural
14numbers n with the exception of n=2 and n=3.
15
16See https://en.wikipedia.org/wiki/Eight_queens_puzzle for more information.
17
18Please refer to documentation for appropriate setup of solving configuration.
19"""
20
21from docplex.cp.model import CpoModel
22from sys import stdout
23
24#-----------------------------------------------------------------------------
25# Initialize the problem data
26#-----------------------------------------------------------------------------
27
28# Set model parameters
29NB_QUEEN = 8
30
31
32#-----------------------------------------------------------------------------
33# Build the model
34#-----------------------------------------------------------------------------
35
36# Create model
37mdl = CpoModel()
38
39# Create column index of each queen
40x = mdl.integer_var_list(NB_QUEEN, 0, NB_QUEEN - 1, "X")
41
42# One queen per raw
43mdl.add(mdl.all_diff(x))
44
45# One queen per diagonal xi - xj != i - j
46mdl.add(mdl.all_diff(x[i] + i for i in range(NB_QUEEN)))
47
48# One queen per diagonal xi - xj != j - i
49mdl.add(mdl.all_diff(x[i] - i for i in range(NB_QUEEN)))
50
51
52#-----------------------------------------------------------------------------
53# Solve the model and display the result
54#-----------------------------------------------------------------------------
55
56# Solve model
57print("Solving model....")
58msol = mdl.solve(TimeLimit=10)
59
60# Print solution
61if msol:
62    stdout.write("Solution:")
63    for v in x:
64        stdout.write(" {}".format(msol[v]))
65    stdout.write("\n")
66    # Draw chess board
67    for l in range(NB_QUEEN):
68        qx = msol[x[l]]
69        for c in range(NB_QUEEN):
70            stdout.write(" ")
71            stdout.write("Q" if c == qx else ".")
72        stdout.write("\n")
73else:
74    stdout.write("Solve status: {}\n".format(msol.get_solve_status()))