logoalt Hacker News

program_whiz • today at 12:53 PM • 0 replies • view on HN

A clarifying way to think about this for sudoku:

For every clue, mark the probability of sampling its number in the row/col to zero. Also mark the probability of selecting a "clue cell" for modification to 0.

Pick a random cell for modification, based on its "energy" (higher energy get modified first):

    1. Every conflicting cell gets energy +1.0 (try to resolve conflicts before new empty cells).  E.g. two 7s on the same row both get +1 energy.

    2. Empty cells have small energy 0.1

    3. Filled cells with no conflicts have energy 0
For the selected cell, choose a digit. Look at numbers in its row/column, every occurrence of a number in the row/col drop prob of sampling by 90%. Example:

    | No. of 7s | chance of 7 |
    | --- | --- |
    | 0 | 10% (equal to other digits) |
    | 1 | 1% |
    | 2 | 0.1% |
Obviously this would get more complex with more numbers on the line (this is just checking 7 on otherwise empty line).

This is essentially what these models are doing. It provides a kind of "wave function collapse" search with random exploration based on "energy", but energy is just defined as conflict / unsolved. For something like a maze, energy is disconnected path segments or walls, etc.