# Problemy z ograniczeniami (CSP)

EN: **Constraint satisfaction problems (CSP)** · id `csp`

Path: [AI Atlas](https://aiatlasgraph.com/llms.txt) › [Fundamenty i rozumowanie](https://aiatlasgraph.com/t/foundations.md) › [Przeszukiwanie i planowanie](https://aiatlasgraph.com/t/search.md) › Problemy z ograniczeniami (CSP)

## Description

- PL: Przypisywanie wartości zmiennym tak, by spełnić wszystkie ograniczenia — harmonogramy, układy, sudoku.
- EN: Assigning values to variables so all constraints hold — schedules, layouts, sudoku.

## In one sentence

- PL: To szukanie układu, w którym wszystkie zapisane warunki są spełnione jednocześnie.
- EN: This finds an arrangement that satisfies all recorded conditions at once.

## Problem it solves

- PL: Wiele wyborów zależy od siebie, więc poprawienie jednego fragmentu może zepsuć inny.
- EN: Many choices depend on each other, so fixing one part can break another.

## What it does

- PL: Odrzuca wartości sprzeczne z warunkami, sprawdza pozostałe połączenia i cofa wcześniejsze wybory, gdy prowadzą do sprzeczności.
- EN: It rules out values that violate conditions, tests remaining combinations and revisits earlier choices when they create contradictions.

## Everyday example

- PL: Układasz spotkania tak, żeby uczestnicy byli dostępni, sale się nie nakładały, a potrzebny sprzęt był na miejscu.
- EN: You schedule meetings so participants are available, rooms are not double booked and the required equipment is present.

## This concerns you if you…

- PL: musisz spełnić wiele warunków jednocześnie
- PL: układasz harmonogram, przydział lub rozmieszczenie rzeczy
- EN: need to satisfy several conditions at once
- EN: arrange schedules, assignments or the placement of objects

## Keywords

backtracking · constraint propagation · arc consistency · AC-3 · SAT solving · constraint programming

## How it works

- PL: Zmienne mają dziedziny wartości, a ograniczenia określają dopuszczalne kombinacje. Propagacja usuwa wartości bez wsparcia, natomiast przeszukiwanie z nawrotami wybiera przypisania i cofa te prowadzące do konfliktu.
- EN: Variables have value domains, and constraints define permitted combinations. Propagation removes unsupported values, while backtracking search selects assignments and reverses those leading to conflicts.

## Limits

- PL: Lokalna zgodność nie gwarantuje rozwiązania całego układu. Trudność zależy od struktury i siły ograniczeń; słaba propagacja pozostawia dużą przestrzeń przeszukiwania.
- EN: Local consistency does not guarantee a complete solution. Difficulty depends on constraint structure and strength; weak propagation leaves a large search space.

## Key terms

- PL: **dziedzina**: Zbiór wartości dopuszczonych dla danej zmiennej.
- PL: **propagacja ograniczeń**: Usuwanie kandydatów niespełniających warunków wynikających z innych zmiennych.
- EN: **domain**: The set of allowed values for a variable.
- EN: **constraint propagation**: Removing candidates violating conditions implied by other variables.

## Know first

- [Logika zdań i logika pierwszego rzędu (Propositional and first-order logic)](https://aiatlasgraph.com/t/fol.md)
- [Przeszukiwanie ślepe (BFS, DFS) (Uninformed search (BFS, DFS, uniform-cost))](https://aiatlasgraph.com/t/uninformedsearch.md)

## Examples

- PL: Backtracking · propagacja ograniczeń · układanie grafików · solwery SAT
- EN: Backtracking · constraint propagation · timetabling · SAT solvers

## Related topics

Untyped, symmetric "see also" links.

- [Generowanie z lokalnych wzorów (Wave Function Collapse) (Wave Function Collapse and constraint-based generation)](https://aiatlasgraph.com/t/wfc.md)

## Sources

- [Berkeley CS188 · Introduction to Artificial Intelligence (Fall 2025)](<https://inst.eecs.berkeley.edu/~cs188/fa25/>) `cs188fa25` · by Emma Pierson, Peyrin Kao (prowadzący)
- [Russell & Norvig · Artificial Intelligence: A Modern Approach, 4th ed. — table of contents](<https://aima.cs.berkeley.edu/>) `aima4` · by Stuart Russell, Peter Norvig

---

AI Atlas revision 122 (2026-10-30) · HTML: https://aiatlasgraph.com/t/csp · index: https://aiatlasgraph.com/llms.txt · everything: https://aiatlasgraph.com/llms-full.txt · updated 2026-10-30