Skip to content

Main content

3SAT Instance Generator Source Code

Browse the implementation files for 3SAT Instance Generator.
tool.ts typescript
// Tool: 3SAT Instance Generator

type GenerationMode = 'planted-satisfiable' | 'unrestricted';

const MAX_CLAUSES = 10_000;
const MAX_VARIABLES = 10_000;
const MODES: GenerationMode[] = [
	'unrestricted',
	'planted-satisfiable'
];

const parsePositiveInteger = (
	input: unknown,
	maximum: number
): number | null => {
	if (
		(typeof input !== 'string' && typeof input !== 'number') ||
		(typeof input === 'string' && input.trim() === '')
	) {
		return null;
	}

	const value = Number(input);

	return Number.isSafeInteger(value) &&
		value >= 1 &&
		value <= maximum
		? value
		: null;
};

const parseProbability = (input: unknown): number | null => {
	if (
		(typeof input !== 'string' && typeof input !== 'number') ||
		(typeof input === 'string' && input.trim() === '')
	) {
		return null;
	}

	const value = Number(input);

	return Number.isFinite(value) && value >= 0 && value <= 1
		? value
		: null;
};

const createRandom = (seed: string): (() => number) => {
	let state = 2166136261;

	for (let index = 0; index < seed.length; index += 1) {
		state ^= seed.charCodeAt(index);
		state = Math.imul(state, 16777619);
	}

	return () => {
		state += 0x6d2b79f5;
		let value = state;
		value = Math.imul(value ^ (value >>> 15), value | 1);
		value ^= value + Math.imul(value ^ (value >>> 7), value | 61);

		return ((value ^ (value >>> 14)) >>> 0) / 4294967296;
	};
};

const randomInteger = (
	minimum: number,
	maximum: number,
	random: () => number
): number =>
	minimum + Math.floor(random() * (maximum - minimum + 1));

export const generate3satInstance = (
	variableCountInput: unknown,
	clauseCountInput: unknown,
	positiveLiteralProbabilityInput: unknown,
	distinctVariablesInput: unknown,
	modeInput: unknown,
	seedInput: unknown
): string => {
	const variableCount = parsePositiveInteger(
		variableCountInput,
		MAX_VARIABLES
	);
	const clauseCount = parsePositiveInteger(
		clauseCountInput,
		MAX_CLAUSES
	);
	const positiveLiteralProbability = parseProbability(
		positiveLiteralProbabilityInput
	);

	if (
		variableCount === null ||
		clauseCount === null ||
		positiveLiteralProbability === null ||
		(distinctVariablesInput !== 'yes' &&
			distinctVariablesInput !== 'no') ||
		!MODES.includes(modeInput as GenerationMode) ||
		typeof seedInput !== 'string' ||
		seedInput.trim() === '' ||
		(distinctVariablesInput === 'yes' && variableCount < 3)
	) {
		return '';
	}

	const mode = modeInput as GenerationMode;
	const random = createRandom(seedInput);
	const plantedAssignment =
		mode === 'planted-satisfiable'
			? Array.from(
					{ length: variableCount },
					() => random() < 0.5
				)
			: undefined;
	const clauses: number[][] = [];

	for (let clauseIndex = 0; clauseIndex < clauseCount; clauseIndex += 1) {
		const variables: number[] = [];

		while (variables.length < 3) {
			const variable = randomInteger(1, variableCount, random);

			if (
				distinctVariablesInput === 'no' ||
				!variables.includes(variable)
			) {
				variables.push(variable);
			}
		}

		const clause = variables.map((variable) =>
			random() < positiveLiteralProbability
				? variable
				: -variable
		);

		if (
			plantedAssignment !== undefined &&
			!clause.some(
				(literal) =>
					(literal > 0) ===
					plantedAssignment[Math.abs(literal) - 1]
			)
		) {
			const literalIndex = randomInteger(0, 2, random);
			const variable = Math.abs(clause[literalIndex]);
			clause[literalIndex] = plantedAssignment[variable - 1]
				? variable
				: -variable;
		}

		clauses.push(clause);
	}

	return JSON.stringify(
		{
			clauseCount,
			clauses,
			distinctVariables: distinctVariablesInput === 'yes',
			mode,
			positiveLiteralProbability,
			...(plantedAssignment === undefined
				? {}
				: { plantedAssignment }),
			seed: seedInput,
			variableCount
		},
		null,
		2
	);
};

export const Tool: TypeTool = {
	name: '3SAT Instance Generator',
	slug: 'generate/3sat-instance',
	intro: 'Generate a reproducible Boolean 3SAT instance as JSON.',
	tool: generate3satInstance,
	i: [
		{
			example: '20',
			label: 'Variable Count',
			placeholder: 'Number of Boolean variables',
			type: 'number',
			value: 20
		},
		{
			example: '80',
			label: 'Clause Count',
			placeholder: 'Number of three-literal clauses',
			type: 'number',
			value: 80
		},
		{
			example: '0.5',
			help: 'Probability that a generated literal is positive before satisfiability adjustment.',
			label: 'Positive Literal Probability',
			placeholder: 'Probability from 0 to 1',
			type: 'number',
			value: 0.5
		},
		{
			example: 'yes',
			label: 'Distinct Variables per Clause',
			placeholder: 'Require distinct variables',
			type: 'select',
			value: 'yes',
			options: [
				{ value: 'yes', text: 'Yes', selected: true },
				{ value: 'no', text: 'No' }
			]
		},
		{
			example: 'unrestricted',
			label: 'Generation Mode',
			placeholder: 'Select a generation mode',
			type: 'select',
			value: 'unrestricted',
			options: [
				{
					value: 'unrestricted',
					text: 'Unrestricted',
					selected: true
				},
				{
					value: 'planted-satisfiable',
					text: 'Planted satisfiable'
				}
			]
		},
		{
			example: 'tool.io',
			label: 'Seed',
			placeholder: 'Random seed',
			type: 'text',
			value: 'tool.io'
		}
	],
	o: [
		{
			example: '{ "clauses": [[1, -2, 3]] }',
			label: '3SAT Instance',
			placeholder: 'Generated JSON will appear here...',
			render: 'textarea',
			type: 'text'
		}
	],
	cite: [
		{
			title: 'Boolean satisfiability problem - Wikipedia',
			url: 'https://en.wikipedia.org/wiki/Boolean_satisfiability_problem'
		}
	]
};

export default Tool;

Description

Browse the implementation files for 3SAT Instance Generator.

References

  1. Tool.io on GitHub
  2. Tool.io TypeScript tools library

Similar or alternative tools