何これ
私は友好祭で展示した作品をリファクタリング(?)して大きな盤面も追加してついでに見た目を改善しただけで白鷺祭に展示しました(のプラカードを首から提げています)
リファクタリングと主張するために、内部の計算方法も変えました
ま実はここまでしなくても高速に求められた説はありますが
DPって何
何なんですかね
🤔
いや私も実質コピペなのでよく分かってないんですYURUSHITE
コピペ元はここです
じゃあなおさらこの記事は何
一応js用に書き直したので備忘録です
ソースコード
解答盤面数算出部のみ抜粋です
const BOARD_SIZE_LIST = [4, 6];
let allAnswerPattern = { 4: [], 6: [] };
function calcAllPatterns() {
for (let calcAnswerBoardSize of BOARD_SIZE_LIST) {
const WIDTH = calcAnswerBoardSize;
const HEIGHT = calcAnswerBoardSize;
const BLOCK_HEIGHT = Math.floor(Math.sqrt(calcAnswerBoardSize));
const BLOCK_WIDTH = calcAnswerBoardSize / BLOCK_HEIGHT;
let workBoard = new Array(HEIGHT);
for (let y = 0; y < HEIGHT; y++) {
workBoard[y] = new Array(WIDTH).fill(0);
}
for (let x = 0; x < WIDTH; x++) {
workBoard[0][x] = x + 1;
}
let dupRow = new Array(WIDTH);
for (let x = 0; x < WIDTH; x++) {
dupRow[x] = new Array(calcAnswerBoardSize).fill(false);
}
let dupColumn = new Array(HEIGHT);
for (let y = 0; y < HEIGHT; y++) {
dupColumn[y] = new Array(calcAnswerBoardSize).fill(false);
}
let dupBlock = new Array(calcAnswerBoardSize / BLOCK_HEIGHT);
for (let y = 0; y < calcAnswerBoardSize / BLOCK_HEIGHT; y++) {
dupBlock[y] = new Array(calcAnswerBoardSize / BLOCK_WIDTH);
for (let x = 0; x < calcAnswerBoardSize / BLOCK_WIDTH; x++) {
dupBlock[y][x] = new Array(calcAnswerBoardSize).fill(false);
}
}
function judgeNumPosition(x, y, num) {
if (dupRow[y][num] === false && dupColumn[x][num] === false && dupBlock[Math.floor(y / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num] === false) {
workBoard[y][x] = num + 1;
dupRow[y][num] = true;
dupColumn[x][num] = true;
dupBlock[Math.floor(y / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num] = true;
return (true);
}
return (false);
}
function deleteNumPosition(x, y, num) {
workBoard[y][x] = 0;
dupRow[y][num] = false;
dupColumn[x][num] = false;
dupBlock[Math.floor(y / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num] = false;
}
function judgeContinueToFill(x, y) {
if (x === HEIGHT - 1) {
if (y === WIDTH - 1) {
allAnswerPattern[calcAnswerBoardSize].push(JSON.parse(JSON.stringify(workBoard)));
return (false);
}
else {
return ("y");
}
}
else {
return ("x");
}
}
function solve(x, y) {
if (workBoard[y][x] > 0) {
switch (judgeContinueToFill(x, y)) {
case "x":
solve(x + 1, y);
break;
case "y":
solve(0, y + 1);
break;
default:
}
}
else {
for (let n = 0; n < calcAnswerBoardSize; n++) {
if (judgeNumPosition(x, y, n)) {
switch (judgeContinueToFill(x, y)) {
case "x":
solve(x + 1, y);
break;
case "y":
solve(0, y + 1);
break;
default:
}
deleteNumPosition(x, y, n);
}
}
}
}
for (let y = 0; y < WIDTH; y++) {
for (let x = 0; x < HEIGHT; x++) {
if (workBoard[y][x] > 0) {
if (judgeNumPosition(x, y, workBoard[y][x] - 1) === false) {
throw new Error("Unexpected board initialize");
}
}
}
}
solve(0, 0);
}
const postMessage = new Message("returnFromCalcAllPatterns", null);
self.postMessage(postMessage);
}
ところで
私も5か月ぶりにコード読んだので備忘録じゃなくて思い出して書いてるだけです
つまり既忘録です
解説
というほどちゃんとしたものじゃないので期待はしないでくださいね
1~36行目
function judgeNumPosition(x, y, num)
の直前まで
解答盤面を求める際に用いる作業用の変数や配列を宣言し初期化しています
BOARD_SIZE_LISTには採用される盤面サイズの一覧が登録されていて、それぞれに対し解答盤面数を算出します
なお、以下において、その時に使用されている盤面サイズの値を、6行目にあるcalcAnswerBoardSizeで表します
BLOCK_HEIGHTにはcalcAnswerBoardSizeの平方根の整数部分、つまり2乗して盤面サイズを超えない最大の整数が入ります
BLOCK_WIDTHにはcalcAnswerBoardSize / BLOCK_HEIGHTが代入されますが、calcAnswerBoardSizeはブロックのマス数とも等しいので、実質的にブロックの面積を高さで割って横を出しているだけです
workboardは解答盤面を算出する際に用いる、作業用の盤面です
calcAnswerBoardSize = 4のとき、workboardは
1 2 3 4
0 0 0 0
0 0 0 0
0 0 0 0
calcAnswerBoardSize = 6のとき、workboardは
1 2 3 4 5 6
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
となります、理由は後述
なおここに書いたように、numはループなどでは0-basedなのに対し、盤面に入れる際はnum + 1にして1-basedに変換していることに注意してください
dup~系は段、列、ブロックごとの各数字が既に入っているかの真偽値が入ります
これ真偽値の命名規則ミスってる説あるな？
38~47行目
function judgeNumPosition(x, y, num)
について
座標(x, y)にnumを入れることが出来るかの判定
座標(x, y)と同じ段・列・ブロックにnumが存在しなければworkboardの(x, y)にnumを代入しながら各dup~系のフラグを立ててtrueを返し、存在すればfalseを返す
判定だけしてフラグ立てとかの作業は他の関数に渡した方がいいのでは？ あと命名規則ミスってるぞ？
49~54行目
function deleteNumPosition(x, y, num)
について
座標(x, y)のnumを削除し、各dup~系のフラグを下ろす
これnum必要なくない？ 現時点で座標(x, y)にある数字を取得すればよくない？ バグの温床になりそう
56~70行目
function judgeContinueToFill(x, y)
について
例としてcalcAnswerBoardSize = 4のとき、
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
の順で作業マスを移動させるように値を返し、最終マス(今回は16)にいる場合は現在の盤面を解答盤面の一つとして登録する
だからこれも判定だけして解答盤面登録は他の関数に渡した方がいいのでは？
72~104行目, 116行目
function solve(x, y)
と
solve(0, 0);
について
DPの大元になる部分
73行目
if (workBoard[y][x] > 0)
は、trueのとき、初期状態からworkboardのそのマスには数字が入っているため、何もせず次のマスに移動し、falseのとき、数字が入るかの確認をするようにする
74行目
switch (judgeContinueToFill(x, y))
は、帰ってきた値によって次に移動するマスがどれかを指定している
defaultとなるのは最後まで盤面が埋まったときなのでそこでそのパターンは終了する(再帰終了)
87行目
for (let n = 0; n < calcAnswerBoardSize; n++)
は、その作業マスに1 ~ calcAnswerBoardSizeまでの数字を入れている(盤面に入れる際はn + 1になるのに注意)
88行目
if (judgeNumPosition(x, y, n))
は、座標(x, y)にnumを入れることが出来るなら次のマスに移動しようとし、出来ないならそこでそのパターンは終了する(再帰終了)
100行目
deleteNumPosition(x, y, n);
は、再帰終了して戻ってきた際に、今のn + 1がworkboardに入っている情報を削除し、次の数字に進む
もしcalcAnswerBoardSizeまで来ていたら1つ前のマスに戻ることになる(85行目のforが再帰終了)
116行目
solve(0, 0);
で呼び出してあげると再帰が始まる
72行目の分岐を2回書いてあるのでここ直せそう？
他んとこ
特に意味はないので無視
で、結局これは何？
コードレビューです
これ全通りの解答求めてないよね？
正解！ やるやん
は？
いいかげん真面目に書きますと、本来はworkboardの1段目も0で埋められたまっさらな盤面でこのDPを実行することで、真の全通りの解答盤面が得られます
しかし、4x4ではまだしも、これを6x6で行うと解答盤面の総数が28,200,960(≒2.82x10^7)通りとなり、実行時間が長くなることが予想されます
ではどのようにしてこれを高速化したかというと、通常の数独において「数字をそっくり入れ替える」ことは常に可能であることを利用します
例えば、以下の変換が可能です
1 2 3 4 2 1 3 4
3 4 1 2 3 4 2 1
2 3 4 1 -> 1 3 4 2
4 1 2 3 4 2 1 3
左の解答盤面の1を2に、2を1に全て入れ替えたものが右になっています
ということは、入っている数字を変数の状態にした以下の解答盤面から見ると、これらは同一の解答盤面ということになります
a b c d
c d a b
b c d a
d a b c
変数のとき、1段目の文字は(当たり前ですが)互いに異なる文字となるため、aから昇順に並べて問題ないことになります(昇順じゃないものがあったとしても、文字の表記だけをそっくり入れ替えてしまえば昇順にすることが可能なため)
ということで、この昇順に並べたものを1段目に初めから入れておき、変数(文字)だと扱いにくいので再び数字に置きなおしたのが、上記で説明したDPとなります
でも実際には変数じゃなくて数字が入ってるから、これだけだとおかしくならない？
はい、これだけだとおかしくなります、なので変数での解答盤面の数から実際の解答総数を算出する必要があります
初期状態の4x4では、変数での解答盤面の総数は12通りです、しかし実際には288通り存在します
ここで、a, b, c, dに1, 2, 3, 4を1個ずつ代入するパターン数は4!=24通りです
つまり、変数での解答盤面それぞれに数字の入れ方が24通りあるわけです
ということは、解答総数は12x24=288通り……と算出できるわけですね
では、例えば1手目に左上に1を入れたとしましょう
a b c d 1 ? ? ?
c d a b ? ? ? ?
b c d a ? ? ? ?
d a b c ? ? ? ?
上の例だと、a=1となりますが、この解答盤面自体に矛盾は生じません、つまり有効なままです
他の変数での解答盤面でも同様に有効なままなので、変数での解答盤面の総数は12通りのままです
ただ、残りのb, c, dに2, 3, 4を1個ずつ代入するパターン数は3!=6通りになります
よって、解答総数は12x6=72通りとなります
さらに、2手目に右下に1を入れたとしましょう
a b c d 1 ? ? ?
c d a b ? ? ? ?
b c d a ? ? ? ?
d a b c ? ? ? 1
上の例だと、c=1となり、a=cとなるため、これは矛盾します(各変数には異なる数字が入る必要があるため)
これが矛盾しない(つまり右下もaの)盤面は3通りしかありません
残りの3変数に数字を1個ずつ代入するパターン数は先ほどと同じく3!=6通りになります
よって、解答総数は3x6=18通りとなります
では、1の代わりに2を入れたとしましょう
a b c d 1 ? ? ?
c d a b ? ? ? ?
b c d a ? ? ? ?
d a b c ? ? ? 2
上の例だと、c=2となり、a≠cとなるため、これは矛盾しません
これが矛盾するパターンは右下もaのものです、矛盾しないものを数え上げると9通りになります
しかし、変数は残り2つになり、ここに数字を1個ずつ代入するパターン数は2!=2通りになります
よって、解答総数は9x2=18通りとなります
つまり？
パターン数の算出には以下の式を用いています
(変数での解答盤面パターン数)*{(盤面サイズ)-(既に埋まった数字の種類の数)}!
ただし、0!=1としています
この方法を用いることで、6x6での算出が必要なパターン数を6!=720分の1(たったの39,168通り！)(39,168!通りじゃないです)に圧縮することが可能になります
実際の実行時間はというと、手持ちの2015年発売のタブレットくんで3秒弱です(ガバガバ測定)
これをページロード時にのみ実行するので、動作はサクサクと言っていいんじゃないでしょうか
最後に言い残すことはあるか？
原稿料として1円/1Byteください
あともっとここ改善できないかなど思いついた方は是非お知らせください
SATソルバー？ 聞かなかったことにします
追記
function calc3DPatterns() {
const boardSize = 4;
const typeNums = boardSize;
const X_LENGTH = boardSize;
const Y_LENGTH = boardSize;
const Z_LENGTH = boardSize;
const BLOCK_HEIGHT = Math.floor(Math.sqrt(boardSize));
const BLOCK_WIDTH = boardSize / BLOCK_HEIGHT;
let all3DAnswerPattern = [];
let count = 0;
let workBoard = new Array(Z_LENGTH);
for (let z = 0; z < Z_LENGTH; z++) {
workBoard[z] = new Array(Y_LENGTH);
for (let y = 0; y < Y_LENGTH; y++) {
workBoard[z][y] = new Array(X_LENGTH).fill(0);
}
}
for (let x = 0; x < X_LENGTH; x++) {
workBoard[0][0][x] = x + 1;
}
let isOverlappedX = new Array(Z_LENGTH);
for (let z = 0; z < Z_LENGTH; z++) {
isOverlappedX[z] = new Array(Y_LENGTH);
for (let y = 0; y < Y_LENGTH; y++) {
isOverlappedX[z][y] = new Array(typeNums).fill(false);
}
}
let isOverlappedZY = new Array(boardSize);
for (let x = 0; x < X_LENGTH; x++) {
isOverlappedZY[x] = new Array(boardSize / BLOCK_HEIGHT);
for (let z = 0; z < boardSize / BLOCK_HEIGHT; z++) {
isOverlappedZY[x][z] = new Array(boardSize / BLOCK_WIDTH);
for (let y = 0; y < boardSize / BLOCK_WIDTH; y++) {
isOverlappedZY[x][z][y] = new Array(typeNums).fill(false);
}
}
}
let isOverlappedY = new Array(Z_LENGTH);
for (let z = 0; z < Z_LENGTH; z++) {
isOverlappedY[z] = new Array(X_LENGTH);
for (let x = 0; x < X_LENGTH; x++) {
isOverlappedY[z][x] = new Array(typeNums).fill(false);
}
}
let isOverlappedZX = new Array(boardSize);
for (let y = 0; y < Y_LENGTH; y++) {
isOverlappedZX[y] = new Array(boardSize / BLOCK_HEIGHT);
for (let z = 0; z < boardSize / BLOCK_HEIGHT; z++) {
isOverlappedZX[y][z] = new Array(boardSize / BLOCK_WIDTH);
for (let x = 0; x < boardSize / BLOCK_WIDTH; x++) {
isOverlappedZX[y][z][x] = new Array(typeNums).fill(false);
}
}
}
let isOverlappedZ = new Array(Y_LENGTH);
for (let y = 0; y < Y_LENGTH; y++) {
isOverlappedZ[y] = new Array(X_LENGTH);
for (let x = 0; x < X_LENGTH; x++) {
isOverlappedZ[y][x] = new Array(typeNums).fill(false);
}
}
let isOverlappedYX = new Array(boardSize);
for (let z = 0; z < Z_LENGTH; z++) {
isOverlappedYX[z] = new Array(boardSize / BLOCK_HEIGHT);
for (let y = 0; y < boardSize / BLOCK_HEIGHT; y++) {
isOverlappedYX[z][y] = new Array(boardSize / BLOCK_WIDTH);
for (let x = 0; x < boardSize / BLOCK_WIDTH; x++) {
isOverlappedYX[z][y][x] = new Array(typeNums).fill(false);
}
}
}
function canFillNum(x, y, z, num) {
if (isOverlappedX[z][y][num] || isOverlappedZY[x][Math.floor(z / BLOCK_HEIGHT)][Math.floor(y / BLOCK_WIDTH)][num]
|| isOverlappedY[z][x][num] || isOverlappedZX[y][Math.floor(z / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num]
|| isOverlappedZ[y][x][num] || isOverlappedYX[z][Math.floor(y / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num]) {
return (false);
}
return (true);
}
function changeOverlappedFlag(x, y, z, num, bool) {
isOverlappedX[z][y][num] = bool;
isOverlappedZY[x][Math.floor(z / BLOCK_HEIGHT)][Math.floor(y / BLOCK_WIDTH)][num] = bool;
isOverlappedY[z][x][num] = bool;
isOverlappedZX[y][Math.floor(z / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num] = bool;
isOverlappedZ[y][x][num] = bool;
isOverlappedYX[z][Math.floor(y / BLOCK_HEIGHT)][Math.floor(x / BLOCK_WIDTH)][num] = bool;
}
function moveFillingCell(x, y, z) {
if (x === X_LENGTH - 1) {
if (y === Y_LENGTH - 1) {
if (z === Z_LENGTH - 1) {
pushAnswerPattern();
return (false);
}
else {
return ("z");
}
}
else {
return ("y");
}
}
else {
return ("x");
}
}
function pushAnswerPattern() {
all3DAnswerPattern.push(JSON.parse(JSON.stringify(workBoard)));
count++;
}
function solve(x, y, z) {
if (workBoard[z][y][x] > 0) {
changeOverlappedFlag(x, y, z, workBoard[z][y][x] - 1, true);
switch (moveFillingCell(x, y, z)) {
case "x":
solve(x + 1, y, z);
break;
case "y":
solve(0, y + 1, z);
break;
case "z":
solve(0, 0, z + 1);
break;
default:
}
}
else {
for (let n = 0; n < typeNums; n++) {
if (canFillNum(x, y, z, n)) {
workBoard[z][y][x] = n + 1;
changeOverlappedFlag(x, y, z, n, true);
switch (moveFillingCell(x, y, z)) {
case "x":
solve(x + 1, y, z);
break;
case "y":
solve(0, y + 1, z);
break;
case "z":
solve(0, 0, z + 1);
break;
default:
}
workBoard[z][y][x] = 0;
changeOverlappedFlag(x, y, z, n, false);
}
}
}
}
solve(0, 0, 0);
console.log("count", count);
}
console.log
count 32
ほーん
