ascendant

An automated solver for Skyscrapers^↗ puzzles.

Run

Clone the repository:

> git clone https://github.com/Sup2point0/ascendant

You will need Rust nightly^↗ since the project uses generic_const_exprs.

ascendant> cargo run

Some example puzzles are provided in src/examples.rs.

Progress

size	full easy	full hard	sparse
4x4	solvable	solvable	solvable
5x5	solvable	solvable	solvable
6x6	solvable	solvable	–
7x7	solvable	solvable
8x8	–

Algorithm

Outline

The solving algorithm is iterative – it’ll keep passing over the grid, trying to make logical deductions, until it can no longer find any.

The steps in each pass-through are as follows (they are executed in this order to optimise deduction rate, but the order is irrelevant, really):

• Use the clues to establish a foundation of what digits each cell might take on.
  • For instance, a lane with a clue of $4$ in a $6 \times 6$ puzzle could start with any of ${ 1, 2, 3 }$, but not ${ 4, 5, 6 }$.
• If a peak has been found, further use the clues to establish ascending sequences of candidates.
• Use the rules of Sudoku to eliminate invalid candidates.
• Find cells which are the only place in their lane for a digit to go.
  • For instance, if the middle cell of a row is the only one with $2$ as a candidate, then we know $2$ must go in that middle cell.
• Find cells with only 1 candidate left – these cells have been solved.

Philosophy

• The goal is to get as far as possible with purely logical deductions, i.e. no ‘guesswork’ or ‘backtracking’. Even though guesswork isn’t well-defined^↗...
• The strategies I plan on implementing are mostly those covered in Skyscraping^↗.
• If we stick firmly to this, then we may be able to also generate new skyscrapers puzzles!

Terminology

• Skyscraper: One value in a cell. For instance, the “5-skyscraper”.
• Lane: A straight line of cells in the $x$ or $y$ direction.
• Row: A horizontal lane, determined by a $y$ index.
• Col: A vertical lane, determined by an $x$ index.
• Peak: An $N$-skyscraper in an $N \times N$ puzzle. Akin to a ‘maximum’ in mathematics.
• Sequence: An ascending sequence of skyscrapers, looking from a clue across the lane towards the peak. Ideally strictly ascending, but not always so.