ClassicComputerScienceProblemsInPython/Chapter3/queens.py at master · giuice/ClassicComputerScienceProblemsInPython · GitHub

History

50 lines (45 loc) · 1.88 KB

Raw

# queens.py

# From Classic Computer Science Problems in Python Chapter 3

# Licensed under the Apache License, Version 2.0 (the "License");

# you may not use this file except in compliance with the License.

# You may obtain a copy of the License at

# http://www.apache.org/licenses/LICENSE-2.0

# Unless required by applicable law or agreed to in writing, software

# distributed under the License is distributed on an "AS IS" BASIS,

# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.

# See the License for the specific language governing permissions and

# limitations under the License.

from csp import Constraint, CSP

from typing import Dict, List, Optional

class QueensConstraint(Constraint[int, int]):

def __init__(self, columns: List[int]) -> None:

super().__init__(columns)

self.columns: List[int] = columns

def satisfied(self, assignment: Dict[int, int]) -> bool:

# q1c = queen 1 column, q1r = queen 1 row

for q1c, q1r in assignment.items():

# q2c = queen 2 column

for q2c in range(q1c + 1, len(self.columns) + 1):

if q2c in assignment:

q2r: int = assignment[q2c] # q2r = queen 2 row

if q1r == q2r: # same row?

return False

if abs(q1r - q2r) == abs(q1c - q2c): # same diagonal?

return False

return True # no conflict

if __name__ == "__main__":

columns: List[int] = [1, 2, 3, 4, 5, 6, 7, 8]

rows: Dict[int, List[int]] = {}

for column in columns:

rows[column] = [1, 2, 3, 4, 5, 6, 7, 8]

csp: CSP[int, int] = CSP(columns, rows)

csp.add_constraint(QueensConstraint(columns))

solution: Optional[Dict[int, int]] = csp.backtracking_search()

if solution is None:

print("No solution found!")

else:

print(solution)

ClassicComputerScienceProblemsInPython/Chapter3/queens.py at master · giuice/ClassicComputerScienceProblemsInPython · GitHub

Expand file tree

Breadcrumbs

queens.py

Latest commit

History

Breadcrumbs

queens.py

File metadata and controls