blog.dnpp.org

ナンプレ (いわゆる数独) の問題を可逆圧縮する。

世界一難しいらしい問題

情報を圧縮したい。

上の画像の様な問題を眺めていて、圧縮しやすそうだなぁと思いませんか？僕は思います。

Ah3gBgSiIDgiIZiQlmdHZpgZ-WMcA という Web Safe な base64 文字列に圧縮できそうな気がするので圧縮していきます。

圧縮してどうするの。

盤面をシェアする URL にすることができます。

例えば https://unp.dnpp.org/Ah3gBgSiIDgiIZiQlmdHZpgZ-WMcA このようなリンクを生成することができます。

URL の中に必要な情報を全て入れることによって Lambda@Edge に動的に静的な HTML を遅延評価で生成させるという目論見です。

実装方針を考える。

数独の盤面を構築している情報について考えます。

  • 81 マス
  • 1 ~ 9 の数字か、空白の 10 種類

ここで「出題された問題のみを対象とする」という前提を置きましょう。ユーザーが入力した数字なのか、初期配置の数字なのかという情報を不要にします。

  • 空白は 0
  • 左上から右下に向かって走査する

と決めてやれば、 10 進数 81 桁の数字で表現できそうです。

このルールで、ヘッダ画像にあるような問題を表現してみます。

800000000003600000070090200050007000000045700000100030001000068008500010090000400

情報を観察する。

情報技術の教科書によく出てくる符号化が使えないか、データの特性をよく観察してみます。

よく見ると 0 が連続しているので、単純なランレングス符号化が効きそうな気がしてきます。数独の問題は 81 マス中、 30 から 40 ほどは空きマスであるという特性があるので、この特性を良い感じに利用できると圧縮効率が上がりそうですね。

ここで「マスが空白であるかどうか」という 1 bit の情報を先に抜き出すことを考えます。

上記の例で言うと

100000000001100000010010100010001000000011100000100010001000011001100010010000100

という 81 bit の情報になります。その後、問題から 0 でない数字を並べると

836792574571316885194

という 10 進数の数字になります。しかしよく見ると、この数字は 1 ~ 9 の 9 つの数字しか出てこないので、各桁から 1 を引いて 9 進数の数字として扱うことができます。

詳細な計算は省きますが、ここで 9 進数として扱ってやると少し情報を節約できるので、最終的な base64 にしたときに 1 文字削れる可能性が高まります。

base64 の情報量は 1 文字あたり 6 bit

なので扱うバイナリが 6 の倍数の長さであると嬉しいのですが、現実のデータは残念ながら 6n のビット列にならない場合の方が多く、ここでパディングの問題が生じます。

ここで最初に「マスが空白であるかどうか」という情報を 81 bit 固定長のデータで表現したことを利用します。この情報に 3 bit 足して 84 bit 固定長のバイナリにすると 6 の倍数になって base64 的に嬉しい訳です。

後ろに続く任意長バイナリをデコードする際のパディングの桁数の表現には 3 bit で丁度良いので、ここに情報を格納することにしましょう。

まとめると

  • 81 bit (数字が入っているかどうかの bit パターン)
  • 3 bit (任意長バイナリのパディング桁数)
  • 6n bit (9進数の数字 + パディング)

このような情報で表現してやることで、 base64 エンコードフレンドリーなバイナリにすることができそうです。

実際には

  • RFC5646 で定義されている言語情報
  • カラーテーマ
  • フォント

の情報も一緒に格納しているので、3文字程データ量が増えていますが、本筋ではないので割愛します。

そして例え正しくデコードできたとしても、ナンプレ・数独の問題として成立するかは別問題なため、ソルバーに結果を食わせて、問題として成立しているか、難易度はどのくらいか、などのチェックもしています。

ということで、あらゆる問題を表現できる

この世界に存在する 9x9 の全てのナンプレ、数独の問題がシェア可能です。やったね。

シェアされた問題は僕が作った アプリ で開いて遊べます。

締め

個人開発しているアプリにシェア機能を実装したときの技術的な話でした。

盤面データのシリアライズ周りのアイデアと実装は割とすぐ終わったけど、どちらかと言えば実際に泥臭くて大変だったのは Lambda@Edge で動く Web アプリケーションの開発の方で、ここにも現実のプロダクト開発によくあるギャップがありますね…。

小ネタとして Lambda@Edge のダミーサーバーを esbuild + tsx + vanilla react で作ったり、 cdk デプロイの際に差分が出ないような決定的な zip を作ったり、sharp で OGP 画像を動的に作ったり、などの話もあるっちゃあります。

実際の開発時の発想は記事とは逆の順番で「絶対にサーバー代を掛けたくないし、メンテフリーであって欲しいし、しかし絶対に落ちて欲しくない」というところから出発して、 Lambda@Edge にコンテンツを生成させて CloudFront にキャッシュさせる構成で実現できることから膨らませていきました。

実際お金も掛かってないし満足の行く出来です。

自己PR

作ったアプリは こちら

SwiftUI のみで実装されていて、 iOS/macOS/visionOS で動きます。

アプリを作ったときの問題生成アルゴリズムの話は こちら

無料・完全に広告なしです。是非遊んでやってください。 (もちろん気に入ったら課金してくれると嬉しい)