1960๋…„๋Œ€ ์ดˆ์ฐฝ๊ธฐ ์ปดํ“จํ„ฐ ๊ฒŒ์ž„๋ถ€ํ„ฐ ์‹œ์ž‘๋œ ์ง€๋ขฐ์ฐพ๊ธฐ๋Š” ๋‹จ์ˆœํ•œ ๊ณ ์ „ ํผ์ฆ์„ ๋„˜์–ด, ์ด์‚ฐ์ˆ˜ํ•™(Discrete Mathematics)๊ณผ ๋…ผ๋ฆฌํ•™์˜ ์ •์ˆ˜๋ฅผ ๋‹ด๊ณ  ์žˆ๋Š” ์ง€์  ์‚ฐ๋ฌผ์ž…๋‹ˆ๋‹ค. ์ด ๊ฒŒ์ž„์˜ ๋ณธ์งˆ์€ **'์ œ์•ฝ ์ถฉ์กฑ ๋ฌธ์ œ(Constraint Satisfaction Problem)'**๋กœ ์ •์˜๋  ์ˆ˜ ์žˆ์œผ๋ฉฐ, ์ด๋Š” ํ˜„๋Œ€ ์ปดํ“จํ„ฐ ๊ณผํ•™์—์„œ ์ธ๊ณต์ง€๋Šฅ ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐฉ์‹๊ณผ ๋งค์šฐ ์œ ์‚ฌํ•ฉ๋‹ˆ๋‹ค.

๊ฐ ๊ฒฉ์ž์— ํ‘œ์‹œ๋œ ์ˆซ์ž๋Š” ์ธ์ ‘ํ•œ 8๊ฐœ์˜ ๋ฏธํ™•์ธ ์˜์—ญ ๋‚ด์— ์กด์žฌํ•˜๋Š” ์ง€๋ขฐ์˜ ๊ฐœ์ˆ˜๋ฅผ ๋ช…์‹œํ•˜๋Š” '์ˆ˜ํ•™์  ์ƒ์ˆ˜' ์—ญํ• ์„ ํ•ฉ๋‹ˆ๋‹ค. ํ”Œ๋ ˆ์ด์–ด๋Š” ์ด ์ƒ์ˆ˜๋ฅผ ๋ฐ”ํƒ•์œผ๋กœ '๋ชจ์ˆœ ์ œ๊ฑฐ๋ฒ•(Proof by Contradiction)'์„ ์ˆ˜ํ–‰ํ•ฉ๋‹ˆ๋‹ค. ์˜ˆ๋ฅผ ๋“ค์–ด, ํŠน์ • ์ˆซ์ž์˜ ์ œ์•ฝ ์กฐ๊ฑด์ด ์ด๋ฏธ ์ถฉ์กฑ๋˜์—ˆ๋‹ค๋ฉด ์ฃผ๋ณ€์˜ ๋ชจ๋“  ๋ฏธํ™•์ธ ์นธ์€ ์•ˆ์ „ํ•œ ์นธ์œผ๋กœ ํ™•์ •๋˜๋ฉฐ, ๋ฐ˜๋Œ€๋กœ ๋‚จ์€ ์นธ์˜ ์ˆ˜๊ฐ€ ์ˆซ์ž์™€ ์ผ์น˜ํ•œ๋‹ค๋ฉด ๊ทธ๊ณณ์€ ๋ฐ˜๋“œ์‹œ ์ง€๋ขฐ๋ผ๋Š” '๋…ผ๋ฆฌ์  ํ•„์—ฐ์„ฑ'์ด ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค.