import {
__,
addIndex,
always,
compose,
concat,
cond,
contains,
curry,
difference,
F,
filter,
head,
identity,
intersection,
isEmpty,
isNil,
join,
last,
length,
map,
mapObjIndexed,
merge,
mergeAll,
not,
prop,
range,
reduce,
reject,
split,
splitEvery,
startsWith,
sum,
T,
times,
transpose,
trim,
union,
values,
zip,
} from 'ramda';
const BOARD_SIZE = 9;
const BOX_SIZE = 3;
const BOXES_SIDE = 3;
const POSSIBLE_VALUES = range(1, BOARD_SIZE + 1);
const getCount = compose(
length,
filter(Boolean),
times,
);
const removeOne = (x, xs) => reject(element => element === x, xs);
const getCellCandidates = prop('candidates');
const getCellValue = prop('value');
const getCellX = prop('x');
const getCellY = prop('y');
const getCellsCandidatesLists = compose(
reject(isNil),
map(getCellCandidates),
);
const getCellsValues = compose(
reject(isNil),
map(getCellValue),
);
const getBoxCellsByIndexes = curry((boxX, boxY, board) => {
const cells = [];
for (let y = boxY * BOX_SIZE; y < (boxY + 1) * BOX_SIZE; y += 1) {
for (let x = boxX * BOX_SIZE; x < (boxX + 1) * BOX_SIZE; x += 1) {
const boxCell = board[y][x];
cells.push(boxCell);
}
}
return cells;
});
const iterateOverBoxes = curry((f, board) => {
const results = [];
for (let y = 0; y < BOXES_SIDE; y += 1) {
for (let x = 0; x < BOXES_SIDE; x += 1) {
results.push(f(x, y, board));
}
}
return results;
});
const getBoxesCells = iterateOverBoxes(getBoxCellsByIndexes);
const getBoxValues = ({ x, y }, board) => compose(
getCellsValues,
getBoxCellsByIndexes,
)(
Math.floor(x / BOX_SIZE),
Math.floor(y / BOX_SIZE),
board,
);
const getColumnCellsByIndex = curry((x, board) => map(prop(x), board));
const getColumnsCells = board => times(getColumnCellsByIndex(__, board), BOARD_SIZE);
const getColumnValues = ({ x }, board) => compose(
getCellsValues,
getColumnCellsByIndex,
)(x, board);
const getRowCellsByIndex = prop;
const getRowsCells = board => times(getRowCellsByIndex(__, board), BOARD_SIZE);
const getRowValues = ({ y }, board) => compose(
getCellsValues,
getRowCellsByIndex,
)(y, board);
function obtainBoardCandidates(board) {
function obtainCellCandidates(cell) {
if (getCellValue(cell)) {
return cell;
}
return merge(cell, {
candidates: compose(
difference(__, getBoxValues(cell, board)),
difference(__, getColumnValues(cell, board)),
difference(__, getRowValues(cell, board)),
getCellCandidates,
)(cell),
});
}
return map(map(obtainCellCandidates), board);
}
export function parseBoard(str) {
const isBoardRow = startsWith('|');
function parseRow(rowStr, y) {
function getCell(x) {
const getEmptyCell = () => ({
candidates: POSSIBLE_VALUES,
x,
y,
});
const index = x + 1;
if (index >= rowStr.length) {
return getEmptyCell();
}
const valueStr = rowStr.charAt(index);
if (valueStr === ' ') {
return getEmptyCell();
}
const value = Number(valueStr);
if (!Number.isFinite(value) || value < 1) {
throw Error(
`A row "${rowStr}" contains unexpected character "${valueStr}" at position ${index}`,
);
}
return {
value,
x,
y,
};
}
return times(getCell, BOARD_SIZE);
}
const board = compose(
addIndex(map)(parseRow),
filter(isBoardRow),
map(trim),
split('\n'),
)(str);
if (board.length !== BOARD_SIZE) {
throw new Error(`The board has ${board.length} rows (should be ${BOARD_SIZE})`);
}
return board;
}
/**
* @returns - How much cells were crosshatched.
*/
function crosshatch(board) {
/**
* @returns - How much cells were crosshatched.
*/
function crosshatchBox(x, y, unusedBoard) {
const boxCells = getBoxCellsByIndexes(x, y, board);
/**
* @returns - How much cells were crosshatched.
*/
function crosshatchValue(value) {
function getCellsWidth(cells) {
const xs = map(getCellX, cells);
return Math.max.apply(null, xs) - Math.min.apply(null, xs);
}
function getCellsHeight(cells) {
const ys = map(getCellY, cells);
return Math.max.apply(null, ys) - Math.min.apply(null, ys);
}
const hasCellValue = compose(
cond([
[Boolean, contains(value)],
[T, F],
]),
getCellCandidates,
);
const valueCells = filter(hasCellValue, boxCells);
/**
* @returns - How much cells were crosshatched.
*/
const crosshatchCells = cells => compose(
length,
filter(identity),
map((cell) => {
const candidates = getCellCandidates(cell);
if (!candidates || !contains(value, candidates)) {
return false;
}
cell.candidates = removeOne(value, candidates);
if (cell.candidates.length === 0) {
throw new Error(`Cell (${cell.x}, ${cell.y}) candidates list is empty`);
}
return true;
}),
difference(cells),
)(valueCells);
const firstCell = head(valueCells);
if (getCellsWidth(valueCells) === 0) {
return crosshatchCells(
getColumnCellsByIndex(
getCellX(firstCell),
board,
),
);
} else if (getCellsHeight(valueCells) === 0) {
return crosshatchCells(
getRowCellsByIndex(
getCellY(firstCell),
board,
),
);
}
return 0;
}
return compose(
sum,
map(crosshatchValue),
difference(POSSIBLE_VALUES),
getCellsValues,
)(boxCells);
}
return {
crosshatchedCellsCount: compose(
sum,
iterateOverBoxes,
)(crosshatchBox, board),
};
}
function getBoardRepr(board) {
function getCellRepr(cell) {
const value = getCellValue(cell);
if (value) {
return [
' ',
` ${value} `,
' ',
];
}
const candidates = getCellCandidates(cell);
return compose(
map(join('')),
splitEvery(3),
map(cond([
[last, head],
[T, always(' ')],
])),
zip(POSSIBLE_VALUES),
map(contains(__, candidates)),
)(POSSIBLE_VALUES);
}
const getRowRepr = compose(
join('\n'),
map(join('|')),
transpose,
map(getCellRepr),
);
const delimiter = compose(
concat(__, '\n'),
concat('\n'),
join(''),
times(always('—')),
)((3 * BOARD_SIZE) + (BOARD_SIZE - 1));
return compose(
join(delimiter),
map(getRowRepr),
)(board);
}
/**
* @returns - Affected cells' count.
*/
function obtainCellsCandidatesDomain(cells) {
const findFirst = curry((f, list) => {
for (const element of list) {
const result = f(element);
if (result) {
return result;
}
}
return null;
});
function obtainDomain(_cells, _domain = [], _cellsCount = 0) {
if (_cellsCount >= _cells.length) {
return null;
}
const processCell = (cell) => {
const newDomain = compose(
union(_domain),
getCellCandidates,
)(cell);
const domainAdditionSize = newDomain.length - _domain.length;
const newCellsCount = (_cellsCount + domainAdditionSize) - 1;
if (newCellsCount <= 0) {
return newDomain;
}
return obtainDomain(
removeOne(cell, _cells),
newDomain,
newCellsCount,
);
};
return findFirst(processCell, _cells);
}
/**
* @returns - Affected cells' count.
*/
function applyDomain(domain) {
if (!domain) {
return 0;
}
/**
* @returns - `true` -- if the cell was affected by the domain.
*/
function applyCellDomain(cell) {
const cellCandidates = getCellCandidates(cell);
const candidates = difference(cellCandidates, domain);
if (isEmpty(candidates) || cellCandidates.length === candidates.length) {
return false;
}
cell.candidates = candidates;
return true;
}
return compose(
length,
filter(identity),
map(applyCellDomain),
filter(getCellCandidates),
)(cells);
}
return compose(
applyDomain,
obtainDomain,
filter(getCellCandidates),
)(cells);
}
const obtainBoxesCandidatesDomain = compose(
sum,
map(obtainCellsCandidatesDomain),
getBoxesCells,
);
const obtainColumnCandidatesDomain = curry((x, board) => compose(
obtainCellsCandidatesDomain,
getColumnCellsByIndex(x),
)(board));
const obtainRowCandidatesDomain = curry((y, board) => compose(
obtainCellsCandidatesDomain,
getRowCellsByIndex(y),
)(board));
function obtainBoardCandidatesDomains(board) {
const rowsDomainsCount = getCount(obtainRowCandidatesDomain(__, board), BOARD_SIZE);
const columnsDomainsCount = getCount(obtainColumnCandidatesDomain(__, board), BOARD_SIZE);
const boxesDomainsCount = obtainBoxesCandidatesDomain(board);
return {
boxesDomainsCount,
columnsDomainsCount,
rowsDomainsCount,
};
}
/**
* @returns - Filled in cells' count.
*/
function fillInCellsValues(cells) {
function getUniqueCandidates(candidatesLists) {
const getCandidatesCounts = reduce(
(counts, candidate) => {
if (counts[candidate]) {
counts[candidate] += 1;
} else {
counts[candidate] = 1;
}
return counts;
},
);
const getCandidatesListsCounts = reduce(getCandidatesCounts, {});
return compose(
reject(isNil),
values,
mapObjIndexed((count, candidateStr) => (count === 1 ? Number(candidateStr) : null)),
getCandidatesListsCounts,
)(candidatesLists);
}
/**
* @returns - Filled in cells' count.
*/
function fillInValues(candidates) {
/**
* @returns - Was cell filled.
*/
function fillInValue(cell) {
const cellCandidates = getCellCandidates(cell);
if (!cellCandidates) {
return false;
}
const remainingCandidates = intersection(candidates, cellCandidates);
if (remainingCandidates.length > 1) {
throw new Error(
`Cell (${cell.x}, ${cell.y}) with candidates ${cellCandidates} is invalid.` +
` Unique candidates: ${candidates}.`,
);
}
if (remainingCandidates.length !== 1) {
return false;
}
cell.value = head(remainingCandidates);
delete cell.candidates;
return true;
}
return compose(
length,
filter(identity),
map(fillInValue),
)(cells);
}
return compose(
fillInValues,
getUniqueCandidates,
getCellsCandidatesLists,
)(cells);
}
const fillInBoxesValues = compose(
length,
filter(identity),
map(fillInCellsValues),
getBoxesCells,
);
const fillInColumnsValues = compose(
length,
filter(identity),
map(fillInCellsValues),
getColumnsCells,
);
const fillInRowsValues = compose(
length,
filter(identity),
map(fillInCellsValues),
getRowsCells,
);
function fillInBoardValues(board) {
const rowsObtainedWithValuesCount = fillInRowsValues(board);
let newBoard = obtainBoardCandidates(board);
const columnsObtainedWithValuesCount = fillInColumnsValues(newBoard);
newBoard = obtainBoardCandidates(newBoard);
const boxesObtainedWithValuesCount = fillInBoxesValues(newBoard);
return {
board: newBoard,
stats: {
boxesObtainedWithValuesCount,
columnsObtainedWithValuesCount,
rowsObtainedWithValuesCount,
},
};
}
export function solve(initialBoard) {
let board = initialBoard;
let stats;
do {
board = obtainBoardCandidates(board);
const crosshatchingStats = crosshatch(board);
console.log(getBoardRepr(board));
const {
stats: fillInStats,
board: filledInBoard,
} = fillInBoardValues(board);
board = filledInBoard;
stats = mergeAll([
crosshatchingStats,
obtainBoardCandidatesDomains(board),
fillInStats,
]);
console.log(stats);
} while (compose(
not,
isEmpty,
filter(Boolean),
values,
)(stats));
console.log(getBoardRepr(board));
return board;
}
const main = () => {
const BOARD = `
|9 7
| 5
| 573
| 63 1 4
| 5 2
| 4 9 7
|8 4
|29 8
| 16 `;
const board = parseBoard(BOARD);
const solvedBoard = solve(board);
console.log(getBoardRepr(solvedBoard));
};