여러 가지 가능성을 가진 셀의 합

Question

저는 Ruby에서 Killer Sudoku Solver를 프로그래밍하고 있습니다. 나는 인간의 전략을 취하여 코드에 넣으려고합니다. 나는 약 10 개의 전략을 구현했지만이 문제에 대해서는 문제가있다.

킬러 스도쿠에서는 셀의 "구역"이 있으며이 셀의 합을 알기 때문에 각 셀의 가능성을 알 수 있습니다.

예 :

는

• 전지 (1)가 될 수있는 1, 3, 4 또는 9
• 셀 2는 2, 4 또는 5
• 셀 3 일 수 3, 4 또는 9
• 될 수 모든 셀의 합은 12이어야합니다.

가능성을 제거하기 위해 모든 가능성을 시험해 보시기 바랍니다. 예를 들어 셀 2는 3을 만들 수 없기 때문에 셀 1은 9가 될 수 없습니다.

그래서 원하는 수의 셀을 필요로합니다. 그것들을 시도하고 그것이 작동하지 않는 것을 보는 것은 불가능합니다.

어떻게하면됩니까?

Answer 1

게임 해결의 일반적인 문제에 접근하는 여러 가지 방법이 있으며 인간 전략을 모방하는 것이 항상 최선의 방법은 아닙니다.

첫번째 방법,

는 기본적으로, 우리는 세포의 조합의 모든 가능성을 시도하려는 짐승 - forcy하고 올바른 합계를 가지고있는 사람을 선택 : 그것은 여기에 당신이 당신의 질문을 해결할 수있는 방법은 말했다.

cell_1 = [1,3,4,9] 
cell_2 = [2,4,5] 
cell_3 = [3,4,9] 
all_valid_combinations = cell_1.product(cell_2,cell_3).select {|combo| combo.sum == 12} 
# => [[1, 2, 9], [3, 5, 4], [4, 4, 4], [4, 5, 3]] 
#.sum isn't a built-in function, it's just used here for convenience 

은 개별 셀이 아래로 껍질을 벗기다, 당신은 할 수 있습니다 : 당신은 세포의 거대한 대형 세트가없는 경우

cell_1 = all_valid_combinations.map {|combo| combo[0]}.uniq 
# => [1, 3, 4] 
cell_2 = all_valid_combinations.map {|combo| combo[1]}.uniq 
# => [2, 5, 4] 
. . . 

는,이 방법으로 코드 쉽습니다. 그것은 약간의 비능률적 인 것을 얻을 수 있습니다. 작은 문제의 경우, 이것이 제가 사용하는 방법입니다. 검색

또 다른 잘 알려진 기술을 역 추적

---

두번째 방법은 다른 접근 방식에서 문제가 걸립니다. 기본적으로 각 셀에 대해 "이 셀을 다른 셀에 지정할 수 있습니까?"라고 물어보십시오.

셀 1부터 시작하여 숫자는 1 일 수 있습니까? 확인하기 위해 셀 2와 셀 3의 합이 11이 될 수 있는지 확인합니다. (12-1) * 셀 2의 값은 2입니까? 확인하려면 셀 3 합계 9 (11-1)

등등 수 있습니다. 아주 많은 경우에 유효한 조합을 여러 개 가질 수있는 경우 셀에 대해 유효한 숫자를 처음 발견 할 때 'true'를 반환 할 수 있기 때문에 약간 더 빠릅니다. 어떤 사람들은 재귀 알고리즘이 좀 더 어려워지기 때문에 마일리지가 다를 수 있습니다.