Solving N-queens problem using Google or-tools

Hello reader,

In this post, I am going to explain the code I wrote for solving the "N-queens Problem" using the "Google or-tools".

Google Optimization Tools is a software suit which makes it easy to solve many types of combinatorial optimization problems.

N-queens problem asks this question: "How can N queens be placed on an NxN chessboard so that no two of them attack each other?". Here is a solution for 4 queens:

No two queens are on the same row, column, or diagonal.

The N-queens problem is ideally suited to constraint programming. We'll walk through a simple Python program that uses or-tools to solve N-queens for any value of N.

We are going to:

1. Create the solver,
2. Define our variables,
3. Add constraints,
4. Create the search tree,
5. Iterate through the solutions.

For creating our solver, we need the "pywrapcp" module from or-tools:

from ortools.constraint_solver import pywrapcp

First we create our solver:

solver = pywrapcp.Solver("N-queens")

We should now declare our queens' coordinates as variables. We have a NxN board. So we should keep the x and y coordinates. While the first thing came to mind for storing them is to create a 2-D array, a smarter way to do is to store them in a 1-D array:  with the index representing the y coordinate(row), and the value representing the x coordinate(column).
We want our variables to be in range of 0..N. For this purpose, we are going to use "solver.IntVar". "IntVar" is an expression which allows us to define a variable's bound. Let's create our variables in one line:

queens = [solver.IntVar(0, N - 1, "q%i" % i) for i in range(N)]

That was easy, right? Now we have named our variables as "q0, q1, .., q(N-1)".

It is time to add our constraints to our solver. Basically, we have 2 constraints. We have to ensure that no two queens are:

1. On the same column: No two values of the array can be the same.
2. On the same diagonal: The values plus(and minus) the indices should be all different.

We can add the first constraint like this:

solver.Add(solver.AllDifferent(queens))

"solver.AllDifferent" enforces a set of variables to take distinct values. We can use it for the diagonal constraints too:

solver.Add(solver.AllDifferent([queens[i] + i for i in range(N)]))
solver.Add(solver.AllDifferent([queens[i] - i for i in range(N)]))

We are now ready for solving the problem. First, we should build our search tree. Using the "solver.Phase", we tell the solver what to solve. The first parameter will be our set of variables. The second parameter specifies how to choose the next "IntVar" variable to be selected in the search. The third parameter indicates what value to assign to the selected "IntVar". Since for this post the speed is not important, the default behaviors are chosen.

tree = solver.Phase(queens,
                    solver.INT_VAR_DEFAULT,
                    solver.INT_VALUE_DEFAULT)

After creating the search tree, we can now begin our search.

solver.NewSearch(tree)

We can print our solutions while iterating through them as:

    solution_count = 0
    while solver.NextSolution():
        solution_count += 1
        solution = [queens[i].Value() for i in range(N)]
        print "Solution %d:" % solution_count, solution
        for i in range(N):
            for j in range(N):
                if solution[i] == j:
                    print "Q",
                else:
                    print "_",
            print
        print

We have reached the end of our search.

The documentation says that it is just better practice to finish the search with the method "EndSearch".

solver.EndSearch()

That's it. I hope you enjoyed this walk through.

You can find the full code here:

https://gist.github.com/mfkaptan/e6416b06a60373b1340f

See you next post.