数独解法プログラムの解法疑似コードが知りたいです。

前提・実現したいこと

初めまして。都内の普通高校に通うとものです。

私は今、独学でC++のプログラミングを1年ほど学んでおり、夏の期間を使って趣味の数独の採点プログラムを作ろうと考えておりました。
プログラムを組むにあたり、下記のアルゴリズムでの疑似コードを教えていただきたいです。

あるマスに候補数字が一つしかなければそのマスはその候補数字で確定するというロジックです。
下図で○のついた候補数字4のあるマスは4以外の候補数字がないため、このマスは4で確定します。　半角は数独でいうマスに入る可能性の添え字です。

１５ 68　　　　　　１　５　68
④ ３９　　→ 　　　 4 　３　９
48 ７２　　　　　　8　７　２　

どうかご教授いただければ幸いです。

発生している問題・エラーメッセージ

エラーメッセージ

該当のソースコード

 /**
     * 単一候補法
     * @param mat
     * @param candmat
     */
   public void SinglizeCandidateLogic(int[][] mat, int[][] candmat)
    {
        List<Integer> candList = new ArrayList<>();

        for (int i = 0; i < Utility.ROW; i++)
            for (int j = 0; j < Utility.COL; j++)
                if (candmat[i][j] > 0)
                {
                    //候補の取得
                    candList = Utility.GetOnBitList(candmat[i][j]);

                    if (candList.size() == 1)
                    {//1個しか候補なかったら記憶したビットに対応する数字を確定
                        mat[i][j] = candList.get(0);
                        Utility.ExcludeCandidateInRowColBlock(candmat, new Point(i, j), (int)Math.pow(2, candList.get(0)));
                    }
                }
    }

試したこと

コードは試しに書いてみたものですが正確性に乏しいので見なくても大丈夫です。アルゴリズムだけご教授を頂きたいです。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

行動規範の内容に同意します

回答3件

ベストアンサー

ここに各言語での実装がいっぱい載ってます。
C++もありますが、アルゴリズムの異なる４種類が載っているC#はとりわけ参考になると思います。
いいのができたらwikiなので追加してやってください。

投稿2020/08/27 21:20

satocha

総合スコア336

退会済みユーザー

2020/08/27 21:23

面白いまとめですね。

7sstrictly

2020/08/28 01:23

ありがとうございます！参考にさせていただきます。

satocha

2020/08/28 01:47

質問タイトルを「アルゴリズム」から、「疑似コード」に変えたようですね。 C++を使っておられるのでしたら、C#はC++プログラマにとってまさに「疑似コード」ですので、ぜひ読み解いてください。最初の「manual」は総当たりで解を探しているので一番理解しやすいと思います。「ズル」をするなら、３番目の「automatic」ですね。解を探す部分をMSの解探索ライブラリに丸投げしてるのですから。アルゴリズムの勉強にはなりませんが、現実に何かプログラムを作らなければならないようなときに、こういうアプローチを知っておくことも無駄にはなりません。２、４の「amb」「Dancing Links」はどちらもこういうパズル問題に使われる手法なので、ググってみてください。疑似コードやいろいろな言語での実装例が出てきます。

行動規範の内容に同意します

総当たりのコードを書いてみました。

Java
1class Sudoku {
2	char[][] b = new char[9][9];
3
4	public static void main(String[] args) { new Sudoku(); }
5
6	Sudoku() {
7		String[] a = {
8			"8 . . 3 . . 6 . .",
9			". . . . . . . . 3",
10			". 3 1.. . 5 . . .",
11			"3 . . 8 . . 2 . .",
12			". . 7 . 3 . 5 . 4",
13			". 6 . . . 4 . . .",
14			"6 . 4 . 2 . . . .",
15			"1 . . 6 . . 4 . 7",
16			". 5 . . 4 1 . . ."
17		};
18		for (int i = 0; i < 9; i++)
19			for (int j = 0, k = 0; j < 9; j++, k += 2)
20				b[i][j] = a[i].charAt(k);
21		print();
22		solve(0, 0);
23	}
24
25	void print() {
26		for (int i = 0; i < 9; i++) {
27			for (int j = 0; j < 9; j++) System.out.print(" " + b[i][j]);
28			System.out.println();
29		}
30		System.out.println("--");
31	}
32
33	void solve(int i, int j) {
34		if (j == 9) {
35			if (++i == 9) { print(); return; }
36			j = 0;
37		}
38		if (b[i][j] != '.') solve(i, j + 1);
39		else {
40			for (char c = '1'; c <= '9'; c++) 
41				if (ok(i, j, c)) { b[i][j] = c; solve(i, j + 1); }
42			b[i][j] = '.';
43		}
44	}
45
46	boolean ok(int i, int j, char c) {
47		for (int k = 0; k < 9; k++)
48			if (b[i][k] == c || b[k][j] == c) return false;
49		i = i / 3 * 3; j = j / 3 * 3;
50		for (int k = i + 3; i < k; i++)
51			if (b[i][j] == c || b[i][j+1] == c || b[i][j+2] == c) return false;
52		return true;
53	}
54}

入力を標準入力にするなら、

Java
1			for (int j = 0, k = 0; j < 9; j++, k += 2)
2				b[i][j] = a[i].charAt(k);

これを、次のように変更してください。

Java
1			for (int j = 0; j < 9; j++) {
2				char c = 0;
3				do {
4					int v = 0;
5					try {
6						v = System.in.read();
7						if (v < 0) { System.exit(1); }
8					} catch (Exception e) { System.exit(1); }
9					c = (char)v;
10				} while (Character.isWhitespace(c));
11				b[i][j] = Character.isDigit(c) ? c : '.';
12			}