Logo

Programming-Idioms

# 10 Recursive solver
Finds the next empty cell. If none found, the board is solved — return it. Otherwise, try numbers 1–9: If valid, set the cell and recurse. If recursion succeeds, return the result. If all numbers fail, return nil to backtrack.
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
#include <stdlib.h>
#include <time.h>
srand(time(NULL));
for (int i = 0; i < N-1; ++i)
{
    int j = rand() % (N-i) + i;
    int temp = x[i];
    x[i] = x[j];
    x[j] = temp;
}
(shuffle x)
#include <algorithm>
#include <vector>
std::random_shuffle(x.begin(), x.end());
using System;
using System.Collections.Generic;
using System.Linq;
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> input)
    => input.OrderBy(_ => Guid.NewGuid());

using System;
using System.Collections.Generic;
private static Random rng = new Random();  

public static void Shuffle<T>(this IList<T> x)  
{  
    int n = x.Count;  
    while (n > 1) {  
        n--;  
        int k = rng.Next(n + 1);  
        T value = x[k];  
        x[k] = x[n];  
        x[n] = value;  
    }  
}
import std.random;
randomShuffle(x);
var shuffled = x.toList()..shuffle();
x.shuffle();
y = Enum.shuffle x
[Y||{_,Y} <- lists:sort([ {rand:uniform(), N} || N <- X])].
module M_shuffle
contains
function scramble( number_of_values ) result(array)
   integer,intent(in)    :: number_of_values
   integer,allocatable   :: array(:)
   array=[(i,i=1,number_of_values)]
   n=1; m=number_of_values
   do k=1,2
    do i=1,m
     call random_number(u)
     j = n + FLOOR((m+1-n)*u)
     itemp=array(j); array(j)=array(i); array(i)=itemp
    enddo
   enddo
end function scramble
end module M_shuffle
 :
use M_shuffle, only : scramble
newlist=list(scramble(size(list))

import "math/rand"
for i := len(x) - 1; i > 0; i-- {
	j := rand.Intn(i + 1)
	x[i], x[j] = x[j], x[i]
}
import "math/rand"
func shuffle[T any](x []T) {
	rand.Shuffle(len(x), func(i, j int) {
		x[i], x[j] = x[j], x[i]
	})
}
import "math/rand"
rand.Shuffle(len(x), func(i, j int) {
	x[i], x[j] = x[j], x[i]
})
import "math/rand"
for i := range x {
	j := rand.Intn(i + 1)
	x[i], x[j] = x[j], x[i]
}
import "math/rand"
y := make([]T, len(x))
perm := rand.Perm(len(x))
for i, v := range perm {
	y[v] = x[i]
}
x.shuffle()
shuffle x = if length x < 2 then return x else do
	i <- System.Random.randomRIO (0, length(x)-1)
	r <- shuffle (take i x ++ drop (i+1) x)
	return (x!!i : r)

for (var i = x.length - 1; i > 0; i--) {
    var j = Math.floor(Math.random() * (i + 1));
    var temp = x[j];
    x[j] = x[i];
    x[i] = temp;
}
import static java.util.Arrays.asList;
import static java.util.Collections.shuffle;
shuffle(asList(x));
import java.util.Collections;
Collections.shuffle(x);
x.shuffle()
val y = x.shuffled()
(let ((end (length x)))
 (loop for i from 0 below end
       do (rotatef (aref x i)
                   (aref x (+ i (random (- end i)))))))

function(x)
	for i = #x, 2, -1 do
		local j = math.random(i)
		x[i], x[j] = x[j], x[i]
	end
end

shuffled = {}
for i, v in ipairs(x) do
	local pos = math.random(1, #shuffled+1)
	table.insert(shuffled, pos, v)
end
@import GameplayKit;
x.shuffledArray
shuffle($x);
var Iter,rr: integer; 
[...]
  for Iter := 0 to high(x) do
    begin
      rr := random(high(x))+1;
      tmp := x[Iter];
      x[Iter] := x[rr];
      x[rr] := tmp;
    end;
use List::Util 'shuffle';
@shuffled = shuffle(@x);
import random
random.shuffle(x)
from random import shuffle
shuffle(x)
y = x.shuffle
use rand::seq::SliceRandom;
use rand::thread_rng;
let mut rng = thread_rng();
x.shuffle(&mut rng);
extern crate rand;
use rand::{Rng, StdRng};
let mut rng = StdRng::new().unwrap();
rng.shuffle(&mut x);
use std::hash::{BuildHasher, Hasher, RandomState};
pub fn shuffle<T>(vec: &mut [T]) {
    let n = vec.len();
    for i in 0..(n - 1) {
        let j = rand() % (n - i) + i;
        vec.swap(i, j);
    }
}

pub fn rand() -> usize {
    RandomState::new().build_hasher().finish() as usize
}
import scala.util.Random
val shuffled = Random.shuffle(x)
(shuffle x)
(define shuffle
  (lambda (x)
    (if (< (length x) 2) 
        list
        (let ((item (list-ref list (random (length x)))))
          (cons item (shuffle (remove item x)))))))
x shuffled.
SudokuSolver >> solve
    | empty row col |
    empty := self findEmptyCell.
    empty isNil ifTrue: [^ board].
    row := empty // 9.
    col := empty \\ 9.
    1 to: 9 do: [:num |
        (self isValidAtRow: row col: col value: num) ifTrue: [
            | newBoard result |
            newBoard := self setCellAtRow: row col: col value: num.
            self board: newBoard.
            result := self solve.
            result ifNotNil: [^ result].
        ].
    ].
    ^ nil

Function Shuffle(Of T)(collection As IEnumerable(Of T)) As List(Of T)
    Dim r As Random = New Random()
    Shuffle = collection.OrderBy(Function(a) r.Next()).ToList()
End Function

Preview