TypeScript + Reactを勉強するために数独を解くアプリを作った話(処理編)

[画面作る編](https://qiita.com/vranometria/items/a1134eb733f484a2a7f8)の続きです。

普段数独で遊ぶときの思考をプログラムにすることで、TypeScriptとReactを使ってみる試みです。
当方、攻略サイトを見たことがないのですごく効率が悪いかもしれません。


#下ごしらえ
## 行、列、グループ内のセルをまとめて操作する役割のクラスを作る

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/b4337f8f-c73e-81bb-b90e-aa2385927590.png)

行、列、グループの何れにせよ、内部のマスをまとめて操作できると楽なので、
その様な役割を担うCellSetクラスを作成します

``` cellSet.tsx
import CellData from "./cellData"

export default class CellSet {

    id : number;
    cells: CellData[];

    constructor(id:number, cells: CellData[]){
        this.id = id;
        this.cells = cells;
    }

    /** 渡されたマス以外のマスから、可能性を消す */
    erasePossible = (cellData: CellData) :void => {
        this.cells.filter(x => x.id !== cellData.id).forEach(c => c.erasePossible(cellData.value));
    }
}
```

CellSet等をまとめてstateに保持したいので、いっそStateクラスを作って一つにまとめます

CellSetが内包するCellDataとCellSetは相互に参照できた方が楽なので、
CellDataにCellSetインスタンスを渡すようにします。

```cellData.tsx
import CellSet from "./cellSet";

export default class CellData {

  ...

   // メンバー追加
   group: CellSet | null = null;
   row: CellSet | null = null;
   column: CellSet | null = null;
}
```


```state.tsx
import CellData from "./cellData";
import CellSet from "./cellSet";
import Const from "./const";

export default class State {
    /** 81マス */
    cellDatas: CellData[]; 

    /** 9グループ分のCellSet */
    groups: CellSet[] = [];

    /** 9行分のCellSet */
    rows: CellSet[] = [];

    /** 9列分のCellSet */
    columns: CellSet[] = [];

    constructor(cells:CellData[]){
        this.cellDatas = cells;
        this.const = Const.getInstance();

        this.const.nineValues.forEach( id => {

            /* グループ用CellSetの生成、マスからもCellSetにアクセスできるようにする */
            const targetGroupCells = cells.filter(x => x.groupId === id);
            const group = new CellSet(id, targetGroupCells);
            targetGroupCells.forEach( c => c.group = group );
            this.groups.push(group);

            /* 行用の以下略 */
            const targetRowCells = cells.filter(x => x.rowId === id);
            const row = new CellSet(id, targetRowCells);
            targetRowCells.forEach(c => c.row = row);
            this.rows.push(row);

            /* 列用の以下略 */
            const targetColumnCells = cells.filter(x => x.columnId === id);
            const column = new CellSet(id, targetColumnCells);
            targetColumnCells.forEach(c => c.column = column);
            this.columns.push(column);
        });
    }
}
```

stateに保持するクラスが変わるので反映します

``` App.tsx
export default class App extends React.Component < {}, {model: State}> { //変更

  constructor(props: any){
    super(props);
    this.state = { model: new State(this.createDummyCellDatas()) } //変更
    this.handleChange = this.handleChange.bind(this);
    this.readXlsxFile = this.readXlsxFile.bind(this);
  }

  /** 1マスの表示切替 */
  private changeViewMode = () => {
    let model: State = this.state.model;
    model.cellDatas.forEach( c => c.viewMode = c.viewMode === ViewMode.Value ? ViewMode.Possibles : ViewMode.Value); //変更
    this.setState({model: model});
  }

  /** XLSXファイルを読み込み、CellDataを生成してstateに格納する */
  private readXlsxFile = (file: File) => {
    const reader = new FileReader();
    reader.onload = (e) => {

     ...

      this.setState({ model: new State(cells) }); //変更
    }
    reader.readAsArrayBuffer(file);
  }
}
```


## １マスの値が確定したとき、行・列・グループから可能性を消す

1マスの値が確定したときの処理を作ります。
①valueに確定値を入れ、可能性をクリアする　②グループ・列・行の確定マス以外から可能性を消す処理をします。
CellDataクラスに値を確定させるdetermineメソッドを作成し、
行・列・グループのerasePossibleメソッドでまとめて可能性を消し込みます

```cellData.tsx
export default class CellData {

    /** 値を確定する */
    determine = (value: number) : void => {
        this.value = value;
        this.possibles = []
        this.group?.erasePossible(this);
        this.row?.erasePossible(this);
        this.column?.erasePossible(this);
    }
}
```

# 解く

## ファイル読み込み直後の可能性消し

ファイルを読み込んだ時点で値が決まっているマスをもとに可能性を消します

``` App.tsx
export default class App extends React.Component < {}, {model: State}> {

  /** XLSXファイルを読み込み、CellDataを生成してstateに格納する */
  private readXlsxFile = (file: File) => {
    const reader = new FileReader();
    reader.onload = (e) => {
      ...
   
      //追加
      const state = new State(cells);
      state.init();
      this.setState({ model: state });
    }
    reader.readAsArrayBuffer(file);
  }
}
```

```state.tsx
export default class State {
   
    ...
    
    init = () => this.cellDatas.filter( c => c.value).forEach( c => c.determine(c.value) );
}
```

これにより、以下のデータを読み込んだ直後は、
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/5b74b7cd-d740-c6bf-118b-e46a0ee4777d.png)

可能性表示がこの様になります
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/54ab1063-d7fe-38cf-4a51-75906accacb2.png)


## グループ・列・行の中で、１マスしか可能性が残ってない場合は確定する

以下のように、可能性を取りうるマスが一つしかない場合は確定します
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/cc15b670-3d69-8729-a8b3-c2b396aedcfb.png)

```cellSet.tsx
import CellData from "./cellData"
import { Const } from "./const"; //追加

export default class CellSet {

    ...

    
    /**
     *　集合内のセルで、可能性を持つマスが一つだけの場合は確定する
     */
    determineJustOnePossible = () => {
        Const.NINE_VALUES.forEach( n => {
            let hasPossibleCells = this.cells.filter( c => c.possibles.includes(n)) ;
            if(hasPossibleCells.length === 1){
              hasPossibleCells[0].determine(n);
            }
        });
    }
}
```

```state.tsx

export default class State {

    ...

    culcNextState = () => {
        [ this.groups, this.rows, this.columns ].flat().forEach( g => g.determineJustOnePossible() );
    }
}
```

```App.tsx
export default class App extends React.Component<{}, { model: State }> {

  /**
   * 確定値の探索
   */
  private executeNext = (): void => {
    let state:State = this.state.model;
    state.culcNextState();
    this.setState({model: state});
  }
}
```

# 1グループ内で可能性が並んでいる場合は、他グループの同じ行位置・列位置から可能性を消す

1つのグループ内で、
①可能性が２マスか３マスまで絞られている
②一列に並んでいる
とき、同じ行位置、または列位置の他マスがもつ可能性を消します


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/59694c93-c59a-2521-f412-111881f9dc14.png)


``` state.tsx

export default class State {

    ...

    culcNextState = () => {
        [ this.groups, this.rows, this.columns ].flat().forEach( g => g.determineJustOnePossible() );

        this.erasePossibleFromAlinedPossible(); // 追加
    }



     /**
     * 残っている可能性が並んでいるとき、ほかグループのマスから可能性を消す
     */
      erasePossibleFromAlinedPossible = () => {

        Const.NINE_VALUES.forEach( n => {
            this.groups.forEach( group => {

                // 2マスか3マスまで絞られているか
                const cells = group.cells.filter( c => c.possibles.includes(n) );
                if(cells.length !== 2 && cells.length !== 3){return;}

                const rowId = cells[0].rowId;
                const columnId = cells[0].columnId;
                const otherGroupCells = this.cellDatas.filter( c => c.groupId !== group.id );

                // 絞られたマスは行方向に並んでいるか？  並んでいたら別グループの同行マスから可能性を消す　行方向でも同じことをする
                const targetCells = cells.every( x => x.rowId === rowId ) ? otherGroupCells.filter( g => g.rowId === rowId) 
                : cells.every(x => x.columnId === columnId) ? otherGroupCells.filter( c => c.columnId === columnId)  
                : [];

                targetCells.forEach(c => c.erasePossible(n));
            });
        });
    }
}

```

## ペアがあったら、ペア値以外の可能性を消す


一つの行・列・グループの中において、「残った可能性が２つで、可能性の数字が同じマス」がある場合、
その２つを勝手にペアと呼ぶことにします

場合によっては、マスの値が確定していなくても確定したものとして考えられます

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/c5866823-f426-ecad-7e69-0ed058c277af.png)





ペアが見つかると、その２つの可能性以外は一旦考えなくて良くなります
以下の様な場合、4・6でペアができ、3,1,7の可能性を消せます
また、その結果1・3でペアができるので、７の位置が確定します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/a872d6a7-67f1-d9b8-89b3-a58dd4274706.png)

``` cellSet.tsx
    /**
     * ペアを探し、発見したらそれ以外の可能性を消す
     */
    findPairs = () => {

        Const.NINE_VALUES.forEach(n1 => {

            // 2マスまで絞れている可能性を抽出(p1)
            const p1 = this.cells.filter(x => x.possibles.includes(n1));
            if (p1.length !== 2) { return; }

            Const.NINE_VALUES.filter(n2 => n2 > n1).forEach(n2 => {

                // p1以外で、２マスまで絞れている可能性を抽出(p2)
                const p2 = this.cells.filter(x => x.possibles.includes(n2));
                if (p2.length !== 2) { return };

                // p1とp2が同じマスである場合はペアを作成。ペアの値以外を可能性から消す。
                if (p1.every(p => p2.includes(p))) {
                    p1.forEach(p => {
                        p.possibles = [n1, n2];
                    });
                }
            });
        });
    }
```


``` state.tsx

export default class State {

    culcNextState = () => {

        ...

        [ this.groups, this.rows, this.columns ].flat().forEach( g => g.findPairs() ); //追加
    }
}
```

# 実行

ここまで実装してテストしたところ、手持ちの問題が結構解ける様でした

画面作成編で使っていた問題を入れてみます


![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/79e9ebea-0be6-4545-eca2-83099224ff83.png)

読み込み直後
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/1a14c389-3ec9-0525-be49-f07c9455c976.png)


Execute 1回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/7c34151f-08d6-384a-5965-428f9cb9006b.png)


Execute 2回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/05f69092-6e57-a9bb-f744-d43e96e1964a.png)

Execute 3回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/9e0275d2-c371-c4fe-8677-a88f5206941b.png)

Execute 4回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/18ba9e53-3e87-ea14-e3f5-31626f52ff25.png)

Execute 5回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/debf43b7-4698-ed78-6189-380c2dd875f4.png)

Execute 6回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/c5bf821e-a230-1d98-b3af-02dcc40945b2.png)

Execute 7回目

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/156655/78cf61c3-2fdf-f2d6-7238-90cc2d9d650a.png)

解けました。

この実装は可能性から推測できる問題にのみ使えるので、
推測だけでは解けないトライアンドエラーが必要となる問題に対しては無力です
そういう問題に対してはバックトラック法を使うことになります


# 感想

・思っていたよりも経過がわかりにくかったので、差分は赤色で表示したほうが良かった
・stateで保持するクラスにメソッドを持たせると、改修が重なって行くにつれて巨大化しそう。どうなんだろう？
・型があるとわかりやすいと改めて思いました。でもJavaScriptが好きな人は逆に嫌いそう