You're reading the documentation for a development version. For the latest released version, please have a look at master.

queens_solver.solver

Functions

solve_queens_game(mat)	Solve a LinkedIn Queens puzzle using integer linear programming.
gen_constraint_mat(mat, mode)	Generate a sparse constraint coefficient matrix for the Queens puzzle.

Module Contents

queens_solver.solver.solve_queens_game(mat)

Solve a LinkedIn Queens puzzle using integer linear programming.

Formulates the Queens puzzle as a binary integer linear programming problem and solves it with scipy.optimize.linprog. Enforces one queen per row, column, and color region, with no diagonal adjacency.

Parameters:

mat (scipy.sparse.csr_array) – Sparse matrix of the puzzle board. Each entry holds the integer color ID of a cell; shape matches the puzzle dimensions.

Returns:

Dense binary array of shape (n_row, n_col) where 1 marks a queen and 0 marks an empty cell.

Raises:

RuntimeError – If the linear programming solver fails to find a valid solution.

Return type:

numpy.ndarray

queens_solver.solver.gen_constraint_mat(mat, mode)

Generate a sparse constraint coefficient matrix for the Queens puzzle.

Constructs sparse matrices for the integer linear programming formulation. The mode parameter selects the constraint type: "row", "column", or "color" for equality constraints; "\" or "/" for diagonal-adjacency upper-bound constraints.

Parameters:

• mat (scipy.sparse.csr_array) – Sparse matrix of the puzzle board. Each entry holds the integer color ID of a cell.

• mode (Literal['row', 'column', 'color', '/', '\\']) – Constraint type. One of "row", "column", "color", "\", or "/".

Returns:

CSR sparse matrix of linear constraint coefficients. Each column corresponds to a flattened board cell in row-major order (row * n_col + col).

Return type:

scipy.sparse.csr_array