コーディングしなさすぎてコーディングを忘れたエンジニアがコーディングを思い出すためにコーティングします。
今回は、アメリカのコーデイング練習サイトCodeSignalの問題「sudoku2」を解いていきます。
サイトによると、この問題はApple、UBERの面接で出されたことがあるようです。
問題
9×9マスの数独を表す、以下のような2次元配列が与えられます。
grid = [['.', '.', '.', '1', '4', '.', '.', '2', '.'],
['.', '.', '6', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '1', '.', '.', '.', '.', '.', '.'],
['.', '6', '7', '.', '.', '.', '.', '.', '9'],
['.', '.', '.', '.', '.', '.', '8', '1', '.'],
['.', '3', '.', '.', '.', '.', '.', '.', '6'],
['.', '.', '.', '.', '.', '7', '.', '.', '.'],
['.', '.', '.', '5', '.', '.', '.', '7', '.']]
数独をご存知の方ならわかると思いますが、数独のルールでは、縦9マス、横9マス、3×3の範囲それぞれで1〜9の文字が重複してはいけません。
3×3の範囲というのは、次の枠組み内のことを意味しています。
この問題では、この解き途中みたいな数独について上記の3点のポイントをチェックし、条件を満たしていればture、そうでなければfalseを返す関数を書きます。
たとえば、上の例なら縦9マス、横9マス、3×3の範囲どれをチェックしても数値は重複してないので、答えはtrueです。
一方、下の例なら答えはfalseです。
真ん中の下段の3×3の範囲に2が2回登場しているからです。
grid = [['.', '.', '.', '.', '2', '.', '.', '9', '.'],
['.', '.', '.', '.', '6', '.', '.', '.', '.'],
['7', '1', '.', '.', '7', '5', '.', '.', '.'],
['.', '7', '.', '.', '.', '.', '.', '.', '.'],
['.', '.', '.', '.', '8', '3', '.', '.', '.'],
['.', '.', '8', '.', '.', '7', '.', '6', '.'],
['.', '.', '.', '.', '.', '2', '.', '.', '.'],
['.', '1', '.', '2', '.', '.', '.', '.', '.'],
['.', '2', '.', '.', '3', '.', '.', '.', '.']]
解き方・考え方
まず普通に考えたら、縦、横、3×3のそれぞれについて重複を確認し、どれか一つでも重複があればその時点でfalseを返せばいいですよね。
、、、
それしか思い浮かびませんでした。
Javaで書くとこんな感じです。
boolean sudoku2(char[][] grid) {
boolean answer = true;
HashSet<Character> seen = new HashSet<>();
char target;
// check row
for (int i=0; i<grid.length; i++) {
seen.clear();
for (int j=0; j<grid[i].length; j++) {
target = grid[i][j];
if (seen.contains(target) && target != '.') {
return false;
} else {
seen.add(target);
}
}
}
// check column
for (int i=0; i<grid.length; i++) {
seen.clear();
for (int j=0; j<grid[i].length; j++) {
target = grid[j][i];
if (seen.contains(target) && target != '.') {
System.out.println("check column false");
return false;
} else {
seen.add(target);
}
}
}
// check subgrid
for(int startRow=0; startRow<9; startRow+=3){
for(int startColumn=0; startColumn<9; startColumn+=3){
//loop inside grid
seen.clear();
for(int i=startRow; i<startRow+3; i++){
for(int j=startColumn; j<startColumn+3; j++){
target = grid[i][j];
if(seen.contains(target) && target != '.') {
return false;
} else {
seen.add(target);
}
}
}
}
}
return true;
}
コードの説明：seenというHashSetを用意し、その中にチェックした数値を入れて重複していないか確認しています。チェックする観点が3つあるので、それぞれ上から行（// check rowの箇所）、列（//check columnの箇所）、3×3（// check subgridの箇所）と固まりがあります。
さて、これでもテストは通ったのですが、他の方のコードを見るともっとはるかにいい方法がありました。
そのまま転載は微妙なので、アイデアはパクってコードは少し変えて掲載します。
boolean sudoku2(char[][] grid) {
Set<String> seen = new HashSet<String>();
for (int i=0; i<grid.length; i++){
for (int j=0; j<grid.length; j++){
if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in row " + i)) {return false;}
if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in col " + j)) {return false;}
if (grid[i][j] != '.' && !seen.add(grid[i][j] + " in row " + i/3 + " " + j/3)) {return false;}
}
return true;
}
}
コードの説明：seenにチェックした値を入れるのは前のコードと同じですが、この場合はループは2個しか使っていません。2次元配列の値を先頭から一つずつチェックしていき、ただチェックした値を入れるのではなく、こんな感じで文字列として保存します。
1 in row 0
1 in column 0
1 in subgrid 0
このおかげで、たとえば同じ1でも「X行目に出てきた1」「X列目に出てきた1」「ここの3×3で出てきた1」のように別ものとして保存できます。
そのため、ループは一回でも一気に3つの観点で重複を確認できます。
最後に、HashSetのaddは追加しようとする値と同じ値がすでにある場合はfalseを返すので、falseの場合（重複している場合）はreturn falseとします。
この考え方にたどり着くには、まずはループを少なくしようとすることだと思います。
次に、確認観点が3つあるからといって、同じ値を別のところでそれぞれ確認するのは無駄、という考え方をしなきゃいけない気がします。
ここまでくれば上の例のようにスマートには解けなくても、「じゃあHashSetを3つ作って、配列の値を一つづつ見ていきながらそれぞれに格納していこう」、などという発想が生まれそうです。