퍼즐 해결을위한 프로그래밍 디자인

Question

죄송합니다. 여기에 잘못 게시했습니다. 하지만 일종의 Stackoverflow 채널 내가 이것을 게시해야하며이 최선이라고 생각하지 않았다.

저는 KenKen 퍼즐을 풀고 있습니다. 그것은 스도쿠와 매우 유사하며 합계와 연산자가있는 일부 케이지가 있으며 고유 번호를 사용하여 채우기 상자를 해결해야합니다.

퍼즐을 풀기 위해 나는 새장의 총 가치와 같은 각 새장에 대한 값을 얻을 수있는 입력을 가지게 될 것입니다. 연산자는 관련된 광고 상자에 사용됩니다. 되돌아을 사용하여 문제를 해결하기위한 나의 방법으로 당

:

1. 나는 각 케이지의 클래스 데이터 구조를 만들 수있는 입력을 구문 분석하고있다.

2. 나중에 각 케이지에 대한 클래스 개체 배열을 만듭니다.

3. 그런 다음이 퍼즐을 해결하기 위해 백 트랙킹을 사용하여 알고리즘을 적용 할 것입니다.

나는 단지 그들이 프로그래밍 방식이 옳다고 생각한다면, 여기에 사람과상의하고 싶었 코딩을 시작하거나 나에게 뭔가를 제안하려는 경우 내가 여전히 접근 방식을 변경해야하거나 수행하기 전에 풀다.

Answer 1

역 추적은 아마이 문제를 해결하는 가장 좋은 방법 중 하나라고 생각합니다. 솔직히 나는 지금 더 나은 것을 알 수 없습니다.

알고리즘에서 정확히 무엇을 할 계획인지 알 수 없습니다. 하지만 역 추적 자체에만 의존해서는 안됩니다. 나는 KenKen이 무엇인지 알기 위해서 wikipedia에 대한 기사만을 읽었습니다. 그러나 처음부터 역 추적을 향상시킬 수있는 것처럼 보입니다.

역 추적의 경우 일반적으로 스택을 사용합니다. 그래서 아마 어떤 케이지에 어떤 숫자를 넣었는지를 알려주는 객체들을 가진 스택을 가지고있을 것입니다. 이제이 스택 객체 각각에 알고리즘이 여러 가지 가능성 중에서이 숫자를 선택했는지 또는 알고리즘이 다른 선택 사항이 없어이 위치에서이 숫자를 선택했는지 여부를 알려주는 속성을 제공 할 수 있습니다. 그래서 그 대신 같은 스택 :

(2,2) 5 
(1,1) 4 
(0,0) 1 

과 같을 것이다 당신의 스택 : 당신이 다른 값을 선택 할 수 없기 때문에, 당신은 마지막으로 "묵시적"만 역 추적해야 다음

(2,2) 5 CHOSEN 
(1,1) 4 IMPLIED 
(0,0) 1 CHOSEN 

과 이리. 또한 다른 모든 선택 사항이 잘못 되었다면 어떤 것이 암시 될 수 있습니다. KenKen에서 이것이 얼마나 멀리 가능한지 모르겠습니다. 처음에는 알고리즘이 나중에이 장소에서 실제로 암시되지는 않지만 IMPLIED를 사용하도록 알고리즘을 강제 할 수는 없습니다.