흥미롭고 유머러스한 - 페이지 3970

[Andrey Kisselyov]

Дмитрий :

그러니 가서 100만 달러를 가져오세요. 패키지를 가져가세요

그들이 정말로 해결책이 필요하다면 스스로 해결할 것입니다.

감사합니다.

[Dr. Trader]

Vladimir Suschenko :

힌트에 대한 설명 - 우리는 일반 알고리즘(아마도 그 중 하나 이상이 있을 수 있음)뿐만 아니라 최신 컴퓨터가 큰 보드 차원의 문제를 실시간으로 해결할 수 있도록 하는 알고리즘이 필요합니다. 사용 가능한 알고리즘으로 많은 필드의 문제를 해결하려면 최신 컴퓨터에 너무 많은 시간(및 메모리)이 필요할 수 있습니다.

이제 SAT/SMT 솔버로 이러한 문제를 해결하는 것이 유행입니다. 해결 속도를 최대화하려면 부울 함수의 문제를 cnf 형식으로 표현한 다음 이 문서 http://www.cs.cmu.edu/~hjain/papers/sudoku-as-SAT의 예를 어떻게든 따라야 합니다. PDF

그건 그냥 sat solver가 문제를 해결할 수 있는지 여부에 대해 yes/no의 형태로 간단히 답을 줄 것입니다. 거기에서 답(그림의 위치)을 얻는 방법을 모릅니다. 이 기술을 어떻게 사용해야 하는지 모르겠습니다.

[Roman Shiredchenko]

그리샤 봐 ... 바로 지금 ..

[Roman Shiredchenko]

그런 분들을 위해

https://www.youtube.com/watch?v=VpOqb-0Ec4w

[Roman Shiredchenko]

재미있고 흥미롭다

[Roman Shiredchenko]

임호

[Dr. Trader]

다음은 8개의 퀸에 대한 문제에 대한 상당히 빠른 솔루션입니다. 파이썬에서는 36밀리초 안에 해결할 수 있습니다. http://www.cs.tau.ac.il/~msaiv/courses/asv/z3py/guide-examples. htm ("여덟 개의 여왕"이라는 제목을 찾아야 함)

python https://github.com/Z3Prover/z3/releases 에 이 라이브러리가 필요하며 코드 자체에서 먼저 "from z3 import *"를 실행한 다음 첫 번째 링크에 있는 코드만 실행합니다.

100만 벌면 안되고, 퀸의 수에 따라 풀어야 하는 시간이 기하급수적으로 늘어납니다. 예를 들어 100퀸의 문제는 이미 30분 정도 풀렸습니다.

[Oksana Berenko]

geratdc :

문제는 해결책이 없습니다. 7 개의 여왕이 체스 판의 전체 영역을 덮습니다.

그것은 가지고 있습니다 :

[Denis Sartakov]

거의 서사시 시대에 ... 예?

[Andrey Kisselyov]

Dr. Trader :

다음은 8개의 퀸에 대한 문제에 대한 상당히 빠른 솔루션입니다. 파이썬에서는 36밀리초 안에 해결할 수 있습니다. http://www.cs.tau.ac.il/~msaiv/courses/asv/z3py/guide-examples. htm ("여덟 여왕"이라는 제목을 찾아야 함)

python https://github.com/Z3Prover/z3/releases 에 이 라이브러리가 필요하며 코드 자체에서 먼저 "from z3 import *"를 실행한 다음 첫 번째 링크에 있는 코드만 실행합니다.

100만 벌면 안되고, 퀸의 수에 따라 풀어야 하는 시간이 기하급수적으로 늘어납니다. 예를 들어 100퀸의 문제는 이미 30분 정도 풀렸습니다.

이 문서는 1000개 이상의 셀 측면이 있는 필드에 관한 것입니다. 100 * 100 필드에 이미 30분이 필요하다는 사실을 기반으로 알고리즘은 이것을 풀지 않을 것입니다.

감사합니다.