Databases
StackOverflow2013
Postsdbo
POSolving Sudoku using a genetic algorithm
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POSolving Sudoku using a genetic algorithm
    primarykey
    data
    text
    <p>I've taken on the task of creating a sudoku solver using a genetic algorithm.</p> <p><strong>Initialization</strong>: Store the given values in each chromosome, and then randomly generate values such that each row is a valid permutation of the values 1 through 9.</p> <p><strong>Fitness</strong>: Determined by the number of "out of place" values in each row, column, and square grid, added together.</p> <p><strong>Fitness Function</strong>: Typical roulette wheel selection</p> <p><strong>Selection</strong>: Random, but weighted using the roulette wheel.</p> <p><strong>Crossover</strong>: Randomly choose various rows from two parents, which creates one child. (I've also implemented a crossover that randomly chooses 3 rows at a time from the two parents - in an effort to preserve good mini-grids). The following are two example children, one from each crossover method:</p> <pre><code>Parent 1 row 1 Parent 2 row 2 Parent 1 row 3 Parent 2 row 4 Parent 1 row 5 Parent 2 row 6 Parent 2 row 7 Parent 1 row 8 Parent 1 row 9 Parent 1 row 1 Parent 1 row 2 Parent 1 row 3 Parent 2 row 4 Parent 2 row 5 Parent 2 row 6 Parent 1 row 7 Parent 1 row 8 Parent 1 row 9 </code></pre> <p><strong>Mutation</strong>: Initially I just swapped the values at two random locations, but this actually made the algorithm much worse because it introduced duplications in rows which had been valid permutations. So I altered the mutation (which seems to perform best when the chance of mutation is in the 25% - 50% range) to randomly choose a row, and then randomize the ordering of that row (leaving the given values in their correct locations).</p> <p>I also tried a mutation where it chose a random row and then chose two random (non-given) positions in the row and swapped them, but this made the performance much worse as well. (Unlike the swapping of the two random locations, I don't understand why this mutation would make the performance so much worse, yet a mutation to randomize the entire row makes the performance better)</p> <p>My algorithm has yet to solve a puzzle of any difficulty. It will often times get close (in the range of only 6 to 10 conflicts), but it can never get to a solution (it's presumably finding local minima and getting stuck).</p> <p>In an effort to improve the algorithm, I added the ability to replace a large portion of the population (worst performing chromosomes) with completely randomized boards, but this seems to have a minimal effect.</p> <p>What are weak points in my approach? How can I improve the performance?</p> <p>It seems like Sudoku might lend itself to better performance from mutation, as opposed to crossover.</p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USRyan
    1. USRyan
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POSolving Sudoku using a genetic algorithm
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POSolving Sudoku using a genetic algorithm
      1. USSatish Patel
      1. VTFavorite
    1. COWhy use a genetic algorithm for this? Genetic algorithms are usually used for NP-Complete problems, whereas solving a sudoku is much easier (and, in fact, quite an easy algorithm to write)
      singulars
      1. POSolving Sudoku using a genetic algorithm
      1. USJasper
    2. COI believe Soduko solvers are NP-complete problems, but we can solve small Soduko puzzles.
      singulars
      1. POSolving Sudoku using a genetic algorithm
      1. USajon
    3. COajon is right. And this is more of an exercise in tackling various topics using genetic algorithms.
      singulars
      1. POSolving Sudoku using a genetic algorithm
      1. USRyan
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload