Solitare Solver for MOLEK-SYNTEZ game

solitare.js

(async () => {
const orderedSet = ['6','7','8','9','10','V','D','K','T'];

const nextAbove = c =>
	orderedSet[orderedSet.indexOf(c) + 1];

let moveHistory = [];

const analyze = (state) => {
	let moves = [];
	const w = state.deal.length; // column count

	for (let sc=0; sc<w; sc++) { // source column
		let sh=state.deal[sc].length, ce=sh-1; // card end
		// console.log('card end', { ce, c: deal[sc][ce] });
		for (cb=ce; cb>=0; cb--) { // card begin
			const c = state.deal[sc][cb];
			const na = nextAbove(state.deal[sc][cb]);
			// console.log('card begin', { cb, c, na });
			if (state.deal[sc][cb-1] !== na) break;
		}
		// console.log('card slice', { sc, cb, ce });

		// for each valid slice of sequential range
		for (let cs=cb; cs<=ce; cs++) {
			// for each valid target in remaining columns
			for (let tc=0; tc<w; tc++) {
				let move = {};
				move.cs = cs;
				move.ce = ce;
				const empty = state.deal[tc].length < 1;
				const cards = state.deal[sc].slice(cs, ce+1);
				const to = state.deal[tc].length-1;
				const below = state.deal[tc][to];
				
				// source col must not be empty
				if (state.deal[sc].length < 1) continue;
				// source col must not be target col
				if (tc === sc) continue;
				// target col must be open (not be locked or completed)
				if ('o' !== state.col[tc]) continue;
				
				// target col bottom card must be one of:
				// or not locked
				let valid = false;
				// if source is locked
				if ('l' === state.col[sc]) {
					// must be nextAbove top of source slice
					if (below === nextAbove(state.deal[sc][cs])) {
						valid = true;
					}
				}
				else {
					if (empty) {
						// its fine
						valid = true;
					}
					// nextAbove top of source slice
					else if (below === nextAbove(state.deal[sc][cs])) {
						// its fine
						valid = true;
					}
					else if (1 === cards.length) {
						// its fine but this will lock it
						move.locking = true;
						valid = true;
					}
				}
        
        // TODO: needs a few more rules to be completely successful, but ran out of time
				
				if (true === valid) {
					// console.log('consider '+ JSON.stringify({ cards, sc, cs, ce, cards, tc, to, below }));
					move.cards = [...cards];
					move.sc = sc;
					move.tc = tc;
					move.to = to;
					move.below = below;
					moves.push(move);
				}
			}
		}
	}
	
	// console.log('valid moves:');
	// for (const move of moves) {
	// 	console.log(`  col ${move.sc+1} cards ${move.cards.join(',')} to col ${move.tc} below ${move.below}.`);
	// }

  // TODO: sort moves, prioritizing by some strategy. (not strictly necessary, but may optimize solve time) ie.
  // - favor locking columns that are mostly complete, especially if they end with 6
  // - favor moving stacks to empty columns in ways that don't cause the column to complete 
  
	return moves;
}



const applyState = (state, move) => {
	const newState = {
		deal: [
			[...state.deal[0]],
			[...state.deal[1]],
			[...state.deal[2]],
			[...state.deal[3]],
			[...state.deal[4]],
			[...state.deal[5]],
		],
		col: [...state.col],
	};
	
	const take = newState.deal[move.sc].splice(move.cs, move.ce+1);
	newState.deal[move.tc].splice(move.to+1, 0, ...take);	
	// unlock source (successful moves always unlock)
	newState.col[move.sc] = 'o';
	// lock target
	if (true === move.locking) {
		newState.col[move.tc] = 'l';
	}

	return newState;
};

const isWon = (state) => {
	let cbwt = 0, ce = 0;
	for (let i=0,w=state.deal.length; i<w; i++) {
		const col = state.deal[i];
		if (col.length < 1) ce++;
		else if ('T' === col[0]) cbwt++;
	}
	// 4 cols beginning with T, 2 cols empty
	return 4 === cbwt && 2 === ce;
};

const search = async (state, seen = {}, history=[], depth=0) => {
	process.stdout.write('>');
	const moves = analyze(state);
	const serial = serialize(state);
	if (seen[serial]) return false;
	seen[serial] = true;
	
	// win condition
	if (isWon(state)) return history;
	// stuck; not won and no moves remaining
	else if (moves.length < 0) return false;
	
	// continue tree search recursively
	let result = false, i=0;
	for (const move of moves) {
		i++;
		console.log(`search move ${i}/${moves.length} @ depth ${depth}\n`+serial);
		console.log(`move\n  col ${move.sc+1} cards ${move.cards.join(',')} to col ${move.tc+1} below ${move.below}.\n`);
		// await new Promise(ok=>setTimeout(ok, 100));
		result = await search(applyState(state, move), seen, [...history, move], depth+1);
		if (false !== result) break;
	}
	process.stdout.write('<');
	return result;
};

const pad2 = c =>
	(' '+(c||'  ')).substr(-2);

const serialize = state => {
	let ml = 0;
	for (let i=0,w=state.deal.length; i<w; i++) {
		ml = Math.max(ml, state.deal[i].length);
	}
	let out = '';
	for (let x=0,w=state.deal.length; x<w; x++) {
		out += pad2(state.col[x]) +' ';
	}
	out += '\n';
	for (let y=0; y<ml; y++) {
		for (let x=0,w=state.deal.length; x<w; x++) {
			out += pad2(state.deal[x][y]) +' ';
		}
		out += '\n';
	}
	return out;
};

const initialState = {
	deal: [
		['D',  'V',  'D',  '9',  '10', '9'  ],
		['K',  'K',  '8',  'T',  '9',  '7'  ],
		['T',  'K',  '7',  '6',  '8',  'V'  ],
		['8',  'K',  '6',  'V',  '6',  '10' ],
		['6',  '7',  'T',  '9',  '7',  'D'  ],
		['V',  'T',  '10', '10', 'D',  '8'  ],
	],
	// o = open, l = locked
	col: ['o','o','o','o','o','o'],
};

const result = await search(initialState);

if (null == result) {
	console.log('failed to solve. unwinnable?');
	process.exit(1);
}

console.log('winning solve:');
console.log(JSON.stringify(result, null, 2));
process.exit(0);

})();

i would improve this by making the for...loop into reusable iterator functions which would both simplify the code and ensure that the way the deal data structure is traversed is consistent. i think i got confused at some point and rotated 90deg the order of the cards in the matrix because column-major looks nicer when written in code it looks just like the game board, but row-major is simpler to traverse since it would have been each column arranged in a single array--but then you have to tilt your head for it to resemble the game board. a lame mistake but i put a time limit and didn't want to spend all day perfecting it. i am proud that it has good general structure and shows the concept for a solver. even the output appears to get very close to solving as you see it work.