loading
main.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
// Sudoku uses numbers 1-9
const SIZE = 9;

/**
 * Generates an array with values.
 *
 * @param  {Number}   len
 * @param  {Function} [callback]
 * @return {Array}
 */
const generateArray = (len, callback = () => {}) =>
	Array.apply(null, { length: len }).map(callback);

// [1, 2, 3, 4, 5, 6, 7, 8, 9]
const NUMBERS = generateArray(SIZE, (_, index) => index + 1);

/**
 * Shuffles an array.
 *
 * @param  {Array}   array
 * @param  {Boolean} [shouldMutate=false]
 * @return {Array}
 */
const shuffleArray = (array = [], shouldMutate = false) => {
	const arr = shouldMutate ? array : array.slice();
	for (let i = arr.length - 1; i > 0; i--) {
		const j = Math.floor(Math.random() * (i + 1));
		const temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	return arr;
};

/**
 * Generates row.
 *
 * @return {Array}
 */
const generateRow = () => shuffleArray(NUMBERS);

/**
 * Given output, checks if row is usable.
 *
 * @param  {Number}  index
 * @param  {Array}   row
 * @param  {Array}   output
 * @return {Boolean}
 */
const isRowUsable = (index, row = [], output = []) => {
	let rowIndex = output.length - 1;
	for (; rowIndex > -1; rowIndex--) {
		let columnIndex = output[rowIndex].length - 1;
		for (; columnIndex > -1; columnIndex--) {
			// check if row value exists in output column
			const rowValue = row[columnIndex];
			if (rowValue === output[rowIndex][columnIndex]) return false;

			let rowStart = 6;
			if (index < 3) {
				rowStart = 0;
			} else if (index < 6) {
				rowStart = 3;
			}

			let columnStart = 6;
			if (columnIndex < 3) {
				columnStart = 0;
			} else if (columnIndex < 6) {
				columnStart = 3;
			}

			let section = [];
			for (i = 0; i < 3; i++) {
				if (output[rowStart + i] instanceof Array) {
					section = section.concat(
						output[rowStart + i].slice(columnStart, columnStart + 3)
					);
				}
			}

			// check if row value exists in output 3x3 section
			if (section.indexOf(rowValue) !== -1) return false;
		}
	}
	return true;
};

/**
 * Generates a solution to a Sudoku puzzle.
 *
 * @return {Array}
 */
const generateSolution = () => {
	// seed 1st row
	const output = [generateRow()];

	// generate rows 2 to 8
	let loopCount = 0;
	for (let index = 1; index < 8; index++) {
		while (true) {
			const row = generateRow();
			if (isRowUsable(index, row, output)) {
				output[index] = row;
				loopCount = 0;
				break;
			}
			loopCount++;
			// break and try again if stuck in infinite loop
			if (loopCount > 2e5) return generateSolution();
		}
	}

  // invert the output
	const columnValues = output.reduce((result, row, rowIndex) => {
		row.forEach((columnValue, columnIndex) => {
			result[columnIndex] = result[columnIndex] || [];
			result[columnIndex][rowIndex] = columnValue;
		});
		return result;
	}, []);

	// get 9th row
	const lastRow = [];
	for (let number = SIZE; number > 0; number--) {
		for (let i = columnValues.length - 1; i > -1; i--) {
			if (columnValues[i].indexOf(number) === -1) {
				lastRow[i] = number;
				break;
			}
		}
	}
	output.push(lastRow);

	return output;
};

console.log(generateSolution());
Native Browser JavaScript