Files

297 lines
13 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

---
id: 5900f3cc1000cf542c50fedf
title: '問題 96數獨'
challengeType: 5
forumTopicId: 302213
dashedName: problem-96-su-doku
---
# --description--
數獨(日語含義爲*數字位置*)是一個非常流行的解密遊戲。 它的起源尚不清楚但必須歸功於萊昂哈德·歐拉Leonhard Euler他發明了一種類似的但更加困難的解密遊戲名叫拉丁方塊Latin Squares。 數獨的目標是用數字替換 9X9 網格中的空白(或零),使得每行,每列和每個 3X3 小網格中都只包含 1 到 9 這 9 個數字。 下面是一個示例,包含一個經典的謎題及其對應解。
<div style="margin: auto; background-color: white; padding: 10px; width: 80%; text-align: center;">
<table border="0" cellpadding="0" cellspacing="0" align="center">
<tbody>
<tr>
<td>
<table cellpadding="5" cellspacing="0" border="1">
<tbody>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
0 0 3<br />9 0 0<br />0 0 1
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
0 2 0<br />3 0 5<br />8 0 6
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
6 0 0<br />0 0 1<br />4 0 0
</td>
</tr>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
0 0 8<br />7 0 0<br />0 0 6
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
1 0 2<br />0 0 0<br />7 0 8
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
9 0 0<br />0 0 8<br />2 0 0
</td>
</tr>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
0 0 2<br />8 0 0<br />0 0 5
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
6 0 9<br />2 0 3<br />0 1 0
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
5 0 0<br />0 0 9<br />3 0 0
</td>
</tr>
</tbody>
</table>
</td>
<td width="50">
<img src="images/spacer.gif" width="50" height="1" alt="" /><br />
</td>
<td>
<table cellpadding="5" cellspacing="0" border="1">
<tbody>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
4 8 3<br />9 6 7<br />2 5 1
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
9 2 1<br />3 4 5<br />8 7 6
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
6 5 7<br />8 2 1<br />4 9 3
</td>
</tr>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
5 4 8<br />7 2 9<br />1 3 6
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
1 3 2<br />5 6 4<br />7 9 8
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
9 7 6<br />1 3 8<br />2 4 5
</td>
</tr>
<tr>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
3 7 2<br />8 1 4<br />6 9 5
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
6 8 9<br />2 5 3<br />4 1 7
</td>
<td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
5 1 4<br />7 6 9<br />3 8 2
</td>
</tr>
</tbody>
</table>
</td>
</tr>
</tbody>
</table>
</div>
一個構造良好的數獨謎題應該只有一個唯一的解,可以通過邏輯解出,雖然可能需要採用“猜測和測試”方法來排除選項(對此有很多爭議的意見)。 搜索的複雜性決定了謎題的難度;上面的示例很簡單,因此可以通過直接的邏輯推理來解出答案。
`puzzlesArr` 數組裏有若干個數獨謎題字符串,難度不一,但是每個謎題的解都是唯一的。
通過解出 `puzzlesArr` 數組中所有謎題返回所有解左上角三位數字之和舉個例子483 就是上述例子中左上角的三位數字。
# --hints--
`suDoku(testPuzzles1)` 應該返回一個數字。
```js
assert(typeof suDoku(_testPuzzles1) === 'number');
```
`suDoku(testPuzzles1)` 應該返回 `1190`
```js
assert.strictEqual(suDoku(_testPuzzles1), 1190);
```
`suDoku(testPuzzles2)` 應該返回 `24702`
```js
assert.strictEqual(suDoku(_testPuzzles2), 24702);
```
# --seed--
## --after-user-code--
```js
const _testPuzzles1 = [
'003020600900305001001806400008102900700000008006708200002609500800203009005010300',
'200080300060070084030500209000105408000000000402706000301007040720040060004010003',
'000000907000420180000705026100904000050000040000507009920108000034059000507000000'
];
const _testPuzzles2 = [
'003020600900305001001806400008102900700000008006708200002609500800203009005010300',
'200080300060070084030500209000105408000000000402706000301007040720040060004010003',
'000000907000420180000705026100904000050000040000507009920108000034059000507000000',
'030050040008010500460000012070502080000603000040109030250000098001020600080060020',
'020810740700003100090002805009040087400208003160030200302700060005600008076051090',
'100920000524010000000000070050008102000000000402700090060000000000030945000071006',
'043080250600000000000001094900004070000608000010200003820500000000000005034090710',
'480006902002008001900370060840010200003704100001060049020085007700900600609200018',
'000900002050123400030000160908000000070000090000000205091000050007439020400007000',
'001900003900700160030005007050000009004302600200000070600100030042007006500006800',
'000125400008400000420800000030000095060902010510000060000003049000007200001298000',
'062340750100005600570000040000094800400000006005830000030000091006400007059083260',
'300000000005009000200504000020000700160000058704310600000890100000067080000005437',
'630000000000500008005674000000020000003401020000000345000007004080300902947100080',
'000020040008035000000070602031046970200000000000501203049000730000000010800004000',
'361025900080960010400000057008000471000603000259000800740000005020018060005470329',
'050807020600010090702540006070020301504000908103080070900076205060090003080103040',
'080005000000003457000070809060400903007010500408007020901020000842300000000100080',
'003502900000040000106000305900251008070408030800763001308000104000020000005104800',
'000000000009805100051907420290401065000000000140508093026709580005103600000000000',
'020030090000907000900208005004806500607000208003102900800605007000309000030020050',
'005000006070009020000500107804150000000803000000092805907006000030400010200000600',
'040000050001943600009000300600050002103000506800020007005000200002436700030000040',
'004000000000030002390700080400009001209801307600200008010008053900040000000000800',
'360020089000361000000000000803000602400603007607000108000000000000418000970030014',
'500400060009000800640020000000001008208000501700500000000090084003000600060003002',
'007256400400000005010030060000508000008060200000107000030070090200000004006312700',
'000000000079050180800000007007306800450708096003502700700000005016030420000000000',
'030000080009000500007509200700105008020090030900402001004207100002000800070000090',
'200170603050000100000006079000040700000801000009050000310400000005000060906037002',
'000000080800701040040020030374000900000030000005000321010060050050802006080000000',
'000000085000210009960080100500800016000000000890006007009070052300054000480000000',
'608070502050608070002000300500090006040302050800050003005000200010704090409060701',
'050010040107000602000905000208030501040070020901080406000401000304000709020060010',
'053000790009753400100000002090080010000907000080030070500000003007641200061000940',
'006080300049070250000405000600317004007000800100826009000702000075040190003090600',
'005080700700204005320000084060105040008000500070803010450000091600508007003010600',
'000900800128006400070800060800430007500000009600079008090004010003600284001007000',
'000080000270000054095000810009806400020403060006905100017000620460000038000090000',
'000602000400050001085010620038206710000000000019407350026040530900020007000809000',
'000900002050123400030000160908000000070000090000000205091000050007439020400007000',
'380000000000400785009020300060090000800302009000040070001070500495006000000000092',
'000158000002060800030000040027030510000000000046080790050000080004070100000325000',
'010500200900001000002008030500030007008000500600080004040100700000700006003004050',
'080000040000469000400000007005904600070608030008502100900000005000781000060000010',
'904200007010000000000706500000800090020904060040002000001607000000000030300005702',
'000700800006000031040002000024070000010030080000060290000800070860000500002006000',
'001007090590080001030000080000005800050060020004100000080000030100020079020700400',
'000003017015009008060000000100007000009000200000500004000000020500600340340200000',
'300200000000107000706030500070009080900020004010800050009040301000702000000008006'
];
```
## --seed-contents--
```js
function suDoku(puzzlesArr) {
return true;
}
// Only change code above this line
const testPuzzles1 = [
'003020600900305001001806400008102900700000008006708200002609500800203009005010300',
'200080300060070084030500209000105408000000000402706000301007040720040060004010003',
'000000907000420180000705026100904000050000040000507009920108000034059000507000000'
];
suDoku(testPuzzles1);
```
# --solutions--
```js
function suDoku(puzzlesArr) {
function solve(puzzle) {
for (let row = 0; row < 9; row++) {
for (let col = 0; col < 9; col++) {
if (puzzle[row][col] > 0) {
continue;
}
const allowedNumbers = getAllowedNumbers(puzzle, row, col);
for (let number = 1; number <= 9; number++) {
if (allowedNumbers[number]) {
puzzle[row][col] = number;
if (solve(puzzle)) {
return true;
}
}
}
puzzle[row][col] = 0;
return false;
}
}
return true;
}
function getAllowedNumbers(puzzle, row, col) {
const allowed = new Array(10).fill(true);
allowed[0] = false;
for (let i = 0; i < 9; i++) {
const numberInSameRow = puzzle[row][i];
if (numberInSameRow > 0) {
allowed[numberInSameRow] = false;
}
const numberInSameCol = puzzle[i][col];
if (numberInSameCol > 0) {
allowed[numberInSameCol] = false;
}
}
const rowOfSubGrid = Math.floor(row / 3) * 3;
const colOfSubGrid = Math.floor(col / 3) * 3;
for (let rowInSubGrid = 0; rowInSubGrid < 3; rowInSubGrid++) {
for (let colInSubGrid = 0; colInSubGrid < 3; colInSubGrid++) {
const numberInSameSubGrid =
puzzle[rowOfSubGrid + rowInSubGrid][colOfSubGrid + colInSubGrid];
if (numberInSameSubGrid > 0) {
allowed[numberInSameSubGrid] = false;
}
}
}
return allowed;
}
function parsePuzzle(string) {
const puzzle = [];
for (let row = 0; row < 9; row++) {
puzzle.push(
string
.slice(row * 9, 9 + row * 9)
.split('')
.map(x => parseInt(x, 10))
);
}
return puzzle;
}
let sum = 0;
for (let i = 0; i < puzzlesArr.length; i++) {
const puzzle = parsePuzzle(puzzlesArr[i]);
if (solve(puzzle)) {
sum += 100 * puzzle[0][0] + 10 * puzzle[0][1] + puzzle[0][2];
}
}
return sum;
}
```